Python Sudoku Solver using Backtracking

Sudoku puzzles are the most popular form of number game that we have been playing since our childhood. In fact, it is a simple puzzle, with a simple design and simple rules without any hindrances. However, children and adults of all ages cannot help but fall in love with its challenges. In this project, we will develop a Sudoku game in Python. Let’s start!!!

What is the Sudoku Game?

The Sudoku puzzle game is played on a 9 x 9 grid. Within the rows and columns are 9 boxes which are made up of 3 x 3 space. The purpose of the puzzle is to enter a digit number from 1 to 9 in each row & a 9 × 9 grid column without duplicating any numbers between the row, column or box.

Python Sudoku Solver Project Details

Sudoku is one of the most popular games in children and adults also, it is a fun game that keeps the brain active and improves brain capacity. In the Python programming language, pygame is the best module for making game programs. Also, we are importing the request library and then we are making get calls and post calls for accessing url. We are using sugoku API to create the initial board values and store the grid values in our board.

Project Prerequisite

This project requires good python knowledge and a pygame library that we will use for this project. For this project, we use an algorithm to reverse the sudoku solution which is a backtracking algorithm.

Download Python Sudoku Solver Code

Please download the source code of Python Sudoku from the following link: Python Sudoku Solver Project

Steps to Build a Python Sudoku Solver

Below are the steps to develop python sudoku solver project from scratch

1. Installing pygame module.
2. Import Modules- pygame and requests.
3. Setting Pygame and Building a pygame window
4. Making Sudoku Grid
5. Building API
6. Placing the elements on the board
7. Function to check if grid position is empty or not
8. Function for checking if the entered value is valid
9. Solving Sudoku using a Backtracking algorithm.
10. Quitting the game

Step 1: Installing pygame module.

As the name suggests it is used in building games in python. Pygame is the python library that provides functionality for drawing graphics, drawing lines, making geometry, and many shapes easily.

We need a pygame library for this python sudoku game. Install pygame using the below command.

pip install pygame

Step 2: Import Modules- pygame and requests

#PythonGeeks- imports
import pygame
import requests

Code Explanation

• pygame library- Pygame is the python library that provides functionality for drawing graphics, drawing lines, making geometry, and many shapes easily.
• Request library – Request is the library used in python for making get calls and post calls as well to access sudoku url.

Step 3: Setting Pygame and Building a pygame window

WIDTH = 550
Background_Color = (245,251,250)

def main():
    pygame.init()
    window = pygame.display.set_mode((WIDTH, WIDTH))
    pygame.display.set_caption("Sudoku using PythonGeeks")

Code Explanation

• Import pygame using the command pip install pygame
• Background_Color – We fill the window with this background color.
• pygame.init – In the main use function we use this pygame.init for initializing the pygame module.
• pygame.display.set_mode – we create the window using this with the width 550.
• set_caption – Setting the caption here as “Sudoku using PythonGeeks”

Step 4: Making Sudoku Grid

for i in range(0,10):
        if(i%3 == 0):
            pygame.draw.line(window, (0,0,0), (50 + 50*i, 50), (50 + 50*i ,500),4)
            pygame.draw.line(window, (0,0,0), (50, 50 + 50*i), (500, 50 + 50*i),4)
 
        pygame.draw.line(window, (0,0,0), (50 + 50*i, 50), (50 + 50*i ,500 ), 2 )
        pygame.draw.line(window, (0,0,0), (50, 50 + 50*i), (500, 50 + 50*i), 2 )
    pygame.display.update()

Code Explanation

• In order to add the grid here, we have a loop that will run 10 times. And will make columns and rows of the grid.
• We have a background color and we fill the window with this background color.
• Now make the grids using a for loop, sudoku basically a 9 cross 9 grid, so right we need 10 lines in the vertical and 10 in the horizontal.
• pygame.draw.line – Use to draw these vertical and horizontal lines. Using the parameters window, color, starting coordinates, and ending coordinates.

As we have seen, sudoku grids contain bold lines after every third line. So for making the line bold after every third line here we add an if loop.

Step 5: Building API

response_API = requests.get("https://sugoku.herokuapp.com/board?difficulty=easy")
grid_board = response_API.json()['board']
original_grid = [[grid_board[x][y] for y in range(len(grid_board[0]))] for x in range(len(grid_board))]

Code Explanation-

• We have to call an API and fetch those values which will be filling in our sudoku. Now the reason for doing that is just that we can input any random values into sudoku.
• We need to have a proper set of values that can be solved so here I found this amazing site called sugoku they have an API which you can hit and they will provide you sudoku boards for free.
• so here we add an API call so we can populate our grid with those elements.
• This is the link https://sugoku.herokuapp.com/board?difficulty=easy and here we set the difficulty as easy.
• response.json()[‘board’] – here we extract the board from this response that we have got so we will store that in a variable called gird. So this will transfer the grid into our variable grid.
• original_grid – Purpose of making this variable is only for making a copy of the board because we will be changing the values of the board so at last it will help in checking the correctness.

