数独回溯算法求解器引发递归错误

Question

我正在创建一个基于文本的数独解算器，每次我运行我的代码都会遇到 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 是我们要检查的当前网格。我增加了递归限制，它解决了一半多一点的问题，而以前只解决了一半问题，但我不知道如何重写递归部分。我知道这有点多，但感谢您的帮助！

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() 永远不会 returns 父 self.solve() 调用的值，因此 none 的函数调用永远退出，直到代码的最后。

我相信您打算做的是每次添加一个值时，都会对 self.solve() 进行新的调用。并且每次发现一个值无效时，都会将一些指标（即 False）返回给之前调用的 self.solve()。在此实现中，最多将有 81 次对 self.solve() 的递归调用。在您当前的体系结构中，可能有多达 9^81 次递归调用，因此 RecursionError 随着您在每次连续调用中快速用完堆栈中可用的 space。

要修复，我建议修改您的代码，以便 self.solve() returns True 如果有有效的棋盘组合， False 否则，并进行递归调用到 self.solve() 每次添加一个值。基于这种方法，我认为你只需要一个函数（解决）而不需要回溯函数。

伪代码：

def self.solve():
    # find the next unassigned square
    # for each value in range (1,9) assign that value to square and make recursive call to solve()
    # if all recursive calls return False, return False
    # if any call to solve() ever returns True, a valid solution to the board has been found

数独回溯算法求解器引发递归错误

Sudoku Backtracking Algorithm Solver raising a RecursionError

python

sudoku

recursive-backtracking