数独的解法

数独的规则

在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实现

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注