Step 6: Placing the elements on the board

buffer = 5

window.fill(Background_Color)
Font = pygame.font.SysFont('Comic Sans MS', 35)


for i in range(0, len(grid_board[0])):
    for j in range(0, len(grid_board[0])):
        if(0<grid_board[i][j]<10):
        Value_board = font.render(str(grid_board[i][j]), True, original_grid_element_color)
        window.blit(Value_board, ((j+1)*50 + 15, (i+1)*50 ))

pygame.display.update()

Code Explanation

• window.fill – for filling background color
• Font – In the main function declaring the font
• In order to populate the sudoku we will have a for loop inside a for loop. myfont.render – here we have to render the text which we have to add
• window.blit – It copies content of one window to another window of python sudoku solver project
• We need to place it on the screen if you recall whenever we add a text to a screen in a pygame so 1st render that particular text and then we add it to the screen using blit function of pygame.
• display.update – Displaying updated window.

Step 7: Function to check if grid position is empty or not

def isEmpty(number):
    if number == 0:
        return True
    return False

Code Explanation

def isEmpty() – This function checks if the position of the grid which you have supplied is empty or not. If num is equal to 0 then it is empty otherwise not.

Step 8: Function for checking if the entered value is valid

def isValid(place, number):
    
    for i in range(0, len(grid_board[0])):
        if(grid_board[place[0]][i] == number):
            return False
 
    for i in range(0, len(grid_board[0])):
        if(grid_board[i][place[1]] == number):
            return False
 
    x = place[0]//3*3
    y = place[1]//3*3
   
    for i in range(0,3):
        for j in range(0,3):
            if(grid_board[x+i][y+j]== number):
                return False
    return True

Code Explanation

• def isValid() – This function checks that whatever number we are choosing is a valid no. or not.
• There are 3 constraints of sudoku row, column and box if these constraints are satisfied then only address a valid number.

Step 9: Solving Sudoku using Backtracking algorithm

solving = 0
def Sudoku_solver(window):
    font = pygame.font.SysFont('Comic Sans MS', 35)
    for i in range(0,len(grid_board[0])):
        for j in range(0, len(grid_board[0])):
            if(isEmpty(grid_board[i][j])):
                for k in range(1,10):
                    if isValid((i,j), k):                  
                        grid_board[i][j] = k
                        pygame.draw.rect(window, Background_Color, ((j+1)*50 + buffer, (i+1)*50+ buffer,50 -2*buffer , 50 - 2*buffer))
                        value = font.render(str(k), True, (0,0,0))
                        window.blit(value, ((j+1)*50 +15,(i+1)*50))
                        pygame.display.update()
                        pygame.time.delay(10)
                       
                        Sudoku_solver(window)                
                        #Exit condition
                        global solving
                        if(solving == 1):
                            return                 
                        #if sudoku_solver returns, there's a mismatch
                        grid_board[i][j] = 0
                        pygame.draw.rect(window, Background_Color, ((j+1)*50 + buffer, (i+1)*50+ buffer,50 -2*buffer , 50 - 2*buffer))
                        pygame.display.update()
                return              
    solving = 1

Code Explanation

• Backtracking algorithm – Here we solve a Python Sudoku game using a backtracking algorithm. One by one we are assigning the numbers to the empty cells. Check it before assigning that the same number is already present in the current row, column and box. After that, assign the proper number using a recursive function to check whether it leads to the solution or not. If it doesn’t lead to the solution then assign the next number.
• Backtracking algorithm steps-
• Backtracking algorithm uses a recursive function so we have applied simple logic that traverses the grid, the sudoku grid from top left to bottom right.
• We visit each of the empty cells and we will determine if a particular number is correct in that place or not.
• If it is correct in that place we will insert that number and move ahead and if in the future we find that we arrive at a position where no number is being valid then we will backtrack and remove this number which we had inserted.
• So first we have to traverse the grid because we have to check each element.
• Here we add an exit condition using the global variable solved and we make it as zero and once this is solved we will make it as one.
• Font – declaring the font
• window.blit – Copies content of one window to another window.
• display.update – use for displaying updated window.
• time.delay – It used to delay time so we can see the output. Here we set it as 10ms.
• solver.window() – Again calling solve() to fill rest of the cells
• global solve – For an existing window.
• draw.rect – Erasing previously entered value on the screen

Step 10: Quitting the game

while True:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
        pygame.quit()
        return

main()

Code Explanation

• Here we use a while loop for quitting the pygame window. If we press the quit button pygame window will quit.

Python Sudoku Solver Output

Summary

We have successfully created a python sudoku solver game as well as a Sudoku solver using a backtracking algorithm. We have learned about the implementation of pygame while making the project and also backtracking algorithms.