Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
- Each of the digits
1-9 must occur exactly once in each row.
- Each of the digits
1-9 must occur exactly once in each column.
- Each of the the digits
1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
Empty cells are indicated by the character '.'.
A sudoku puzzle…
…and its solution numbers marked in red.
Note:
- The given board contain only digits
1-9 and the character '.'.
- You may assume that the given Sudoku puzzle will have a single unique solution.
- The given board size is always
9x9.
解法
填表格问题，深度优先搜索。只需要对每一个插入的新元素进行合法性判断即可，因为之前插入的数一定是合法的。注意在搜索失败时需将赋值的点还原为未赋值的状态，相当于回溯。
具体代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
class {
public void solveSudoku(char[][] board) {
if (board.length != 9 || board[0].length != 9) {
return;
}
dfs(board, 0, 0);
}
boolean dfs(char[][] board, int row, int col) {
if (row == 9) {
return true;
}
if (board[row][col] == '.') {
for (int i = 1; i <= 9; i++) {
board[row][col] = (char) ('0' + i);
if (isValid(board, row, col)) {
if (col == 8) {
if (dfs(board, row + 1, 0)) {
return true;
}
} else {
if (dfs(board, row, col + 1)) {
return true;
}
}
}
board[row][col] = '.';
}
return false;
} else {
if (col == 8) {
return dfs(board, row + 1, 0);
} else {
return dfs(board, row, col + 1);
}
}
}
boolean isValid(char[][] board, int row, int col) {
for (int i = 0; i < board.length; i++) {
if (board[i][col] == board[row][col] && i != row) {
return false;
}
}
for (int j = 0; j < board[0].length; j++) {
if (board[row][j] == board[row][col] && j != col) {
return false;
}
}
for (int i = row / 3 * 3; i < row / 3 * 3 + 3; i++) {
for (int j = col / 3 * 3; j < col / 3 * 3 + 3; j++) {
if (board[i][j] == board[row][col] && (i != row || j != col)) {
return false;
}
}
}
return true;
}
}
|
近期评论