解数独
1.解法
这道题是一个棋盘问题，而棋盘问题是一个典型的回溯问题。
首先思考普通人（这里指没有受过专业训练的人）解数独的方法，那就是首先在空白位置假设一个数字，然后在这个假设的基础上去填别的数，如果发现到最后无法填满，则证明假设不成立，然后换一个数继续假设。
上面的思想非常符合回溯的思想，画成图如下所示：
所以我们现在可以进行回溯三部曲：
-
确定函数头
首先思考函数的参数，因为一般的回溯都是通过每次修改参数（比如让参数+1等等），然后再进行操作，但这道题比较特殊，我们来看上图中取1的例子，我们确定取1的位置是通过从头（即row=0，col=0）遍历行和列的方式来确定在空白处取1，取完1后，再进行下一次操作时，发现我们还是要从头遍历行和列才能确定下一个空白的位置，因此这里的参数为空， 即不需要任何参数，因为每一次的操作都是从头开始，不需要在上一层递归的基础上确定某些参数。
有些人可能会问：第二次找空白值的时候，不是可以从上一次递归的列（col）+1开始吗？这样我们的参数就可以加上col了。
答：因为下一次找空白值的时候有可能是在下一列，也有可能在下一行，我们还要写一些if语句来进行逻辑判断，然后确定下一层递归时参数是row+1，还是col+1，因此不如每一次都从头开始遍历，这样代码会简洁一些，并且不会影响时间复杂度。
def backtracking(): -
确定递归出口：
递归出口是所有的空都被填完了的时候，那么什么时候就可以知道所有的空都填完了呢，即row==len(board)。
if row == len(board): return但是这里有一个问题，就是函数头是没有row参数的，我们写这个出口会出问题，这里可以先看下面，下面会给出解释。
-
确定逻辑部分：
逻辑部分就是每次从头遍历行和列，找到下一个空白的位置，然后从1到9逐次填入空白位置，然后进行下一层的递归，只要找到一个合法答案，就可以退出整个程序了（因为数独只有一个答案）
for row in range(len(board)): # 遍历行 for col in range(len(board[0])): # 遍历列 if board[row][col]!='.': # 找到下一个空白位置 continue for i in range(1,10): # 给空白位置填上数字 if isValid(row,col,str(i),board): # 如果该数字合法，即没有相同数字在同行，同列，同宫 board[row][col] = str(i) # 填上 if backtracking(): # 递归 return True # 这里的return True是给一个信号，证明找到答案了 board[row][col] = '.' # 回溯 return False # 如果执行到这里了，证明[1,9]都没有return True（即该空白位置填[1,9]都不成立），那么就不存在答案了，就可以回溯了 return True # 此时row==len(board)，即填满了棋盘这里其实已经涵盖了上面的递归出口，即最后一行return True，因为如果能执行到最后一行，证明row和col都遍历完最后一个位置了，因此直接return True即可，就不用上面的判断了。
-
判断数字是否合法：
def isValid(row,col,i,board): # 检查行 for c in range(len(board[0])): if board[row][c]==i: return False # 检查列 for r in range(len(board)): if board[r][col]==i: return False # 检查宫 rstart = (row // 3) * 3 cstart = (col // 3) * 3 for r in range(rstart,rstart+3): for c in range(cstart,cstart+3): if board[r][c]==i: return False return True这里检查是否同列和同行很容易，只要用循环判断同行同列是否存在重复数字即可。难点在于如何判断同宫。
给定一个位置[row][col]，想判断同宫里面是否有相同数字需要如下步骤：
- 首先给定一个位置[row,col]，需要它所在的宫
- 知道了它所在的宫，再找到该宫的比较有代表性的位置（比如第一位，最后一位，最中间一位，这里的代表性指的是确定了这个位置，那么该宫的其他位置也都能确定）
首先画出图：
1.首先找到位置[row,col]和宫的联系：
我们先从左到右，从上到下给每个宫按行和列编号（蓝色字体），发现如果每个位置的（row//3）就是对应的宫的行数，（col//3）就是对应的宫的列数。
2.然后找到宫和有代表性位置的联系：
发现如果宫按照行和列编号，那么行和列都*3，就变成了该宫的第一个元素的位置
所以代码中写到，rstart = (row // 3) * 3，cstart = (col // 3) * 3，找到了第一个位置，我们只要遍历行和列后+3的范围内的元素中是否有相同元素即可。
整体代码：
def solveSudoku(board):
def backtracking():
for row in range(len(board)):
for col in range(len(board[0])):
if board[row][col]!='.':
continue
for i in range(1,10):
if isValid(row,col,str(i),board):
board[row][col] = str(i)
if backtracking():
return True
board[row][col] = '.'
return False
return True # 此时row==len(board)，即填满了棋盘
def isValid(row,col,i,board):
# 检查行
for c in range(9):
if board[row][c]==i:
return False
# 检查列
for r in range(9):
if board[r][col]==i:
return False
# 检查宫
rstart = (row // 3) * 3
cstart = (col // 3) * 3
for r in range(rstart,rstart+3):
for c in range(cstart,cstart+3):
if board[r][c]==i:
return False
return True
backtracking()
2.总结
python
string 转 int ： i = int(s)
int 转 string ： s = str(i)
算法
回溯算法中确定参数的方法：
找到递归时需要在上一层递归的基础上进行操作的参数。
例如：行，列等等
def backtracking(row)
backtracking(row+1)