Sudoku回溯算法求解器，引发RecursionError

Question

我正在创建一个基于文本的Sudoku求解器，每次运行代码时，我都遇到RecursionError错误。我以为我的代码出了点问题，所以我增加了递归深度，并且可以正常工作，我只是不确定如何重写函数，以便摆脱递归深度错误。

def backtrack (self):
    '''Goes back in the grid and checks for valid numbers'''
    del self.history[len(self.history) - 1]  # goes back to the last spot, not current
    self.pos = self.history[len(self.history) - 1]  # reassign current position
    for numbers in range(9):
        if self.valid(numbers + 1) and (numbers + 1) != self.board[self.pos[0]][self.pos[1]]:  # valid number but not the same as before
            self.board[self.pos[0]][self.pos[1]] = numbers + 1
            return True
    self.board[self.pos[0]][self.pos[1]] = 0 #reset this position to 0
    return False


def solve(self): #recursive, once you get to the end of the board it's solved
    '''solves the Sudoku board, backtrack alg'''
    empty = self.find_empty()
    if not empty:
        return None
    if empty: #if there's an empty spot on the grid:
        for nums in range(9): #try all numbers on a specific spot
            if self.valid(nums+1): #theres no numbers on the column, row, or grid
                self.board[self.pos[0]][self.pos[1]] = nums+1
                break

            elif nums == 8: #reached end of for loop, no number fits in the grid
                while self.backtrack() == False: #keep going until we can plug in a number
                    if self.backtrack() == True:
                        break
        self.solve()  #recursive process

board = Sudoku([
    [7, 8, 0, 4, 0, 0, 1, 2, 0],
    [6, 0, 0, 0, 7, 5, 0, 0, 9],
    [0, 0, 0, 6, 0, 1, 0, 7, 8],
    [0, 0, 7, 0, 4, 0, 2, 6, 0],
    [0, 0, 1, 0, 5, 0, 9, 3, 0],
    [9, 0, 4, 0, 6, 0, 0, 0, 5],
    [0, 7, 0, 3, 0, 0, 0, 1, 2],
    [1, 2, 0, 0, 0, 7, 4, 0, 0],
    [0, 4, 9, 2, 0, 6, 0, 0, 7]
        ])
board.solve()

为澄清起见，self.history是一个元组列表，它记住我们迭代经过的所有0，而self.pos是我们要检查的当前网格。我增加了递归限制，它解决了一半以上的开发板，而以前只解决了一半的开发板，但是我对如何重写递归部分有0的想法。我知道这有点多，但是可以得到帮助！

Error Log:
File "C:/Users/User/Desktop/Sudoku/sudoko_alg.py", line 26, in on_column
    for i in range (9):
RecursionError: maximum recursion depth exceeded in comparison

Process finished with exit code 1

Answer 1

我建议将您的算法重新设计为迭代。

# Verty rough sketch!
states = [Sudoku(initial_numbers)] #a list with the starting configuration
for state in iter(states):
    if state.is_solved():
        print("success!")
        break
    states += state.get_next_states()

Answer 2

您的代码的问题是，每次在self.solve()中对板进行更改时，都会发出对self.solve（）的新调用。 self.solve()从不向父级self.solve()调用返回值，因此直到代码的最后，所有函数调用都不会退出。

我相信您打算做的是，这样每次添加一个值时，都会对self.solve()进行新的调用。并且，每当发现一个值无效时，就会将某个指示符（即False）返回到先前的self.solve()调用。在此实现中，最多将有81个对self.solve()的递归调用。在您当前的体系结构中，可能有多达9 ^ 81个递归调用，因此RecursionError随您在每次后续调用中快速耗尽堆栈中的可用空间。

[为了解决，我建议您修改代码，以便如果存在有效的板卡组合，则self.solve()返回True，否则返回False，并在每次添加值时对self.solve()进行递归调用。