回溯数独求解器总是 returns 初始板

Question

像许多初学者一样，我正在尝试这个简单的项目，但我的算法最终 returns 我开始使用的初始板，这意味着没有可行的解决方案，虽然有一段时间它似乎进展得很好。我知道我正在为它提供一个有效且可解决的数独板。我似乎无法弄清楚我的错误，非常感谢任何意见和批评！

test_sudoku = [[5,3,0,0,7,0,0,0,0],
          [6,0,0,1,9,5,0,0,0],
          [0,9,8,0,0,0,0,6,0],
          [8,0,0,0,6,0,0,0,3],
          [4,0,0,8,0,3,0,0,1],
          [7,0,0,0,2,0,0,0,6],
          [0,6,0,0,0,0,2,8,0],
          [0,0,0,4,1,9,0,0,5],
          [0,0,0,0,8,0,0,7,9]]

class Solver:
    def __init__(self, grid):
        self.grid = grid

    def check_validity(self, i, j, n):
        if n in self.grid[i]:
            return False

        for row in self.grid:
            if n == row[j]:
                return False

        if i <= 2:
            i = 0
        elif i > 2 and i <= 5:
            i = 3
        else:
            i = 6

        if j <= 2:
            j = 0
        elif j > 2 and j <= 5:
            j = 3
        else:
            j = 6

        box = []
        for row in range(i+3):
            box+= self.grid[row][j:j+3]

        if n in box:
            return False

        return True

    def is_empty(self, i, j):
        if self.grid[i][j] == 0:
            return True
        else:
            return False

    def solve(self):
        for i in range(len(self.grid)):
            for j in range(len(self.grid)):
                if self.is_empty(i,j):
                    for n in range(1, len(self.grid)+1):
                        if self.check_validity(i,j,n):
                            self.grid[i][j] = n
                            self.solve()
                            self.grid[i][j] = 0
                    return 
        for row in self.grid:
            print(row)





if __name__ == "__main__":
    solver = Solver(test_sudoku)
    for row in test_sudoku:
        print(row)
    solver.solve()

很可能是我搞砸了递归调用，但我找不到错误。

Answer 1

我偶然发现了这里，因为我在尝试解决 JavaScript 中的相同数独游戏时遇到了类似的问题。首先我把 box+= 改成 box= 得到了稍微好一点的结果，但是速度很慢而且给出了很多不正确的答案。用以下内容替换您的盒子部分：

        for q in range(i,i+3) :
            for w in range(j,j+3) :
                if self.grid[q][w] == n :
                    return False

回溯数独求解器总是 returns 初始板

backtracking sudoku solver always returns initial board

python

recursion

backtracking