Java Reference
In-Depth Information
7.7 Case Study: Sudoku
The problem is to check whether a given Sudoku solution is correct.
Key
Point
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 the novice, this section presents a solution to a simplified
version of the Sudoku problem, which is to verify whether a solution is correct. The complete
solution for solving the Sudoku problem is presented in Supplement VI.A.
Sudoku is a grid divided into smaller boxes (also called regions or blocks ), as
shown in Figure 7.4a. 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 the numbers 1 to 9 so that every row,
every column, and every
VideoNote
Sudoku
9
*
9
3
*
3
fixed cells
free cells
3
*
3
box contains the numbers 1 to 9 , as shown in Figure 7.4b.
53
7
53 46 7 8912
6 72 195 348
1 98 3425 6 7
8 597 6 142 3
4 26 8 5 3 79 1
7 139 2 485 6
9 6 1537284
287 419 63 5
3452 8 61 7
6
195
98
6
8
6
3
Solution
4
8
3
1
7
2
6
6
419
5
8
7
9
9
(a) Puzzle
(b) Solution
F IGURE 7.4
The Sudoku puzzle in (a) is solved in (b).
For convenience, we use value 0 to indicate a free cell, as shown in Figure 7.5a. The grid
can be naturally represented using a two-dimensional array, as shown in Figure 7.5b.
representing a grid
5300
7
0000
00
int [][] grid =
{{ 5 , 3 , 0 , 0 , 7 , 0 , 0 , 0 , 0 },
{ 6 , 0 , 0 , 1 , 9 , 5 , 0 , 0 , 0 },
{ 0 , 9 , 8 , 0 , 0 , 0 , 0 , 6 , 0 },
{ 8 , 0 , 0 , 0 , 6 , 0 , 0 , 0 , 3 },
{ 4 , 0 , 0 , 8 , 0 , 3 , 0 , 0 , 1 },
{ 7 , 0 , 0 , 0 , 2 , 0 , 0 , 0 , 6 },
{ 0 , 6 , 0 , 0 , 0 , 0 , 2 , 8 , 0 },
{ 0 , 0 , 0 , 4 , 1 , 9 , 0 , 0 , 5 },
{ 0 , 0 , 0 , 0 , 8 , 0 , 0 , 7 , 9 }
};
600
195
0
0
0
98
0
0
0
0
6
8
00
0
6
0
00
00
00
00
00
0
3
4
00
8
0
3
1
7
00
0
2
0
6
0
6
0
0
0
0
0
0
0
0
419
5
0
0
0
0
8
0
7
9
(a)
(b)
F IGURE 7.5
A grid can be represented using a two-dimensional array.
To find a solution for the puzzle, we must replace each 0 in the grid with an appropriate
number from 1 to 9 . For the solution to the puzzle in Figure 7.5, the grid should be as shown
in Figure 7.6.
Once a solution to a Sudoku puzzle is found, how do you verify that it is correct? Here are
two approaches:
Check 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 .
 
 
Search WWH ::




Custom Search