题解 | #Sudoku#

利用DFS的思维去解答，没有使用递归，使用的循环，通过empty和full两个列表存储已经填写的格子和没有填写的格子。代码如下：

class SudoKu:

    def __init__(self, sudo):
        self.sudo = sudo 
        self.empty = list(self.getEmptyCell())  # 存放空格子
        self.full = []      # 存放已经填写的格子

    def getEmptyCell(self):
        for i in range(9):
            for j in range(9):
                if self.sudo[i][j] == 0:
                    yield [(i, j), 0]

    def check(self, i, j, value):  # 检查在i,j格子内是否可以填入value
        if value in self.sudo[i]:
            return False 
        if value in [self.sudo[i][j] for i in range(9)]:
            return False 
        x, y = i // 3 * 3, j // 3 * 3 
        if value in [self.sudo[i][j] for i in range(x, x+3) for j in range(y, y+3)]:
            return False
        return True 

    def run(self):
        while self.empty:
            (x, y), v = self.empty.pop(0)
            for i in range(v+1, 10):  # 依次填入1~10的数字
                if self.check(x, y, i):
                    self.full.append([(x, y), i])
                    self.sudo[x][y] = i 
                    break 
            else:   # 如果没有填入任何数字，说明单元格不可填，那么将上一个单元格从full中回溯到empty
                self.empty.insert(0, [(x, y), 0])
                (x, y), v = self.full.pop()
                self.sudo[x][y] = 0   # 格子一定要重置，否则check函数检查会出问题
                self.empty.insert(0, [(x, y), v])
        self.show() 

    def show(self):
        for row in self.sudo:
            print(*row, sep=' ')

while True:
    try:
        data = [list(map(int, input().split())) for _ in range(9)]
        SudoKu(data).run()
    except EOFError: break