Sudoku solver using backtracking

Sudoku solver

Sudoku solver using backtracking

Basically in sudoku, we want to be able to solve a sudoku puzzle given an input like this, which represents a sudoku board:

[[x00, x01, x02, x03... x08],
 [x10, x11, x12, x13... x18],
 ...
 [x80, x81, x82, x83... x88]]

These x_rc values correspond to the value at the rth row, cth column (starting with 0-index) These values could be empty (we will represent this with -1)

So for example,

[[-1,  1,  5, ...],
 [-1, -1, -1, ...],
 [ 6, -1, -1, ...]
 ...]

would represent a board like this:

 -----------
|     1   5 | ...
|           | ...
| 6         | ...
 -----------
 ...

Now, our goal is to solve our sudoku puzzle using Python! :D

Owner
Kylie
YouTube: Kylie Ying
Kylie
Comments
  • Don't understand everything

    Don't understand everything

    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

  • Updated print

    Updated print

    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.

  • Terminates without error

    Terminates without error

    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))
    
    
  • Update sudoku.py (now more than two times as fast)

    Update sudoku.py (now more than two times as fast)

    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.

  • Problem I have noticed

    Problem I have noticed

    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.

Related tags
Terrible sudoku solver with spaghetti code and performance issues

SudokuSolver Terrible sudoku solver with spaghetti code and performance issues - if it's unable to figure out next step it will stop working, it never

Dec 5, 2021
Python Freecell Solver

freecell Python Freecell Solver Very early version right now. You can pick a board by changing the file path in freecell.py If you want to play a game

Nov 26, 2021
Wordle Solver

Wordle Solver Installation Install the following onto your computer: Python 3.10.x Download Page Run pip install -r requirements.txt Instructions To r

Feb 15, 2022
Fastest Semantle solver this side of the Mississippi

semantle Fastest Semantle solver this side of the Mississippi. Roughly 3 average turns to win Measured against (part of) the word2vec-google-news-300

Jul 25, 2022
☘️ Projet Voltaire Solver in Python3
☘️ Projet Voltaire Solver in Python3

☘️ Projet Voltaire Solver in Python3

May 25, 2022
a wordle-solver written in python
a wordle-solver written in python

Wordle Solver Overview This is yet another wordle solver. It is built with the word list of the official wordle website, but it should also work with

Jun 22, 2022
You can easily send campaigns, e-marketing have actually account using cash will thank you for using our tools, and you can support our Vodafone Cash +201090788026

*** Welcome User Sorry I Mean Hello Brother ✓ Devolper and Design : Mokhtar Abdelkreem ========================================== You Can Follow Us O

Nov 3, 2021
Run CodeServer on Google Colab using Inlets in less than 60 secs using your own domain.

Inlets Colab Run CodeServer on Colab using Inlets in less than 60 secs using your own domain. Features Optimized for Inlets/InletsPro Use your own Cus

Dec 30, 2021
Research using python - Guide for development of research code (using Anaconda Python)

Guide for development of research code (using Anaconda Python) TL;DR: One time s

Feb 1, 2022
AIST++ API This repo contains starter code for using the AIST++ dataset.
AIST++ API This repo contains starter code for using the AIST++ dataset.

AIST++ API This repo contains starter code for using the AIST++ dataset. To download the dataset or explore details of this dataset, please go to our

Jul 24, 2022
A flexible free and unlimited python tool to translate between different languages in a simple way using multiple translators.
A flexible free and unlimited python tool to translate between different languages in a simple way using multiple translators.

deep-translator Translation for humans A flexible FREE and UNLIMITED tool to translate between different languages in a simple way using multiple tran

Aug 3, 2022
qecsim is a Python 3 package for simulating quantum error correction using stabilizer codes.

qecsim qecsim is a Python 3 package for simulating quantum error correction using stabilizer codes.

Jul 15, 2022
An ultra fast cross-platform multiple screenshots module in pure Python using ctypes.

Python MSS from mss import mss # The simplest use, save a screen shot of the 1st monitor with mss() as sct: sct.shot() An ultra fast cross-platfo

Jul 22, 2022
To check my COVID-19 vaccine appointment, I wrote an infinite loop that sends me a Whatsapp message hourly using Twilio and Selenium. It works on my Raspberry Pi computer.
To check my COVID-19 vaccine appointment, I wrote an infinite loop that sends me a Whatsapp message hourly using Twilio and Selenium. It works on my Raspberry Pi computer.

COVID-19_vaccine_appointment To check my COVID-19 vaccine appointment, I wrote an infinite loop that sends me a Whatsapp message hourly using Twilio a

Dec 25, 2021
A simple service that allows you to run commands on the server using text

Server Text A simple flask service that allows you to run commands on the server/computer over sms. Think of it as a shell where you run commands over

Nov 9, 2021
Reactjs web app written entirely in python, using transcrypt compiler.

Reactjs web app written entirely in python, using transcrypt compiler.

Dec 11, 2021
Checks for Vaccine Availability at your district and notifies you using E-mail, subscribe to our website.

Vaccine Availability Notifier Project Description Checks for Vaccine Availability at your district and notifies you using E-mail every 10 mins. Kindly

Jun 3, 2021
Simple GUI menu for micropython using a rotary encoder and basic display.

Micropython encoder based menu This is a simple menu system written in micropython. It uses a switch, a rotary encoder and an OLED display.

Jun 20, 2022