leetcode-------解数独(回溯法)
如：
方法：回溯法：
回溯法的思想就是：对于一个问题有多个选择方式，先选择一个方式执行下去，若在执行过程中，发现不符合规则，则回退，回到选择方式的步骤，进而选择其他方式，继续试。
重要：对于回溯法，一定会有个[规则]，这个[规则]将会决定是否回退，所以当我们在使用回溯法时，一定要留意能否构建[规则]。
如这一题，在数独中，规则就是：
1. 在同一列和同一行中，不能出现一样的数字。
2. 在同一个九宫格中，也不难出现同样的数字。
所以我们需要用代码构建规则：
def ok(self,board,i:int,j:int,x:str) -> bool:
for t in range(9):
if board[t][j] == x:return False #(i，j)的同一列中是否已经出现x
if board[i][t] == x:return False #(i，j)的同一行中是否已经出现x
if board[i//3* 3 + t//3][j//3*3 + t%3] == x: return False #(i，j)的同一个九宫格中是否已经出现x
return True
然后我们进入进一步的讨论：
在回溯法中，我们需要构造一个[链式标签](这是我的说法)，意思是：当当前有多种方式可以选择时，我们随机选一种，但并不清楚这种方式是否选得正确，所以当前状态的正确性是由接下去的步骤决定的，若在下面的步骤中，发现与现在的规则不相符，则表明上一步的选择是False的，所以回退到上一步骤，选择其他方式。 要想获得True，只有一种可能，就是程序能顺利执行到结束，所有的选择都与规则相符，才会返回True。否则中间只要有一步错了，就会返回False，一返回False就要回退重新选择。
那如果实现这种方式呢？答案是用递归。代码如下：
代码：
class Solution:
def solveSudoku(self, board) -> None:
self.sudoke(board,0,0)
def sudoke(self,board,i:int,j:int):
if j<=8: #若列没有越界
if board[i][j] != ".": #当前位置若不为空，不需要填入数字，直接去下一个位置
if i<8: #若未到最后一行，则到下一行的位置
if(self.sudoke(board,i+1,j)):return True
else: #若已经是最后一行，则到下一列的起始位置
if(self.sudoke(board,0,j+1)):return True
return False
else: #当前位置为空，需要填入数字
for x in range(1,10): #从1-9选数字填入空格
if not self.ok(board,i,j,str(x)):continue
board[i][j] = str(x)
if i bool:
for t in range(9):
if board[t][j] == x:return False #(i，j)的同一列中是否已经出现x
if board[i][t] == x:return False #(i，j)的同一行中是否已经出现x
if board[i//3* 3 + t//3][j//3*3 + t%3] == x: return False #(i，j)的同一个九宫格中是否已经出现x
return True #若x符合填入条件，返回True。否则返回False
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']]
s = Solution()
s.solveSudoku(board)
for x in board:
print(x)
运行效果：
ZJE_ANDY
原创文章 286获赞 493访问量 86万+
关注
他的留言板
展开阅读全文
作者：ZJE_ANDY
