启发式方法求解数独

题目

• sukudo棋盘是一种逻辑游戏，由9*9的网格组成。玩法要求每一行、每一列、每个3*3的子网格都由1~9九个数字填充，并且每行每列每个子网格填充的数字都不重复。
• 现给定一个9*9的二维数组，求满足条件的填充算法。

思路

• 类似八皇后算法，这种题可以使用启发式搜索，即从1~9找出一个满足条件的数字，然后下一步，如果找不到则意味上一步数字不合适，于是退回上一步，重新选取合适数字。如果还是不行，则继续回退。这种走入死胡同就回退寻找新出路的方式就是启发式搜索。

分析

• 启发式搜索是一种暴力枚举法，把所有可能的方式都尝试一遍。时间复杂度是$O(9^9)$。

代码

class Sukudo:
    def __init__(self,puzzle):
        self.puzzle = puzzle
        self.sukudoBoard = puzzle
    def printSukudoBoard(self):
        for i in range(9):
            for j in range(9):
                print('{}'.format(self.sukudoBoard[i][j]), end="  ")
            print()
    def checkValid(self, i, j, val):
        for k in range(9):
            if k != j and self.sukudoBoard[i][k] == val: # 检测行是否重复
                return False
            if k != i and self.sukudoBoard[k][j] == val: # 检测列是否重复
                return False
        subX = int(i / 3) * 3
        subY = int(j / 3) * 3
        for p in range(subX, subX + 3):  # 检测网格是否重复
            for q in range(subY, subY + 3):
                if p != i and q != j and self.sukudoBoard[p][q] == val:
                    return False
        return True
    def setSukudoBoard(self, x, y):
        if y > 8:
            y = 0
            x += 1
        if x > 8:
            return True
        if self.puzzle[x][y] != 0:  # 判断是否是谜题，谜题不需要尝试填充数字，直接用谜题val就可以
            if self.setSukudoBoard(x, y + 1):
                return True
            else:
                self.sukudoBoard[x][y] = self.puzzle[x][y]
                return False
        for val in range(1, 10):  # 从给定位置从1~9开始填充
            if self.checkValid(x, y, val) is True: # 满足条件进行下一个网格
                self.sukudoBoard[x][y] = val
                if self.setSukudoBoard(x, y + 1): # 下一个网格满足则返回true，不满足重新设置val
                    return True
        self.sukudoBoard[x][y] = 0 # 不满足则该网格至0，返回false，上一步重新填充数字
        return False
if __name__ == '__main__':
    puzzle = '''
    000600000
    006730590
    083010700
    040107003
    000300900
    900008000
    000000001
    009000006
    700801040
    '''
    puzzle = [ [int(l) for l in k] for k in [list(j) for j in [i.strip() for i in puzzle.split("\n") if i.strip()]]]
    s = Sukudo(puzzle)
    if s.setSukudoBoard(0,0):
        s.printSukudoBoard()
    else:
        print("该数独无解")