数独的解法

数独的规则

在9×9的方格里面填写数字1-9，满足

• 每行不重复
• 每列不重复
• 9个3×3的小方格不重复

思路

回溯法

通过DFS遍历尝试每一个数字 根据三条规则，可以用三个二维数组记录每行，每列和每个小方格可填数字状态

row = [[True]*9 for _ in range(9)]
col = [[True]*9 for _ in range(9)]
block = [[True]*9 for _ in range(9)]

row[i][j]表示第i行是否可以填数字j col[i][j]表示第i列是否可以填数字j block[i][j]表示第i个方格是否可以填数字j

用二维数组g表示数独方格的原始状态，0表示空白

def dfs():
    # 遍历所有位置
    for i in range(9):
        for j in range(9):
            # 空白位置
            if g[i][j]==0:
                # 尝试每一个数字
                for k in range(9):
                    # 数字满足行，列，块
                    if row[i][k] and col[j][k] and block[3*(i//3)+j//3][k]:
                        # 填入数字
                        row[i][k] = col[j][k] = block[3*(i//3)+j//3][k]= False
                        g[i][j] = k+1
                        if(dfs()):
                            return True
                        # 有填错的，删除数字
                        row[i][k] = col[j][k] = block[3*(i//3)+j//3][k]= True
                        g[i][j] = 0
                # 九个数字都不能填
                return False
    # 所有位置都填了数字
    return True

回溯法要注意如何进行记录状态，要方便更新，回溯

参考资料

[1]数独求解算法（回溯法和唯一解法）java实现