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.