Solving Sudoku Puzzle using Backtracking in Python | Daily Python #29

This article is a tutorial on solving a sudoku puzzle using Backtracking algorithm in Python

This article is a part of Daily Python challenge that I have taken up for myself. I will be writing short python articles daily.

There are no additional requirements for this article.

What exactly is a Sudoku Puzzle?

According to Wikipedia, Sudoku (originally called Number Place) is a logic-based, combinatorial number-placement puzzle.

The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids that compose the grid (also called “boxes”, “blocks”, or “regions”) contain all of the digits from 1 to 9.

The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution.

Note: The number of classic 9×9 Sudoku solution grids is 6,670,903,752,021,072,936,960 (sequence A107739 in the OEIS), or around 6.67×1021.

So, generating all the grids and choosing the solution is not efficient. To minimize this task, we can use a Backtracking approach.

What is Backtracking?

It is algorithmic-technique for finding all solutions to the same computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate as soon as it determines that the candidate cannot possibly be completed to a valid solution.

In our problem, we need to traverse each block of the grid, check which digit can be placed in this block, repeat till we have a solution. If a digit cannot be placed in the current block, we go to the previous block and try placing another digit in that block, changing the next possible solution.

This basically means, whenever we arrive at a dead-end, we go back to the previous choice we made and change our choice, such that we will have a different possible solution.

Let’s first find a sudoku problem to solve

1 million Sudoku games

You can either download the CSV file or copy a string of the sudoku puzzle problem and create a grid in the code.

Forming the Puzzle

#Forming the Puzzle Grid
def form_grid(puzzle_string):
    global grid
    print('The Sudoku Problem')
    for i in range(0, len(puzzle_string), 9):
        row = puzzle_string[i:i+9]
        temp = []
        for block in row:
            temp.append(int(block))
        grid.append(temp)    
    printGrid()

Function to print the Grid

#Function to print the grid
def printGrid():
    global grid
    for row in grid:
        print(row)

Function to check if a digit can be placed in the current block

#Function to check if a digit can be placed in the given block
def possible(row,col,digit):
    global grid
    for i in range(0,9):
        if grid[row][i] == digit:
            return False
    for i in range(0,9):
        if grid[i][col] == digit:
            return False
    square_row = (row//3)*3
    square_col = (col//3)*3
    for i in range(0,3):
        for j in range(0,3):
            if grid[square_row+i][square_col+j] == digit:
                return False    
    return True

Traversing through all blocks w/ Backtracking

def solve():
    global grid
    for row in range(9):
        for col in range(9):
            if grid[row][col] == 0:
                for digit in range(1,10):
                    if possible(row,col,digit):
                        grid[row][col] = digit
                        solve()
                        grid[row][col] = 0  #Backtrack step
                return
    print('\nThe Solution')
    printGrid()

Finally, passing the Grid and calling the function to Solve the Puzzle

puzzle_string = "004300209005009001070060043006002087190007400050083000600000105003508690042910300"
grid = []
form_grid(puzzle_string)
solve()

Snip of the output of the above code

I hope this article was helpful, do leave some claps if you liked it.

Follow the Daily Python Challenge here:

Ajinkya-Sonawane/Daily-Python

Login * Instagram