题目：
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
1.Each of the digits 1-9 must occur exactly once in each row.
2.Each of the digits 1-9 must occur exactly once in each column.
3.Each of the digits 1-9 must occur exactly once in each of the 9 3×3 sub-boxes of the grid.
The ‘.’ character indicates empty cells.
Example 1:
Input: board = [[“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”]]
Output: [[“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”]]
Explanation: The input board is shown above and the only valid solution is shown below:
我的思路：
这道题其实就是写一个解数独的代码，但是我觉得是我刷leedcode以来遇到的最难的一题，花了我很久的时间（实际上95%的时间都在研究数独的高级解法，然而太抽象了，还是没能理解，并且高级解法的代码实现会非常复杂），因为首先要学会解数独，才能解决这道题。
我的代码采用的是主要是摒除法
cal()
，即数独某个空格的可能值用一个list来表示，这个list中的可能数字为[‘1’,‘2’,‘3’,‘4’,‘5’,‘6’,‘7’,‘8’,‘9’]去掉所在行已经确定的值，所在列已经确定的值，和所在宫（3X3）已经确定的值，空格list的生成由
function cal1()
表示，
board[i][j] = cal1(i,j)
，假如list中只包含一个值，那么这个空格的值就可以是确定的，可以直接返回该值，并且此时由于确定的值多了一个，可以对前面生成的list进行简化，所以从头开始运行一次
cal()
，
if type(board[i][j]) == str: return cal()
；每一行，每一列，每一宫算完之后，整合所有的list，在这些list中，如果一个值只出现在一个list中，那该list可以简化为该值，每当多一个确定的值，从头开始运行一次
cal()
。
到此，大部分的简单难度的数独都是可以解出来的，复杂数独此时也被简化到最简值，后面可以直接采用暴力试错法，直接对空格的list进行遍历，通过
function valid()
判断答案是否有效，当出现有效答案时，可以直接结束循环，获得正确答案。
由于这一题提交的是原始数独的链接，而不是return的值，所以最后一部分的代码用了两个for循环来复制数独，在leedcode中，为了体现题目所蕴含的算法，我一般不采用较为方便和复杂的内置方法来解题，并且做完的时候真的不想回头再优化代码，所以我的答案一般都会有点啰嗦，但是运行速度和占用的内存还算满意。
Runtime: 96 ms, faster than 91.85% of Python3 online submissions for Sudoku Solver.
Memory Usage: 14.3 MB, less than 72.29% of Python3 online submissions for Sudoku Solver.
我的解答：
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
def cal1(x,y):
n1 = ['1','2','3','4','5','6','7','8','9']
x1 = 3 * (x//3)
y1 = 3 * (y//3)
b2 = [board[x1][y1], board[x1 +1][y1], board[x1 +2][y1], board[x1][y1 +1], board[x1 +1][y1 +1], board[x1 +2][y1 +1], board[x1][y1 +2], board[x1 +1][y1 +2], board[x1 +2][y1 +2]]
for i in range(9):
if board[x][i] != '.' and type(board[x][i]) == str:
if board[x][i] in n1:
n1.remove(board[x][i])
if board[i][y] != '.' and type(board[i][y]) == str:
if board[i][y] in n1:
n1.remove(board[i][y])
for j in b2:
if j != '.' and type(j) == str:
if j in n1:
n1.remove(j)
if len(n1) == 1:
return n1[0]
else:
return n1
def cal():
for i in range(9):
a = []
for j in range(9):
b = []
c = []
if board[i][j] == '.' or type(board[i][j]) == list:
board[i][j] = cal1(i,j)
if type(board[i][j]) == str:
return cal()
# while turn to the bottom and right side of 3x3, recalculate the lists of the 3X3
if i%3 == 2 and j%3 == 2:
for i1 in range(9):
x2 = 3*(i//3)
y2 = 3*(j//3)
if type(board[x2+i1//3][y2+i1%3]) == list:
b += board[x2+i1//3][y2+i1%3]
for i2 in range(9):
if type(board[x2+i2//3][y2+i2%3]) == list:
for m2 in board[x2+i2//3][y2+i2%3]:
b2 = b[:]
b2.remove(m2)
if m2 not in b2:
board[x2+i2//3][y2+i2%3] = m2
return cal()
# while turn to the bottom side, recalculate the lists of the column
if i == 8:
for j1 in range(9):
if type(board[j1][j]) == list:
c += board[j1][j]
for j2 in range(9):
if type(board[j2][j]) == list:
for m3 in board[j2][j]:
c2 = c[:]
c2.remove(m3)
if m3 not in c2:
board[j2][j] = m3
return cal()
# while turn to the right side, recalculate the lists of the line
for k in range(9):
if type(board[i][k]) == list:
a += board[i][k]
for l in range(9):
if type(board[i][l]) == list:
for m in board[i][l]:
a2 = a[:]
a2.remove(m)
if m not in a2:
board[i][l] = m
return cal()
def valid():
for i in range(9):
for j in range(9):
if type(board[i][j]) == list:
return False
return True
cal()
b2 = copy.deepcopy(board)
v = False
for nu1 in range(9):
for nu2 in range(9):
if type(b2[nu1][nu2]) == list:
for nu3 in b2[nu1][nu2]:
for i in range(9):
for j in range(9):
board[i][j] = b2[i][j]
board[nu1][nu2] = nu3
cal()
if valid():
v = True
break
if v:
break
if v:
break