题目
LeetCode.37.解数独（困难）
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。
题解
从左到右从上到下遍历所有没有填空的位置，尝试去填数字；填过的位置就跳过。
填过的数字就不能再用了，但是不知道填哪个数字，所以要尝试所有的可能性，采用暴力回溯解法。
填数字时要有三个限制条件，都是保证数字不重复，那么就要存储已访问过的数字，按行、按列、按3x3宫格分开记录和判断，这样最方便快速。
如果能按照限制条件填满一种可能性，就不用再尝试其他可能性了，直接结束程序。
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
| class Solution {
fun solveSudoku(board: Array<CharArray>) {
if (board.isEmpty()) return
val n = board.size
val rowUsed = Array(n) { BooleanArray(n + 1) { false } }
val columnUsed = Array(n) { BooleanArray(n + 1) { false } }
val boxUsed = Array(3) { Array(3) { BooleanArray(n + 1) { false } } }
for (i in 0 until n) {
for (j in 0 until n) {
if (board[i][j] in '1'..'9') {
val num = board[i][j] - '0'
rowUsed[i][num] = true
columnUsed[j][num] = true
boxUsed[i / 3][j / 3][num] = true
}
}
}
fun dfs(row: Int, column: Int): Boolean {
var r = row
var c = column
if (c == n) {
c = 0
r++
if (r == n) return true
}
if (board[r][c] == '.') {
for (i in 1..9) {
if (rowUsed[r][i] || columnUsed[c][i] || boxUsed[r / 3][c / 3][i]) continue
board[r][c] = i.toString()[0]
rowUsed[r][i] = true
columnUsed[c][i] = true
boxUsed[r / 3][c / 3][i] = true
if (dfs(r, c + 1)) {
return true
}
board[r][c] = '.'
rowUsed[r][i] = false
columnUsed[c][i] = false
boxUsed[r / 3][c / 3][i] = false
}
return false
} else {
return dfs(r, c + 1)
}
}
dfs(0, 0)
}
}
|