Java Reference
In-Depth Information
for
(
int
column =
0
; column <
9
; column++)
39
40
if
(column != j && grid[i][column] == grid[i][j])
check rows
41
return false
;
42
43
// Check whether grid[i][j] is valid in j's column
44
45
for
(
int
row =
0
; row <
9
; row++)
check columns
if
(row != i && grid[row][j] == grid[i][j])
46
return false
;
47
48
// Check whether grid[i][j] is valid in the 3-by-3 box
for
(
int
row = (i /
3
) *
3
; row < (i /
3
) *
3
+
3
; row++)
check small boxes
49
50
for
(
int
col = (j /
3
) *
3
; col < (j /
3
) *
3
+
3
; col++)
51
if
(row != i && col != j && grid[row][col] == grid[i][j])
52
return false
;
53
54
return true
;
// The current value at grid[i][j] is valid
55 }
56 }
Enter a Sudoku puzzle solution:
9 6 3 1 7 4 2 5 8
1 7 8 3 2 5 6 4 9
2 5 4 6 8 9 7 3 1
8 2 1 4 3 7 5 9 6
4 9 6 8 5 2 3 1 7
7 3 5 9 6 1 8 2 4
5 8 9 7 1 3 4 6 2
3 1 7 2 4 6 9 8 5
6 4 2 5 9 8 1 7 3
Valid solution
The program invokes the
readASolution()
method (line 6) to read a Sudoku solution
and return a two-dimensional array representing a Sudoku grid.
The
isValid(grid)
method checks whether the values in the grid are valid by verifying
that each value is between
1
and
9
and that each value is valid in the grid (lines 27-34).
The
isValid(i, j, grid)
method checks whether the value at
grid[i][j]
is valid.
It checks whether
grid[i][j]
appears more than once in row
i
(lines 39-41), in column
j
(lines 44-46), and in the box (lines 49-52).
How do you locate all the cells in the same box? For any
grid[i][j]
, the starting cell of
the
isValid
method
overloaded
isValid
method
*
3
3
*
3
3
box that contains it is
grid[(i / 3) * 3][(j / 3) * 3]
, as illustrated in
Figure 7.7.
grid[0][6]
grid[0][0]
For any grid[i][j] in this 3 by 3 box, its starting cell
is grid[3*(i/3)][3*(j/3)] (i.e., grid[0][6]). For
example, for grid[2][8], i=2 and j=8, 3*(i/3)=0 and
3*(j/3)=6.
grid[6][3]
For any grid[i][j] in this 3 by 3 box, its
starting cell is grid[3*(i/3)][3*(j/3)]
(i.e., grid[6][3]). For example, for
grid[8][5], i=8 and j=5, 3*(i/3)=6 and
3*(j/3)=3.
F
IGURE
7.7
The location of the first cell in a
3
*
3
box determines the locations of other cells in the box.
