возвращение судоку решатель всегда возвращает начальную доску

Question

Как и многие новички, я пробую этот простой проект, но мой алгоритм, в конце концов, возвращает исходную доску, с которой я начал, что означает, что не существует жизнеспособного решения, хотя какое-то время он, кажется, развивается просто хорошо. Я точно знаю, что предоставляю ему действительную и разрешимую доску судоку. Кажется, я не могу понять свою ошибку, любой вклад и критику очень ценят!

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. Сначала я поменял коробку + = на коробку = и получил немного лучший результат, но он был очень медленным и дал много неправильных ответов. Замените свою часть коробки следующим:

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