提问者:小点点

Sudoku回溯算法求解程序引发RecursionError


我正在创建一个基于文本的数独求解器,每次运行代码时,我都会遇到一个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

共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()