Java Reference
In-Depth Information
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
.
■