The problem is to check whether a given Sudoku solution is correct.
This book teaches how to program using a wide variety of problems with various levels of difficulty. We use simple, short, and stimulating examples to introduce programming and problem-solving techniques and use interesting and challenging examples to motivate students. This section presents an interesting problem of a sort that appears in the newspaper every day. It is a number-placement puzzle, commonly known as Sudoku. This is a very challenging problem. To make it accessible to novices, this section presents a solution to a simplified version of the Sudoku problem, which is to verify whether a solution is correct. How to find a solution to the Sudoku problem is given in Supplement VI.A.
Sudoku is a 9 X 9 grid divided into smaller 3 X 3 boxes (also called regions or blocks), as shown in Figure 8.3a. Some cells, called fixed cells, are populated with numbers from 1 to 9. The objective is to fill the empty cells, also called free cells, with numbers 1 to 9 so that every row, every column, and every 3 X 3 box contains the numbers 1 to 9, as shown in Figure 8.3b.
For convenience, we use value 0 to indicate a free cell, as shown in Figure 8.4a. The grid can be naturally represented using a two-dimensional array, as shown in Figure 8.4b.
To find a solution for the puzzle is to replace 0 in the grid with appropriate numbers between 1 and 9. For the solution in Figure 8.3b, the grid should be as shown in Figure 8.5.
Suppose a solution to a Sudoku puzzle is found, how do you check if the solution is correct? Here are two approaches:
- One way to check it is to see if every row has numbers from 1 to 9, every column has numbers from 1 to 9, and every small box has numbers from 1 to 9.
- The other way is to check each cell. Each cell must be a number from 1 to 9 and the cell is unique on every row, every column, and every small box.
Listing 8.4 gives a program that prompts the user to enter a solution and program reports true if the solution is valid. We use the second approach in the program to check whether the solution is correct.
Listing 8.4 CheckSudokuSolution.cpp
1 #include <iostream>
2 using namespace std;
3
4 void readASolution(int grid[][9]);
5 bool isValid(const int grid[][9]);
6 bool isValid(int i, int j, const int grid[][9]);
7
8 int main()
9 {
10 // Read a Sudoku puzzle
11 int grid[9][9];
12 readASolution(grid);
13
14 cout << (isValid(grid) ? “Valid solution” : “Invalid solution”);
15
16 return 0;
17 }
18
19 // Read a Sudoku puzzle from the keyboard
20 void readASolution(int grid[][9])
21 {
22 cout << “Enter a Sudoku puzzle:” << endl;
23 for (int i = 0; i < 9; i++)
24 for (int j = 0; j < 9; j++)
25 cin >> grid[i][j];
26 }
27
28 // Check whether the fixed cells are valid in the grid
29 bool isValid(const int grid[][9])
30 {
31 for (int i = 0; i < 9; i++)
32 for (int j = 0; j < 9; j++)
33 if (grid[i][j] < 1 || grid[i][j] > 9 ||
34 !isValid(i, j, grid))
35 return false;
36
37 return true; // The fixed cells are valid
38 }
39
40 // Check whether grid[i][j] is valid in the grid
41 bool isValid(int i, int j, const int grid[][9])
42 {
43 // Check whether grid[i][j] is valid at the i’s row
44 for (int column = 0; column < 9; column++)
45 if (column != j && grid[i][column] == grid[i][j])
46 return false;
47
48 // Check whether grid[i][j] is valid at the j’s column
49 for (int row = 0; row < 9; row++)
50 if (row != i && grid[j] == grid[i][j])
51 return false;
52
53 // Check whether grid[i][j] is valid in the 3-by-3 box
54 for (int row = (i / 3) * 3; row < (i / 3) * 3 + 3; row++)
55 for (int col = (j / 3) * 3; col < (j / 3) * 3 + 3; col++)
56 if (row != i && col != j && grid
57 return false;
58
59 return true; // The current value at grid[i][j] is valid
60 }
The program invokes the readASolution(grid) function (line 12) to read a Sudoku solution into a two-dimensional array representing a Sudoku grid.
The isValid(grid) function checks whether the values in the grid are valid. It checks whether each value is between 1 and 9 and each value is valid in the grid (lines 31-35).
The isValid(i, j, grid) function checks whether the value at grid[i][j] is valid. It checks whether grid[i][j] appears more than once at row i (lines 44-46), at column j (lines 49-51), and in the 3 X 3 box (lines 54-57).
How do you locate all the cells in the same box? For any grid[i][j], the starting cell of the 3 X 3 box that contains it is grid[(i / 3) * 3][(j / 3) * 3], as illustrated in Figure 8.6.
With this observation, you can easily identify all the cells in the box. Suppose grid[r] [c] is the starting cell of a 3 * 3 box, the cells in the box can be traversed in a nested loop as follows:
// Get all cells in a 3 by 3 box starting at grid[r][c]
for (int row = r; row < r + 3; row++)
for (int col = c; col < c + 3; col++)
// grid
It is cumbersome to enter 81 numbers from the keyboard. You may store the input in a file, say CheckSudokuSolution.txt (see www.cs.armstrong.edu/liang/data/CheckSudokuSolution .txt), and compile and run the program using the following command:
g++ CheckSudokuSolution.cpp –o CheckSudokuSolution.exe
CheckSudokuSolution.exe < CheckSudokuSolution.txt
Source: Liang Y. Daniel (2013), Introduction to programming with C++, Pearson; 3rd edition.