# 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

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

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