-
Notifications
You must be signed in to change notification settings - Fork 44
/
_37_solveSudoku.java
131 lines (125 loc) · 4.33 KB
/
_37_solveSudoku.java
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
package pp.arithmetic.leetcode;
/**
* Created by wangpeng on 2019-05-15.
* 37. 解数独
*
* 编写一个程序,通过已填充的空格来解决数独问题。
*
* 一个数独的解法需遵循如下规则:
*
* 数字 1-9 在每一行只能出现一次。
* 数字 1-9 在每一列只能出现一次。
* 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
* 空白格用 '.' 表示。
*
* <image src="http://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Sudoku-by-L2G-20050714.svg/250px-Sudoku-by-L2G-20050714.svg.png"></image>
*
* 一个数独。
*
* <image src="http://upload.wikimedia.org/wikipedia/commons/thumb/3/31/Sudoku-by-L2G-20050714_solution.svg/250px-Sudoku-by-L2G-20050714_solution.svg.png"></image>
*
* 答案被标成红色。
*
* Note:
*
* 给定的数独序列只包含数字 1-9 和字符 '.' 。
* 你可以假设给定的数独只有唯一解。
* 给定数独永远是 9x9 形式的。
*
* @see <a href="https://leetcode-cn.com/problems/sudoku-solver/">sudoku-solver</a>
*/
public class _37_solveSudoku {
public static void main(String[] args) {
char[][] board = new char[][]{
{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
{'6', '.', '.', '1', '9', '5', '.', '.', '.'},
{'.', '9', '8', '.', '.', '.', '.', '6', '.'},
{'8', '.', '.', '.', '6', '.', '.', '.', '3'},
{'4', '.', '.', '8', '.', '3', '.', '.', '1'},
{'7', '.', '.', '.', '2', '.', '.', '.', '6'},
{'.', '6', '.', '.', '.', '.', '2', '8', '.'},
{'.', '.', '.', '4', '1', '9', '.', '.', '5'},
{'.', '.', '.', '.', '8', '.', '.', '7', '9'}
};
_37_solveSudoku solveSudoku = new _37_solveSudoku();
solveSudoku.solveSudoku(board);
print(board);
}
private static void print(char[][] board){
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}
}
/**
* 解题思路:
* 数独的解法就是通过填空,不断的试,可以考虑回溯算法解决
* 本题是他人解法,回溯挺绕的
*
* @param board
*/
public void solveSudoku(char[][] board) {
/**
* 记录某行,某位数字是否已经被摆放
*/
boolean[][] row = new boolean[9][10];
/**
* 记录某列,某位数字是否已经被摆放
*/
boolean[][] col = new boolean[9][10];
/**
* 记录某 3x3 宫格内,某位数字是否已经被摆放
*/
boolean[][] block = new boolean[9][10];
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') {
int num = board[i][j] - '0';
row[i][num] = true;
col[j][num] = true;
// blockIndex = i / 3 * 3 + j / 3,取整
block[i / 3 * 3 + j / 3][num] = true;
}
}
}
dfs(board, row, col, block, 0, 0);
}
private boolean dfs(char[][] board,
boolean[][] row,
boolean[][] col,
boolean[][] block,
int i, int j) {
// 找寻空位置
while (board[i][j] != '.') {
if (++j >= 9) {
i++;
j = 0;
}
if (i >= 9) {
return true;
}
}
for (int num = 1; num <= 9; num++) {
int blockIndex = i / 3 * 3 + j / 3;
if (!row[i][num] && !col[j][num] && !block[blockIndex][num]) {
// 递归
board[i][j] = (char) ('0' + num);
row[i][num] = true;
col[j][num] = true;
block[blockIndex][num] = true;
if (dfs(board, row, col, block, i, j)) {
return true;
} else {
// 回溯
row[i][num] = false;
col[j][num] = false;
block[blockIndex][num] = false;
board[i][j] = '.';
}
}
}
return false;
}
}