GuilinDev
Lc0037
05 August 2008
37 Sudoku Solver
原题概述
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
1-9
- Each of the digits
1
1-9
- Each of the the digits
1
1-9
1
3x3
Empty cells are indicated by the character 1
'.'
A sudoku puzzle…
…and its solution numbers marked in red.
Note:
- The given board contain only digits
1
1-9
1
'.'
- You may assume that the given Sudoku puzzle will have a single unique solution.
- The given board size is always
1
9x9
题意和分析
这道题要求把数独解出来，是回溯法backtracking的应用。关于回溯法，参考了discuss区的讨论，并在在网上看到这样的总结：
1 每个backtracking的题目，最好都有独立判断isValid的程序，这样架构清楚。同时，valid判断函数在这里可以稍微研究一下。只要当前要判断的位置上的数值和本行没有重复，本列没有重复，cube没有重复就是valid。一旦有重复就立即返回，减少判断次数。
2 backtracking的递归函数，通常要有返回值呢。因为要判断递归的方案正确与否，所以这里的递归一定是有返回值的（除非是combination那种没有正确错误概念的backtracking）。
3 可以考虑“先放置，再判断”的方案。比如这里，首先判断当前位置是否为空，如果为空，那么放置一个元素，检查它是否正确。如果正确，就继续进行下面的递归（也就是第29行 isValid&&solveSudoku的作用）。当函数返回错误之后，将刚刚的数值变为空，再进行下一次尝试即可。
4 所有的方案（k从1到9）完毕之后，应该返回错误，这个是不应该被忽略的。
5 最后一点需要注意的是，当i,j循环完毕之后，第27行应该返回true。这里实际上是最终/最底层的一次循环，表明已经解出了sudoku，返回true！切记切记，最终情况！
代码
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
class Solution {
public void solveSudoku(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) {
return;
}
solve(board);
}
private boolean solve(char[][] board) {
for (int i =0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == '.') {//针对空的位置
for (char c = '1'; c <= '9'; c++) {//从1到9开始试，只要valid就保留
if (isValid(board, i, j, c)) {//传入当前board，行，列和准备加入的数字看是否有效
board[i][j] = c;//如果so far是有效的，将数字放入当前cell
if (solve(board)) {//递归调用，注意backtracking的递归是有返回值的
return true;
} else {//回溯过程中发现无效，就让当前cell重新变成default
board[i][j] = '.';
}
}
}
return false;//中间某一条路走不通
}
}
}
return true;//这是回溯法里面递归的返回值,最后一层/一次递归
}
//判断新加的数字是否有效，返回值为boolean
private boolean isValid(char[][] board, int row, int col, char c) {
for (int i =0; i < 9; i++) {
//检查行
if (board[i][col] != '.' && board[i][col] == c) {
return false;
}
//检查列
if (board[row][i] != '.' && board[row][i] == c) {
return false;
}
//检查cube
int rowIndex = 3 * (row / 3);
int colIndex = 3 * (col / 3);
if (board[rowIndex + i / 3][colIndex + i % 3] != '.' && board[rowIndex + i / 3][colIndex + i % 3] == c) {
return false;
}
}
return true;
}
}
DFS + 剪枝
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
class Solution {
public void solveSudoku(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) {
return;
}
backtrack(board, 0, 0);
}
private boolean backtrack(char[][] board, int i, int j) {
int m = 9, n = 9;
if (j == n) {
// 穷举到最后一列的话就换到下一行重新开始。
return backtrack(board, i + 1, 0);
}
if (i == m) {
// 找到一个可行解，触发 base case
return true;
}
if (board[i][j] != '.') {
// 如果有预设数字，不用我们穷举
return backtrack(board, i, j + 1);
}
for (char ch = '1'; ch <= '9'; ch++) {
// 如果遇到不合法的数字，就跳过
if (!isValid(board, i, j, ch))
continue;
board[i][j] = ch;
// 如果找到一个可行解，立即结束
if (backtrack(board, i, j + 1)) {
return true;
}
board[i][j] = '.';
}
// 穷举完 1~9，依然没有找到可行解，此路不通
return false;
}
private boolean isValid(char[][] board, int r, int c, char n) {
for (int i = 0; i < 9; i++) {
// 判断行是否存在重复
if (board[r][i] == n) return false;
// 判断列是否存在重复
if (board[i][c] == n) return false;
// 判断 3 x 3 方框是否存在重复
if (board[(r/3)*3 + i/3][(c/3)*3 + i%3] == n)
return false;
}
return true;
}
}
用三个数据结构来记录行列和小框
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
class Solution {
public boolean isValidSudoku(char[][] board) {
// init data
HashMap<Integer, Integer> [] rows = new HashMap[9];
HashMap<Integer, Integer> [] columns = new HashMap[9];
HashMap<Integer, Integer> [] boxes = new HashMap[9];
for (int i = 0; i < 9; i++) {
rows[i] = new HashMap<Integer, Integer>();
columns[i] = new HashMap<Integer, Integer>();
boxes[i] = new HashMap<Integer, Integer>();
}
// validate a board
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
char num = board[i][j];
if (num != '.') {
int n = (int)num;
int box_index = (i / 3 ) * 3 + j / 3;
// keep the current cell value
rows[i].put(n, rows[i].getOrDefault(n, 0) + 1);
columns[j].put(n, columns[j].getOrDefault(n, 0) + 1);
boxes[box_index].put(n, boxes[box_index].getOrDefault(n, 0) + 1);
// check if this value has been already seen before
if (rows[i].get(n) > 1 || columns[j].get(n) > 1 || boxes[box_index].get(n) > 1)
return false;
}
}
}
return true;
}
}