问题37：编写一个程序，通过已填充的空格来解决数独问题。数独解法需遵循如下规则：
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的3x3宫内只能出现一次。
注意：
- 给定的数独序列只包含数字1-9和字符 '.' 。
- 你可以假设给定的数独只有唯一解。
- 给定数独永远是9x9形式的。
来源：力扣（LeetCode）
链接：https://leetcode.com/problems/sudoku-solver
board的图形化结构
本例的唯一答案
第一步，我们要处理给定的数独，把已有数的格的值与位置记录下来。方法与上一篇文章类似。不同的是，我们定义一个状态列表，其中子列表[i][j]代表第i行第j列元素的状态。对于原本就有数字的格，状态记为1；对于原本没有数字的格，状态记为0。
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
box = [[[] for _ in range(3)] for _ in range(3)]
col = [[] for _ in range(9)]
r = [[] for _ in range(9)]
state = [[[] for _ in range(9)] for _ in range(9)]
for i, row in enumerate(board):
for j, val in enumerate(row):
if val != '.':
state[i][j] = 1 #把原本有数字的格，状态记为1
elif val == '.':
state[i][j] = 0 #把原本无数字的格，状态记为0
continue
r[i].append(val)
col[j].append(val)
box[i//3][j//3].append(val)
第二步，我们定义两个函数，分别用于定位数独中某个格的前一格和后一格。
def previndex(i, j): #寻找数独中前一个索引
if j == 0:
i -= 1
j = 8
else:
j -= 1
return i, j
def nextindex(i, j): #寻找数独中后一个索引
if j == 8:
i += 1
j = 0
else:
j += 1
return i, j
第三步，使用回溯法不断进行尝试，如果到某个地方失败了，就向前回溯，再重新尝试，直到数独最后一个格为止。
ij_cache = [[[] for _ in range(9)] for _ in range(9)] #这个ij缓存用于记录位置ij已经尝试过的数
def ijattempt(i, j, fail):
if fail == 1: #如果位置ij已经尝试了9个数并失败了
ij_cache[i][j] = [] #清空该位置缓存
m, n = previndex(i, j) #寻找上一个状态为0的格
while state[m][n] == 1:
m, n = previndex(m, n)
i, j = m, n
r[i].remove(board[i][j]) #从行i缓存中移除该数
col[j].remove(board[i][j]) #从列j缓存中移除该数
box[i//3][j//3].remove(board[i][j]) #从九宫格中移除该数
board[i][j] = '.' #将本格置为空
ijattempt(i, j, 0) #回溯，重新尝试ij之前一个状态为0的格
elif state[i][j] == 1: #如果该格状态是1
if i == j == 8:
return
i, j = nextindex(i, j)
ijattempt(i, j, 0) #尝试下一格
else: #如果格中没有数，且还有尝试机会
success = 0 #设定一个成功参数，初始为0
for c in range(1, 10):
c = str(c)
if c not in ij_cache[i][j]: #将尝试过的数记录在缓存中
ij_cache[i][j].append(c)
else:
continue
if c not in r[i] and c not in col[j] and c not in box[i//3][j//3]:
#如果新尝试的数c不在行、列和九宫格缓存中
board[i][j] = c #本格的值记为c
r[i].append(c) #将c写入行缓存
col[j].append(c) #将c写入列缓存
box[i//3][j//3].append(c) #将c写入九宫格缓存
success = 1 #成功参数置1
break
if success == 1: #如果成功了，尝试下一格
if i == j == 8:
return
i, j = nextindex(i, j)
ijattempt(i, j, 0)
else: #如果失败了，重新尝试上一格
if j == 0 and i == 0: #此时，上一个的格缓存还在，并没有清零
return -1 #仅仅是把失败格的缓存清零了
else:
ijattempt(i, j, 1)
ijattempt(0, 0, 0)
完整代码如下：
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
box = [[[] for _ in range(3)] for _ in range(3)]
col = [[] for _ in range(9)]
r = [[] for _ in range(9)]
state = [[[] for _ in range(9)] for _ in range(9)]
for i, row in enumerate(board):
for j, val in enumerate(row):
if val != '.':
state[i][j] = 1
elif val == '.':
state[i][j] = 0
continue
r[i].append(val)
col[j].append(val)
box[i//3][j//3].append(val)
def nextindex(i, j):
if j == 8:
i += 1
j = 0
else:
j += 1
return i, j
def previndex(i, j):
if j == 0:
i -= 1
j = 8
else:
j -= 1
return i, j
ij_cache = [[[] for _ in range(9)] for _ in range(9)]
def ijattempt(i, j, ok):
if len(ij_cache[i][j]) == 9 and ok == 1:
ij_cache[i][j] = []
m, n = previndex(i, j)
while state[m][n] == 1:
m, n = previndex(m, n)
i, j = m, n
r[i].remove(board[i][j])
col[j].remove(board[i][j])
box[i//3][j//3].remove(board[i][j])
board[i][j] = '.'
ijattempt(i, j, 0)
elif board[i][j] != '.':
if i == j == 8:
return
i, j = nextindex(i, j)
ijattempt(i, j, 0)
else:
success = 0
for c in range(1, 10):
c = str(c)
if c not in ij_cache[i][j]:
ij_cache[i][j].append(c)
else:
continue
if c not in r[i] and c not in col[j] and c not in box[i//3][j//3]:
board[i][j] = c
r[i].append(c)
col[j].append(c)
box[i//3][j//3].append(c)
success = 1
break
if success == 1:
if i == j == 8:
return
i, j = nextindex(i, j)
ijattempt(i, j, 0)
else:
if j == 0 and i == 0:
return -1
else:
ijattempt(i, j, 1)
ijattempt(0, 0, 0)
运行结果：
[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
速度可以，占用内存微大
