Sudoku Solver Using Backtracking in Python

Visheshkasturia
Jul 5 · 5 min read

The Beginning

I remember back when I started my journey to master Data Structures and Algorithms (still ongoing), I referred to various tutorials and solutions on sites like GeeksforGeeks, LeetCode etc. and although I could understand the solution, I couldn’t program it myself without referring.

Little did I realise at that point that all the practice I was doing, eventually would add up and I would be able to nail a backtracking problem on my own. For those on the track to learn, algorithms or solving problems on various problems, I can only say keep moving forward. Every new problem you encounter, spend some time thinking about it and it is okay to refer to solutions in the beginning while learning algorithms.

Every problem you solve registers as a blip in your mind and once you’ve done enough problems, so many of these blips have been registered that when you encounter a new problem, your mind automatically connects the dots and you’ll be surprised that you solved it on your own.

This problem is special to me because this was the first big problem for me that I solved without referring to anything. I’d like to share my solution:

The Sudoku Problem

The problem statement is simple: Given an unsolved sudoku puzzle, we have to generate all possible solutions of the sudoku.

The people familiar with the concept of Sudoku and Backtracking can skip to the solution where I have explained its implementation.

A sudoku is a puzzle which contains 9 blocks. Each block further has 9 cells for a total of 81 cells. The rules of the puzzle are simple- every block should contain the numbers 1–9, one in each cell, such that the number appears only once in its row, column and block.

Initially, the grid is partially filled. Keeping in mind the constraints, one has to fill in the rest of the cells.

Example- Unsolved Sudoku
Example- Unsolved Sudoku
Example: Unsolved Sudoku

Backtracking is a technique which basically tests all possible options recursively and returns all the correct ones. At any point if no possible option is valid or no further action can be taken, it backtracks to the last valid state.

It is used to solve various well known problems such as N-Queens, Rat in a Maze, Hamiltonian Cycle etc. (Tutorial for another day)

Solution

So given an unsolved sudoku, we have to generate all the possible solutions. The language of the problem statement “all the possible solutions” is generally a hint towards applying backtracking algorithm. The solution has been listed in detail below.

We’ll take line separated input for each row of the board and space separated input for each digit in the row. The board will be stored in a 2D Matrix of 9x9 dimension. The empty cells are denoted by ‘0’ and the non-empty cells by their digits.

board=[]
for i in range(9):
print("Enter space separated elements of row {}".format(i))
row=[int(x) for x in input().strip().split()]
board.append(row)
print()
solveSudoku(board)
Image for post
Image for post
Input Board
Image for post
Image for post

The program implements three functions namely:

  1. isValid() : This function returns True if the current move is valid, i.e. if the digit can be placed in the current cell (board[i][j]). It checks the digit for all possible collision.

Collision can occur if :

i) digit x already occurs in the row

ii) digit x already occurs in the column

iii) digit x already occurs in the block

def isValid(i,j,x,board):
#check row
for col in range(9):
if board[i][col]==x:
return False

#check column
for row in range(9):
if board[row][j]==x:
return False

#check block
startrow=i-i%3
startcol=j-j%3

p=startrow
while p<=startrow+2:
l=startcol
while l<=startcol+2:
if board[p][l]==x:
return False
l+=1
p+=1

return True

2. sudokuSolverHelper(): this is the function which recursively implements the backtracking algorithm and searches for all possible solutions of the problem.

For ith row it recursively call itself for j+1

Each time j >8 we move to the next row i+1 and reset j to 0 (since there are only 9 columns: 0–8)

When i==8 and j==8, it means we have reached the final cell, and if the digit in the final cell is valid, we print the entire board and return.

It is important reset board[i][j] to 0 (unfilled) after we have returned so that we the algorithm can search for further possible solutions.

def solveSudokuHelper(i,j,board):
if i==8 and j==8:
if board[i][j]!=0:
for row in board:
for ele in row:
print(ele, end=" ")
print()
else:
for x in range(1,10):
if isValid(i,j,x,board) is True:
board[i][j]=x
for row in board:
for ele in row:
print(ele, end=" ")
print()
board[i][j]=0
print()
return

if j>8:
solveSudokuHelper(i+1,0,board)
return

if board[i][j]==0:
for x in range(1,10):
if isValid(i,j,x,board) is True:
board[i][j]=x
solveSudokuHelper(i,j+1,board)
board[i][j]=0
else:
solveSudokuHelper(i,j+1,board)
return

3. sudokuSolver(): This is the function that calls the helper function with appropriate arguments. A user while interacting does not want to bother with too many arguments but wants the solution and hence this function takes as argument the board and adds appropriate arguments for recursion purpose and calls the main helper function.

def solveSudoku(board):
solveSudokuHelper(0,0,board)

The output prints all the possible solutions of the given sudoku. In our case there is only possible solution for the given input and it is shown below.

Image for post
Image for post
Output Solution
def isValid(i,j,x,board):
#check row
for col in range(9):
if board[i][col]==x:
return False

#check column
for row in range(9):
if board[row][j]==x:
return False

#check block
startrow=i-i%3
startcol=j-j%3

p=startrow
while p<=startrow+2:
l=startcol
while l<=startcol+2:
if board[p][l]==x:
return False
l+=1
p+=1

return True
def solveSudokuHelper(i,j,board):
if i==8 and j==8:
if board[i][j]!=0:
for row in board:
for ele in row:
print(ele, end=" ")
print()
else:
for x in range(1,10):
if isValid(i,j,x,board) is True:
board[i][j]=x
for row in board:
for ele in row:
print(ele, end=" ")
print()
board[i][j]=0
print()
return

if j>8:
solveSudokuHelper(i+1,0,board)
return

if board[i][j]==0:
for x in range(1,10):
if isValid(i,j,x,board) is True:
board[i][j]=x
solveSudokuHelper(i,j+1,board)
board[i][j]=0
else:
solveSudokuHelper(i,j+1,board)
return
def solveSudoku(board):
solveSudokuHelper(0,0,board)
board=[]
for i in range(9):
print("Enter space separated elements of row {}".format(i))
row=[int(x) for x in input().strip().split()]
board.append(row)
print()
solveSudoku(board)

Ending Note

Backtracking is a fairly simple to implement algorithm once you do get a grip on it. Solving this problem gave a significant boost to my confidence and I hope it helps those who want to learn backtracking or solve this problem. This is the first article I’ve shared on medium. I am looking forward to submitting more.

The Startup

Medium's largest active publication, followed by +717K people. Follow to join our community.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store