In today’s post, we’ll be coding a Sudoku solver in Python.
To complete this project, you need to be familiar with basic programming concepts, such as using two-dimensional arrays, control structures (if statement, for loop etc) and functions.
You also need to know how Sudoku works. If you are unfamiliar, here’s an excellent site you can refer to – https://www.learn-sudoku.com/sudoku-rules.html.
Here are some topics we’ll cover in today’s project:
- What is the backtracking method
- How to use recursion in programming
- How to solve Sudoku using recursion in Python
Table of Contents
Key Concepts
Before we proceed, let’s go through some key concepts needed for today’s project. The first is the concept of backtracking. We’ll be using the backtracking method to solve our Sudoku puzzle later.
What is backtracking?
Backtracking is a technique in programming where we build a solution step-by-step. At any one point, if we realize that it is impossible to find a valid solution for the current step, we return to the previous step and alter the solution for that step.
In the case of Sudoku, backtracking requires us to solve one cell at a time. At any one point, if we reach a cell that we cannot solve, we return to the previous cell and alter the solution for that cell.
The detailed steps are as follow:
- Scan through the cells row-by-row until you reach an empty cell.
- Test numbers from 1 to 9 for that cell. As soon as a valid number is found, we ‘assume’ that this is the correct answer and fill the cell with that number.
- Move on to the next empty cell and repeat Step 2 for that cell.
- Keep repeating until we encounter a cell with no valid answer (i.e., all numbers from 1 to 9 fail).
- When that happens, move back to the previous cell and try the next valid number.
- Keep repeating until we finally solve the puzzle.
Sounds confusing? Let’s look at a video demonstration of how this works (Credit: Video is recorded using the solver at https://cardgames.io/sudoku/).
In the video recording above, we started by inserting the number 2 into the last cell of row 1.
Next, we move on to row 2 and insert the number 1 into the first cell.
After that, we move to the next cell and try to insert the numbers 1 to 9. Unfortunately, none of the numbers work. When that happens, we need to backtrack.
We move back to the previous cell and try the next valid number. Since the previous cell has a value of 1, we try the next number 2. This number fails but the next number 3 works.
Once we find a number that works, we proceed to the next cell again. This time, the number 1 works for that cell.
This keeps repeating until we solve the whole Sudoku board.
Study the video carefully and make sure you fully understand how backtracking works before proceeding. Another instance of backtracking occurs at 00:38.
Once you are familiar with backtracking, let’s move on to recursion. We’ll be using recursion and backtracking to solve the Sudoku puzzle in our project.
What is recursion?
Recursion is a technique where a function calls itself during its execution.
This is very useful when the solution to the programming problem depends on solutions to smaller instances of the same problem.
Suppose we have a Sudoku board with 10 empty cells.
To decide whether a number is valid for the first empty cell, we can use recursion to try solving the remaining 9 cells. If a solution is found for the remaining 9 cells, we know that the current number is the correct number.
On the other hand, if we are unable to find a solution for the remaining 9 cells, we update the current cell to the next possible number. In other words, based on the failed result of the remaining 9 cells, we backtrack to the current cell to update its value.
This is the gist of how we’ll be using recursion to solve our Sudoku puzzle in this project.
For more examples of how recursion can be used to solve other problems, you can check out these posts (here and here).
It’ll be easier to understand recursion when we start working on our project. Let’s do that now.
Let’s do it!
I’ve broken down the project into 5 steps.
Step 1: Create and print board
This step requires us to create an array called myBoard. This array stores the following Sudoku board as a two-dimensional array.
Each element in myBoard is an array that stores a row in the Sudoku board, where empty cells are replaced by the number 0.
For instance, myBoard[0] stores the first row.
In other words,
myBoard[0] = [0, 4, 0, 7, 0, 0, 1, 3, 0]
After creating the board, you need to write code to print the board. Try doing this yourself.
Expected Result
You should get the following output when you run your code.
[0, 4, 0, 7, 0, 0, 1, 3, 0]
[0, 0, 2, 0, 0, 0, 6, 0, 0]
[0, 0, 0, 4, 2, 0, 0, 0, 0]
[6, 0, 0, 0, 0, 2, 0, 0, 3]
[2, 3, 1, 0, 7, 0, 0, 8, 0]
[4, 0, 0, 3, 1, 0, 0, 0, 0]
[0, 7, 0, 0, 0, 8, 0, 0, 0]
[0, 0, 6, 0, 3, 0, 0, 0, 4]
[8, 9, 0, 0, 5, 0, 0, 0, 6]
Need Help?
The following code creates a two-dimensional array with three elements. The three elements are the arrays [1, 2, 3], [2, 7, 1] and [1, 9, 7].
myArray = [[1, 2, 3],
[2, 7, 1],
[1, 9, 7]]
The following code prints the array above:
for line in myArray:
print(line)
Try modifying the code above to complete Step One.
Suggested Solution
myBoard = [[0, 4, 0, 7, 0, 0, 1, 3, 0],
[0, 0, 2, 0, 0, 0, 6, 0, 0],
[0, 0, 0, 4, 2, 0, 0, 0, 0],
[6, 0, 0, 0, 0, 2, 0, 0, 3],
[2, 3, 1, 0, 7, 0, 0, 8, 0],
[4, 0, 0, 3, 1, 0, 0, 0, 0],
[0, 7, 0, 0, 0, 8, 0, 0, 0],
[0, 0, 6, 0, 3, 0, 0, 0, 4],
[8, 9, 0, 0, 5, 0, 0, 0, 6]]
for line in myBoard:
print(line)
Step 2: Write a function to check if a number is valid for a certain cell
In Step 2, we need to write a function called isValid() that has four parameters – board, row, col and num.
board represents the Sudoku board while row and col represent the row and column of a cell respectively. The isValid() function checks if num can be placed in the cell specified by row and col. If it can, the function returns True. Else, it returns False.
For instance, for the highlighted cell in the Sudoku board in Step One, row = 7 and col = 3 (recall that row and column start from index 0). If num = 6, the isValid() function should return False as 6 already exists in that row. In contrast, if num = 1, isValid() should return True.
Try coding this function yourself. Remember that you have to check if num exists in the current row, column and 3×3 square.
Expected Result
After coding the function, you can check if it works correctly by running the following statements:
print(isValid(myBoard, 3, 4, 6))
print(isValid(myBoard, 2, 6, 6))
print(isValid(myBoard, 7, 7, 6))
print(isValid(myBoard, 4, 3, 6))
If you run the code above, you should get the following output:
False
False
False
True
For the first statement, 6 already exists in row 3. For the second, 6 exists in column 6. For the third, 6 exists in the bottom right 3×3 box.
Hence, for the first 3 statements, you get False as the result.
For the last statement, you get True as 6 is a valid number at row = 4, col = 3.
Need Help?
It is relatively easy to check if num exists in a certain row and column. It is harder to check if it exists in the current 3×3 square.
One way to do that is to figure out the position of the top-left corner of the square. For instance, for the highlighted cell in our example, the top-left corner of the square is at row 6, column 3.
To get the row of the top-left corner, you can use the formula row - row%3.
row%3 gives us the remainder when row is divided by 3. This tells us how far the current cell is from the row of the top-left corner.
In our example, row = 7 for the highlighted cell. row%3 gives us 1, indicating that the highlighted cell is one row below the top-left corner.
row - row%3 gives us 6, which is the row of the top-left corner of that 3×3 square.
To get the column of the top-left corner, you can use the formula
col - col%3
This gives us 3 for the highlighted cell.
From the top-left corner, you can then use a loop to check if num exists at rows 6, 7 and 8, for columns 3, 4, 5.
Based on the description above, try completing the isValid() function yourself.
Suggested Solution
ef isValid(board, row, col, num):
#check row
for i in range(9):
if board[row][i] == num:
return False
#check col
for i in range(9):
if board[i][col] == num:
return False
#get top-left corner
c_row = row - row%3
c_col = col - col%3
#check 3x3 square
for i in range(c_row, c_row+3):
for j in range(c_col, c_col+3):
if board[i][j] == num:
return False
#return True if none of the cases above returns False
return True
Step 3: Create a function to check for empty cells
We’ll start working on solving the puzzle in this step. First, let’s define a function called solveBoard() with one parameter – board (which represents the Sudoku board).
We’ll work on the solveBoard() function in the next few steps.
In this step, solveBoard() only needs to do one thing – loop through board and return False once it finds an empty cell. If it does not find any empty cell, it returns True.
Try doing this yourself.
Expected Result
To test the function, you can run the statement below:
print(solveBoard(myBoard))
completedBoard = [[5, 3, 4, 6, 7, 8, 9, 1, 2],
[6, 7, 2, 1, 9, 5, 3, 4, 8],
[1, 9, 8, 3, 4, 2, 5, 6, 7],
[8, 5, 9, 7, 6, 1, 4, 2, 3],
[4, 2, 6, 8, 5, 3, 7, 9, 1],
[7, 1, 3, 9, 2, 4, 8, 5, 6],
[9, 6, 1, 5, 3, 7, 2, 8, 4],
[2, 8, 7, 4, 1, 9, 6, 3, 5],
[3, 4, 5, 2, 8, 6, 1, 7, 9]]
print(solveBoard(completedBoard))
Here, we first pass myBoard to the solveBoard() function. As there are empty cells in myBoard, the solveBoard() function should return False.
Next, we declare a new board called completedBoard that has no empty cells. We pass this board to the solveBoard() function and print the results.
If you run the code above, you should get
False
True
as the output.
Suggested Solution
def solveBoard(board):
for i in range(9):
for j in range(9):
if board[i][j] == 0:
return False
return True
In the solution above, we loop through board one cell at a time. If we find an empty cell, the if condition on line 4 evaluates to True and we return False (on line 5).
If we finish looping through all the cells and do not find any empty cell, we return True on line 6 (outside the for loops).
Step 4: Insert a valid number into the first empty cell
In this step, we need to modify the solveBoard() function. Instead of returning False immediately when we find an empty cell, we’ll try inserting a number into the empty cell and return True if we manage to do that. We return False only if we don’t manage to find a valid number for that cell.
Try doing this yourself.
Expected Result
To test your function, you can run the statements below:
print(solveBoard(myBoard))
for i in myBoard:
print(i)
Here, we pass myBoard to the solveBoard() function and use a for loop to print the values of myBoard after that. If you run the code above, you should get the following output:
True
[5, 4, 0, 7, 0, 0, 1, 3, 0]
[0, 0, 2, 0, 0, 0, 6, 0, 0]
[0, 0, 0, 4, 2, 0, 0, 0, 0]
[6, 0, 0, 0, 0, 2, 0, 0, 3]
[2, 3, 1, 0, 7, 0, 0, 8, 0]
[4, 0, 0, 3, 1, 0, 0, 0, 0]
[0, 7, 0, 0, 0, 8, 0, 0, 0]
[0, 0, 6, 0, 3, 0, 0, 0, 4]
[8, 9, 0, 0, 5, 0, 0, 0, 6]
The first empty cell (at the top-left hand corner) has been replaced with the number 5.
To test the case where there is no valid number for the first empty cell, try running the code below:
invalidBoard = [[0, 4, 2, 7, 8, 9, 1, 3, 5],
[0, 0, 2, 0, 0, 0, 6, 0, 0],
[0, 0, 0, 4, 2, 0, 0, 0, 0],
[6, 0, 0, 0, 0, 2, 0, 0, 3],
[2, 3, 1, 0, 7, 0, 0, 8, 0],
[4, 0, 0, 3, 1, 0, 0, 0, 0],
[0, 7, 0, 0, 0, 8, 0, 0, 0],
[0, 0, 6, 0, 3, 0, 0, 0, 4],
[8, 9, 0, 0, 5, 0, 0, 0, 6]]
print(solveBoard(invalidBoard))
Here, we pass an invalid board to the solveBoard() function. As there is no valid number for the first empty cell (the first cell in the first row), you should get the following output:
False
Need Help?
You need to insert a for loop before the return False statement in Step 3. This for loop runs from 1 to 9. Inside the loop, you can call the isValid() function to check if a number is valid.
Once a valid number is found, replace the cell with the number found and return True. Try doing this yourself.
Suggested Solution
def solveBoard(board):
for i in range(9):
for j in range(9):
if board[i][j] == 0:
for num in range(1, 10):
if isValid(board, i, j, num):
board[i][j] = num
return True #valid number found for first empty cell
return False
return True # no empty cells found
In the solution above, we return False (on line 9) only after the for loop completes and no valid number is found. If a valid number is found, we would have exited the function on line 8 with the return True statement.
Step 5: Insert valid numbers into all empty cells
Finally, we move on to the hardest step – solving the Sudoku puzzle itself.
Up until now, we’ve managed to fill the first empty cell with a valid (but not necessarily correct) number; the rest of the cells are still unsolved. This happens because we exit the solveBoard() function once we find a valid number for the first empty cell (by returning True after we find the number).
If we want to solve the remaining cells, we should not return True immediately after filling the first cell.
Instead, we should call the solveBoard() function recursively to solve the rest of the board.
To do that, we need to replace the return True statement (line 8) in the solution for Step 4 with a recursive call and an if-else statement that does the following:
If the recursive call to the solveBoard() function is able to solve the rest of the board, it means that the value for the current cell is valid. If that’s the case, we can return True to exit the function.
On the other hand, if the recursive solveBoard() function is unable to solve the rest of the board, it means the current cell is invalid. In that case, we should not exit the function. Instead, we should set board[i][j] to zero to indicate that this cell has not been solved.
The for loop (line 5 in the solution for Step 4) will then proceed to try the next number for this cell. It keeps trying until it finds a valid number.
If it is unable to do so, we return False after the for loop (line 9 in the solution for Step 4) to indicate that there is no solution for the current cell.
If the current cell is not the first empty cell, the for loop for the previous cell will then try the next valid number for that cell. This keeps happening until the entire board is solved.
Based on the description above, try modifying the solution for Step Four to solve the entire Sudoku board.
Expected Result
To test your code, you can run the following statements:
solveBoard(myBoard)
for line in myBoard:
print(line)
You’ll get the following output:
[9, 4, 5, 7, 8, 6, 1, 3, 2]
[7, 1, 2, 5, 9, 3, 6, 4, 8]
[3, 6, 8, 4, 2, 1, 5, 7, 9]
[6, 5, 7, 8, 4, 2, 9, 1, 3]
[2, 3, 1, 6, 7, 9, 4, 8, 5]
[4, 8, 9, 3, 1, 5, 2, 6, 7]
[5, 7, 4, 2, 6, 8, 3, 9, 1]
[1, 2, 6, 9, 3, 7, 8, 5, 4]
[8, 9, 3, 1, 5, 4, 7, 2, 6]
Need Help?
The board can be solved by replacing line 8 in Step 4 with the following code:
result = solveBoard(board)
if result == True:
return True
else:
board[i][j] = 0
Suggested Solution
Here’s the final solution for the solveBoard() function.
def solveBoard(board):
for i in range(9):
for j in range(9):
if board[i][j] == 0:
for num in range(1,10):
if isValid(board, i, j, num):
board[i][j] = num
result = solveBoard(board)
if result == True:
return True
else:
board[i][j] = 0
return False
return True
Putting it all together
Here’s the final complete solution:
'''
Declare the Sudoku Board
'''
myBoard = [[0, 4, 0, 7, 0, 0, 1, 3, 0],
[0, 0, 2, 0, 0, 0, 6, 0, 0],
[0, 0, 0, 4, 2, 0, 0, 0, 0],
[6, 0, 0, 0, 0, 2, 0, 0, 3],
[2, 3, 1, 0, 7, 0, 0, 8, 0],
[4, 0, 0, 3, 1, 0, 0, 0, 0],
[0, 7, 0, 0, 0, 8, 0, 0, 0],
[0, 0, 6, 0, 3, 0, 0, 0, 4],
[8, 9, 0, 0, 5, 0, 0, 0, 6]]
'''
Define the isValid() function,
which checks if num can be place in the cell
indicated by row and col
'''
def isValid(board, row, col, num):
#check row
for i in range(9):
if board[row][i] == num:
return False
#check col
for i in range(9):
if board[i][col] == num:
return False
#get top-left corner
c_row = row - row%3
c_col = col - col%3
#check 3x3 square
for i in range(c_row, c_row+3):
for j in range(c_col, c_col+3):
if board[i][j] == num:
return False
#return True if none of the cases above returns False
return True
'''
Define the solveBoard() function,
which solves the Sudoku board using recursion
'''
def solveBoard(board):
for i in range(9):
for j in range(9):
if board[i][j] == 0:
for num in range(1,10):
if isValid(board, i, j, num):
board[i][j] = num
result = solveBoard(board)
if result == True:
return True
else:
board[i][j] = 0
return False
return True
'''
Call the solveBoard() function and
print the result
'''
solveBoard(myBoard)
for line in myBoard:
print(line)
If you run the code above, you’ll get the following output:
[9, 4, 5, 7, 8, 6, 1, 3, 2]
[7, 1, 2, 5, 9, 3, 6, 4, 8]
[3, 6, 8, 4, 2, 1, 5, 7, 9]
[6, 5, 7, 8, 4, 2, 9, 1, 3]
[2, 3, 1, 6, 7, 9, 4, 8, 5]
[4, 8, 9, 3, 1, 5, 2, 6, 7]
[5, 7, 4, 2, 6, 8, 3, 9, 1]
[1, 2, 6, 9, 3, 7, 8, 5, 4]
[8, 9, 3, 1, 5, 4, 7, 2, 6]
That’s all for today’s post.