Решатель алгоритма возврата судоку вызывает ошибку 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

python sudoku recursive-backtracking
person Yariel Mercado    schedule 09.06.2020    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Проблема с вашим кодом заключается в том, что каждый раз, когда на доске в 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
person DerekG    schedule 09.06.2020

arrow_upward
0
arrow_downward

Я бы предложил переформулировать ваш алгоритм как итерацию.

# 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()
person Martin Frisk    schedule 09.06.2020