Hi, Thanks for this example and the video.

I try to understand how this work. I understand the logic of backtracking, but i don't understand how in the code you go back in positions. I have try to use breakpoint() and see how it works but i'm confused.

(Pdb) c
guess: 9
row: 0 , col: 8
> /Dev/sandbox/python_sudoku_solver/sudoku.py(77)solve_sudoku()
-> puzzle[row][col] = -1 # reset the guess
(Pdb) c
> /Dev/sandbox/python_sudoku_solver/sudoku.py(76)solve_sudoku()
-> breakpoint()
(Pdb) c
guess: 3
row: 0 , col: 7
> /Dev/sandbox/python_sudoku_solver/sudoku.py(77)solve_sudoku()
-> puzzle[row][col] = -1 # reset the guess

When i reach guess = 9 on row: 0, col: 8, i set it back to -1 (puzzle[row][col] = -1). But how do i go back to row:0 col:7 ?

Please help me understand.

Regards

Simple change to the print so that you don't have to resize the terminal window for the rows and columns to line up properly.

PS: Thanks for making approachable python project tutorials. Currently switching gears from java to python and your videos have been a major help.

• All functions are now defined under Sudoku class
• An object with puzzle attribute is created when using Sudoku class
• Replace the pprint function with a custom function that prints the puzzle in 3x3 boxes

Heyo, I try to learn Phyton at the moment and I have started to work through your video tutorials. I am currently stuck at the sudoku solver. I have implemented it (My helper functions are a little different than yours, but essentially work the same way) The code has run in a RecursionError it first:

RecursionError: maximum recursion depth exceeded in comparison

But after amping the recursion limit to 5000 (from originally 1000) this error does not occur anymore.

Now there is no error at all. I have put in an integer which just counts up and is printed in the console so I can see after how many iterations the script terminates. Currently it is at 2128 in my IDE and 2129 in my console. My guess is that the OS terminates it, but I am not certain.

I work on a Windows Machine and use Phyton 3.10.4. I have attached the code I have written.

Have a nice day!

from pprint import pprint
def find_next_empty(puzzle):
    #finds next row, col on the puzzle that is not filled yet -->rep with -1
    for r in range (9):
        for c in range(9):
            if puzzle[r][c]==-1:
                return r, c
            else:
                continue
    return None, None

def is_valid(puzzle, guess, row, col):
    #Checks if the guess is valid by checking row, column and matrix.
    for r in range(9):#Check if there is the number guess already in the row (col is static)
        if puzzle[r][col]==guess:
            return False
    for c in range(9):#Check if there is the number guess already in the col (row is static)
        if puzzle[row][c]==guess:
            return False
        
    #I have also to check the 3x3 matrix for the same number
    #I can check row and col and use their index to determine the representative 3x3 Matrix
    #Representing them with CAPS
    ROW=None
    COL=None
    try:#This could be simplified, but I find it easier to read it in several if statements
        #Generates ROW
        if row in range(3):
            ROW=0
        elif row in range(3,6):
            ROW=1
        elif row in range(6,9):
            ROW=2
        else:
            print(f"{row} is not a valid input for row")
            raise ValueError
        
        #Generates COL
        if col in range(3):
            COL=0
        elif col in range(3,6):
            COL=1
        elif col in range(6,9):
            COL=2
        else:
            print(f"{col} is not a valid input for col")
            raise ValueError
    except ValueError:
        return False
    #I still have to check the matrix, but now I know which one I have to check
    #Generate the Matrix as a list and use a second variable to see if there is the guess
    #Making it a list because I do not need to know if it is lower, higer or left or right
    Mat=[]
    for r in range(3):
        for c in range(3):
            Mat.append(puzzle[ROW+r][COL+c])
    if guess in Mat:
        return False
        
        
    return True


def solve_sudoku(puzzle, i):
    #solve sudoku using backtracking!
    #puzzle is a list of lists, where each inner list represents a row in our puzzle
    #return whether a solution exists
    #mutates puzzle to be the solution (if solution exists)
    print(i)
    i+=1
    #step 1: choose somewhere on the puzzle to make a guess
    #Because we essentially brute force the puzzle, we can choose the first free entry in puzzle and start with 1
    row, col = find_next_empty(puzzle)
    #Step 1.1: if there is nowhere left, then we are done because we only allowed valid inputs
    if row is None:
        pprint(puzzle)#Printing the found solution
        return True
    #Step 2: if there is a place to put a number, then make a guess between 1 and 9
    for guess in range(1,10):
    #Step 3: Check if guess is valid
        if is_valid(puzzle, guess, row, col):
            puzzle[row][col]=guess
        #Now we have a modified puzzle which we will iterate
        #Step 4: Iterate
        if solve_sudoku(puzzle, i):
            return True
        #Step 5. Turns out that the guess was shit. So we count up and start again till we have no numbers left
        else:
            puzzle[row][col]=-1#reset the guess (should not be necessary, but just in case)
            continue
    
    #Step 6: If we have tried every combination and did not solve puzzle, then this solver was not able to solve it and will return false.
    #We can assume that this puzzle is not solveable
    return False                
            
if __name__=='__main__':
    import sys
    import threading
    print(sys.getrecursionlimit())
    i =1
    sys.setrecursionlimit(50000)
    threading.stack_size(10**8)
    example_board = [
        [3, 9, -1,   -1, 5, -1,   -1, -1, -1],
        [-1, -1, -1,   2, -1, -1,   -1, -1, 5],
        [-1, -1, -1,   7, 1, 9,   -1, 8, -1],

        [-1, 5, -1,   -1, 6, 8,   -1, -1, -1],
        [2, -1, 6,   -1, -1, 3,   -1, -1, -1],
        [-1, -1, -1,   -1, -1, -1,   -1, -1, 4],

        [5, -1, -1,   -1, -1, -1,   -1, -1, -1],
        [6, 7, -1,   1, -1, 5,   -1, 4, -1],
        [1, -1, 9,   -1, -1, -1,   2, -1, -1]
    ] 
    pprint(example_board)
    print(solve_sudoku(example_board, i))

Hey Kyllie,

I saw the video "Coding a Sudoku solver in Python using recursion/backtracking" of yours on YouTube. I liked the exercise of making your code faster. But most of all it is a practice for me with Github, which I have never used before. I hope I used it correctly.

Cheers, Jeroen

ps. I succeeded in optimizing your code, it performs now more than two times as fast.

Hi! thank you so much for your helpful tutorial. I have noticed that when I run the code with a sudoku puzzle that is already wrong (for example there is already two of the same digits in one row) it freezes.