题目如下：
题目
Note
当我们拿着数独游戏时，我们是通过观感直觉来求解的。详细说来：
- 我们会去找那些规则下能够确定唯一解的空格，然后填入唯一解后再去寻找其他可以确定唯一解的空格。
- 如果找不到有唯一解，我们就找解空间比较小的空格，从解空间中挑一个填上去试试，如果可行继续尝试步骤1，2。如果不可行（有一些空格没有解），我们就把尝试的解从解空间中去掉，再挑其他解进行尝试。
我采用的解题思路如下，为了方便理解，代码有点长，但用断点跟一遍很容易懂，代码 beat 80%：
- 通过数独规则确定每行/ 每列/ 每3*3 box 的候选解空间，如果解空间都为空，代表数独解出，返回答案。反之，步骤2。
- 对于每个空格基于（1）中对应解空间的交集确定解空间，如果有空格解空间为空，返回错误。
- 找出那些有唯一解的空格，如果有填入，再重复步骤（递归）
- 如果没有唯一解的空格，挑选解空间最小的空格，挑选空间中的一个解填入，然后重复步骤（递归），如果返回错误，就将该解从解空间中删除，如果删除后解空间为空，返回错误。反之，再挑一个解填入，重复步骤（递归）。
算法参考流程图如下：
数独算法流程参考
参考代码如下：
class Solution:
def solver(self, board):
import copy
# get the candidates based on rule of row
cd_row = [["1", "2", "3", "4", "5", "6", "7", "8",
"9"], ["1", "2", "3", "4", "5", "6", "7", "8",
"9"], ["1", "2", "3", "4", "5", "6", "7", "8", "9"],
["1", "2", "3", "4", "5", "6", "7", "8",
"9"], ["1", "2", "3", "4", "5", "6", "7", "8",
"9"], ["1", "2", "3", "4", "5", "6", "7", "8", "9"],
["1", "2", "3", "4", "5", "6", "7", "8",
"9"], ["1", "2", "3", "4", "5", "6", "7", "8",
"9"], ["1", "2", "3", "4", "5", "6", "7", "8", "9"]]
i = 0
while i < 9:
for n in board[i]:
if n in cd_row[i]:
cd_row[i].remove(n)
i += 1
# Terminal condition
T = 0
for r in cd_row:
if len(r) == 0:
T = T + 1
if T == 9:
return board
# get the candidates based on rule of col
cd_col = [["1", "2", "3", "4", "5", "6", "7", "8",
"9"], ["1", "2", "3", "4", "5", "6", "7", "8",
"9"], ["1", "2", "3", "4", "5", "6", "7", "8", "9"],
["1", "2", "3", "4", "5", "6", "7", "8",
"9"], ["1", "2", "3", "4", "5", "6", "7", "8",
"9"], ["1", "2", "3", "4", "5", "6", "7", "8", "9"],
["1", "2", "3", "4", "5", "6", "7", "8",
"9"], ["1", "2", "3", "4", "5", "6", "7", "8",
"9"], ["1", "2", "3", "4", "5", "6", "7", "8", "9"]]
j = 0
while j < 9:
for row in board:
if row[j] in cd_col[j]:
cd_col[j].remove(row[j])
j += 1
# get candidates based on rule of 3*3 box
cd_box = [["1", "2", "3", "4", "5", "6", "7", "8",
"9"], ["1", "2", "3", "4", "5", "6", "7", "8",
"9"], ["1", "2", "3", "4", "5", "6", "7", "8", "9"],
["1", "2", "3", "4", "5", "6", "7", "8",
"9"], ["1", "2", "3", "4", "5", "6", "7", "8",
"9"], ["1", "2", "3", "4", "5", "6", "7", "8", "9"],
["1", "2", "3", "4", "5", "6", "7", "8",
"9"], ["1", "2", "3", "4", "5", "6", "7", "8",
"9"], ["1", "2", "3", "4", "5", "6", "7", "8", "9"]]
s = 0
b = 0
while s <= 6:
col = 0
while col <= 6:
for row in board[s:s + 3]:
for n in row[col:col + 3]:
if n in cd_box[b]:
cd_box[b].remove(n)
b += 1
col += 3
s += 3
min_cd = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]
p_x = 0 # solve point x-th row
p_y = 0 # solve point y-th col
cert = [] # point only has one candidate
a = 0
cd_board = []
while a < 9:
cd_b = []
b = 0
while b < 9:
if board[a][b] != ".":
cd_b.append(board[a][b])
else:
cd = [
c for c in cd_row[a] if c in cd_col[b]
and c in cd_box[(a // 3) * 3 + b // 3]
]
if len(cd) == 0:
cert = []
return "wrong"
elif len(cd) <= len(min_cd):
min_cd = cd
p_x = a
p_y = b
if len(cd) == 1:
cert.append([p_x, p_y])
cd_b.append(cd)
b += 1
cd_board.append(cd_b)
a += 1
# print(cd_board, cert)
if len(cert) > 0:
for p in cert:
temp = copy.deepcopy(board)
temp[p[0]][p[1]] = cd_board[p[0]][p[1]][0]
# print("board:", board)
res = self.solver(temp)
if res == "wrong":
return "wrong"
else:
return res
else:
trynum = min_cd[0]
temp = copy.deepcopy(board)
temp[p_x][p_y] = trynum
res = self.solver(temp)
while res == "wrong":
if len(min_cd) > 1:
min_cd.remove(trynum)
trynum = min_cd[0]
temp[p_x][p_y] = trynum
res = self.solver(temp)
else:
return "wrong"
return res
def solveSudoku(self, board):
res = self.solver(board)
i = 0
if res != "wrong":
while i < 9:
j = 0
while j < 9:
board[i][j] = res[i][j]
j = j + 1
i = i + 1
注意：
- 深拷贝和浅拷贝的问题。
- 要求直接对 board进行修改，不可以返回值。
源码地址：
https://github.com/jediL/LeetCodeByPython
其它题目：[leetcode题目答案讲解汇总（Python版 持续更新）]
(https://www.jianshu.com/p/60b5241ca28e)
ps：如果您有好的建议，欢迎交流 :-D，
也欢迎访问我的个人博客 苔原带 (www.tundrazone.com)
网友评论