37. 解数独(Hard)
# 题目描述
编写一个程序,通过填充空格来解决数独问题。
一个数独的解法需遵循如下规则:
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
- 空白格用 '.' 表示。
# 样例
[["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"]]
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 题目解析
深度搜索 + 回溯法,和N皇后一样,就是不断修改数组的状态,检查是否符合规则。
本题只要找到一个答案即可,所以需要进行剪枝。
回溯剪枝的代码如下:
def backtracking(数组):
for (i, j) in (数组各个位置)
for (数字) in (0 - 9)
if backtracking(状态): # 剪枝
return True
return False # 数字遍历结束都无法找到
return True # 所有格子走完(填完)
1
2
3
4
5
6
7
2
3
4
5
6
7
虽然 N皇后 和 解数独 问题是回溯算法中的 Hard 难度的问题,难点部分主要是在 isValid
函数上。
但是从回溯问题来说,并没有前面的一些 递增子序列,分割回文串等难。
# Python示例
def backtracking(board):
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] != ".":
continue
for k in range(1, 10):
if isValid(i, j, str(k), board):
board[i][j] = str(k)
if backtracking(board):
return True
board[i][j] = '.'
return False
return True
def isValid(r, c, number, board):
# 条件1. 数字 1-9 在每一行只能出现一次
for i in range(9):
if board[r][i] == number:
return False
# 条件2. 数字 1-9 在每一列只能出现一次。
for i in range(9):
if board[i][c] == number:
return False
# 条件3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
start_row = 3 * (r // 3)
start_col = 3 * (c // 3)
for i in range(start_row, start_row + 3):
for j in range(start_col, start_col + 3):
if board[i][j] == number:
return False
return True
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
backtracking(board)
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
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
编辑 (opens new window)
上次更新: 2022/10/25, 02:40:54