[LeetCode]37. 解数独(Sudoku Solver)

题目描述

编写一个程序,通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则:

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 ‘.’ 表示。

一个数独。

答案被标成红色。

Note:

  • 给定的数独序列只包含数字 1-9 和字符 ‘.’ 。
  • 你可以假设给定的数独只有唯一解。
  • 给定数独永远是 9x9 形式的。

解题思路

回溯法。从左上角第一个位置开始遍历,遇到空的位置时,从 1-9 放入可以放入的数字,递归的放置下一个数字,若当前位置不可放入任意数字,则回溯到上一个位置修改放入的数字。若已经递归到最后一个位置,说明找到了数独的解。
注:回溯到上一个位置修改数字的时候需要把原来的放置复原。

代码

Python 3.6

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
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
# init hashmap
rows, cols = len(board), len(board[0])
keys = range(1, 10)
boxes_hash = [dict.fromkeys(keys, 0) for _ in range(rows * cols)]
rows_hash = [dict.fromkeys(keys, 0) for _ in range(rows)]
cols_hash = [dict.fromkeys(keys, 0) for _ in range(cols)]
get_box_idx = lambda i, j: (i // 3) * 3 + j // 3

def could_place(num, row, col):
# 当前位置是否能放 num
return not (rows_hash[row][num] > 0 or cols_hash[col][num] > 0 or boxes_hash[get_box_idx(row, col)][num] > 0)

def place(num, row, col):
# 给当前位置放置 num
rows_hash[row][num] += 1
cols_hash[col][num] += 1
boxes_hash[get_box_idx(row, col)][num] += 1
board[row][col] = str(num)

def remove(num, row, col):
# 从当前位置移走 num
rows_hash[row][num] = 0
cols_hash[col][num] = 0
boxes_hash[get_box_idx(row, col)][num] = 0
board[row][col] = "."

def place_next(row, col):
# 放置当前位置的下一个位置
if row == rows - 1 and col == cols - 1:
# 若当前位置为最后一个位置,则说明找到了数独的解
nonlocal solved
solved = True
else:
# 递归地回溯下一个位置
if col == cols - 1:
backtrack(row + 1, 0)
else:
backtrack(row, col + 1)

def backtrack(row=0, col=0):
# 回溯
if board[row][col] == ".":
for num in range(1, 10):
if could_place(num, row, col):
# 如果当前位置可以放置,则放当前位置以及后面的位置
# 如果当前位置不能放置,那么该处回溯会结束,solved 没有变,仍然为 False
# 会回溯到上一个修改,放置下一个值...
place(num, row, col)
place_next(row, col)
if not solved:
# 当前位置回溯返回后 solved 仍未 False 时说明需要修改当前位置的值
remove(num, row, col)
else:
# 当前位置不可放置时,放置下一个位置
place_next(row, col)

# 先把 hashmap 填充为初始值
for i in range(rows):
for j in range(cols):
if board[i][j] != ".":
place(int(board[i][j]), i, j)
solved = False
backtrack()

执行用时 : 336 ms
内存消耗 : 14 MB

参考

https://leetcode-cn.com/problems/sudoku-solver/solution/jie-shu-du-by-leetcode/