我正在创建一个基于文本的数独求解器，每次运行代码时都会遇到递归错误错误。我认为我的代码出了问题，所以我增加了递归深度并且它工作正常，我只是不确定如何重写我的函数以便我可以摆脱递归深度错误。
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
代码的问题在于，每次在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()进行递归调用。基于这种方法，我认为你只需要一个函数(求解(，不需要回溯函数。
伪代码：
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
我建议将算法重新表述为迭代。
# 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()