Here's the C++ solution to Hands-on Project: Sudoku Solver.
type=codeblock|id=cpp_sudoku_solver_official_solution|autocreate=cpp|input=5 3 0 0 7 0 0 0 0\n6 0 0 1 9 5 0 0 0\n0 9 8 0 0 0 0 6 0\n8 0 0 0 6 0 0 0 3\n4 0 0 8 0 3 0 0 1\n7 0 0 0 2 0 0 0 6\n0 6 0 0 0 0 2 8 0\n0 0 0 4 1 9 0 0 5\n0 0 0 0 8 0 0 7 9#include <iostream>using namespace std;const int UNASSIGNED = 0; // empty cells in the sudoku tableconst int N = 9; // sudoku grid size// returns whether or not "number" has been used in particular rowbool usedInRow(int grid[N][N], int row, int number) {for (int col = 0; col < N; col++)if (grid[row][col] == number)return true;return false;}// returns whether or not "number" has been used in particular columnbool usedInCol(int grid[N][N], int col, int number) {for (int row = 0; row < N; row++)if (grid[row][col] == number)return true;return false;}// returns whether or not "number" has been used in particular boxbool usedInBox(int grid[N][N], int row, int col, int number) {int boxStartRow = row - row % 3;int boxStartCol = col - col % 3;for (int ii = 0; ii < 3; ii++)for (int jj = 0; jj < 3; jj++)if (grid[boxStartRow + ii][boxStartCol + jj] == number)return true;return false;}// checks whether or not it is valid to place "number" in the given positionbool isValid(int grid[N][N], int row, int col, int number) {return !usedInRow(grid, row, number) &&!usedInCol(grid, col, number) &&!usedInBox(grid, row, col, number);}// finds the first unassigned or empty cell in sudoku grid. row and column are passed by referencebool findUnassignedLocation(int grid[N][N], int &row, int &col) {for (row = 0; row < N; row++)for (col = 0; col < N; col++)if (grid[row][col] == UNASSIGNED)return true;return false;}// main sudoku solver functionbool solveSudoku(int grid[N][N]) {int row, col;// if there is no unassigned location, then return true - base caseif (!findUnassignedLocation(grid, row, col))return true;for (int number = 1; number <= 9; number++) {// if safeif (isValid(grid, row, col, number)) {// assign valuegrid[row][col] = number;if (solveSudoku(grid))return true;grid[row][col] = UNASSIGNED;}}return false; // this triggers backtracking}// display the gridvoid displayGrid(int grid[N][N]) {for (int row = 0; row < N; row++) {for (int col = 0; col < N; col++)cout << grid[row][col] << " ";cout << endl;}}int main() {int grid[N][N];/*example:0 0 7 9 0 0 6 3 10 0 0 1 0 3 0 4 01 0 0 0 0 5 0 0 96 0 4 8 3 0 0 0 50 0 9 0 0 0 1 0 02 0 0 0 1 7 9 0 45 0 0 3 0 0 0 0 80 9 0 4 0 2 0 0 08 4 6 0 0 1 3 0 0*/cout << "Enter the Sudoku grid (Use 0 for empty cells): " << endl;for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {cin >> grid[i][j];}}cout << endl;if (solveSudoku(grid) == true) {cout << "Solution: " << endl;displayGrid(grid);} else {cout << "No solution exists. " << endl;cout << "Are you sure you entered it correctly?" << endl;}return 0;}
Sample interaction 1:
Enter the Sudoku grid (Use 0 for empty cells):5 3 0 0 7 0 0 0 06 0 0 1 9 5 0 0 00 9 8 0 0 0 0 6 08 0 0 0 6 0 0 0 34 0 0 8 0 3 0 0 17 0 0 0 2 0 0 0 60 6 0 0 0 0 2 8 00 0 0 4 1 9 0 0 50 0 0 0 8 0 0 7 9Solution:5 3 4 6 7 8 9 1 26 7 2 1 9 5 3 4 81 9 8 3 4 2 5 6 78 5 9 7 6 1 4 2 34 2 6 8 5 3 7 9 17 1 3 9 2 4 8 5 69 6 1 5 3 7 2 8 42 8 7 4 1 9 6 3 53 4 5 2 8 6 1 7 9
Sample interaction 2:
Enter the Sudoku grid (Use 0 for empty cells):4 9 0 1 5 7 0 0 00 1 8 0 9 0 0 0 07 5 0 2 8 4 1 0 60 6 0 4 1 5 0 7 01 0 0 7 0 0 4 0 00 0 0 9 0 8 0 6 10 0 7 5 0 0 0 1 36 4 0 0 0 0 2 0 05 0 1 0 7 0 0 8 0Solution:4 9 6 1 5 7 8 3 22 1 8 3 9 6 7 4 57 5 3 2 8 4 1 9 69 6 2 4 1 5 3 7 81 8 5 7 6 3 4 2 93 7 4 9 2 8 5 6 18 2 7 5 4 9 6 1 36 4 9 8 3 1 2 5 75 3 1 6 7 2 9 8 4