CODEWITHSUNDEEP
pythonsudokurecursive-backtracking
Mercrist
Mercrist

Reputation: 109

Sudoku Backtracking Algorithm Solver raising a RecursionError

I'm creating a text based Sudoku solver and everytime I run the code I hit a RecursionError error. I thought something was wrong with my code so I increased the recursion depth and it works fine, I'm just not sure how to rewrite my function so that I can get rid of the recursion depth error.

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

For clarification, self.history is a list of tuples which remembers all the 0s we've iterated through and self.pos is the current grid we want to check. I increased the recursion limit and it solves a little more than half the board vs. just half the board as before but I have 0 idea how to rewrite the recursive part. I know it's a bit much but help is appreciated!

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

Upvotes: 0

Views: 497

Answers (2)

DerekG
DerekG

Reputation: 3948

The issue with your code is that every time a change is made to the board in self.solve(), a new call to self.solve() is issued. self.solve() never returns a value to the parent self.solve() call, so none of the functions calls ever exit until the very end of the code.

I believe what you intended to do is make it so that each time a value is added, a new call to self.solve() is made. And each time a value is discovered to be invalid, some indicator (i.e. False) is returned to the previous call of self.solve(). In this implementation, there would be at most 81 recursive calls to self.solve(). In your current architecture, there could be as many as 9^81 recursive calls, hence the RecursionError as you quickly use up available space in the stack with each successive call.

To fix, I suggest modifying your code so that self.solve() returns True if there is a valid board combination and False otherwise, and make a recursive call to self.solve() every time a value is added. Based on this approach I think you need only one function (solve) and don't need a backtrack function.

Pseudocode:

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

Upvotes: 2

Martin Frisk
Martin Frisk

Reputation: 31

I would suggest reformulating your algorithm as an iteration.

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

Upvotes: 0

Related Questions