Sudoku Solver with Computer Vision and Deep Learning in Python (Part 1)
This is the first part of a series on solving sudoku puzzles using computer vision and deep learning. In this post, we will examine the problem and write the code for a backtracking algorithm that we will use to solve sudoku puzzles. The complete code for this project can be found here.
Sudoku Rules
Let’s briefly review the format and rules of a sudoku puzzle. A sudoku board is a square board of cells, typically arranged in a 9x9 array. The goal is to fill every cell in the puzzle with a digit between 1 and 9. There must not be any duplicate digits in any row, any column, or any 3x3 non-overlapping subsection of the board (as outlined in bold in the example below).
Algorithm
The algorithm we will use to solve our sudoku puzzles is known as backtracking. Backtracking is a depth-first search, where we explore each branch as far as possible, and take a step back (backtrack) if we reach a dead end from which we cannot proceed further. The steps are as follows:
1. Find the first empty cell on the board.
2. Place a digit between 1 and 9 in this cell.
3. Check if this digit is valid according to the current board.
4a. If the digit is valid, repeat steps 1 to 3 recursively, until there are no empty cells left on the board.
4b. If the digit is not valid, try the next digit until you reach 9.
5. If we try to place a 9 in a particular cell, and find it is not valid, then we have nowhere further to go — we have reached a dead-end, and we need to backtrack. Remove the digit from this cell and return to the previous cell to continue trying numbers.
6. Once the board is full, we have found a solution.
This GIF shows the backtracking algorithm in action:
Puzzle Representation in Code
We represent the puzzle as a 2D array with shape (9, 9). Valid sudoku digits are between 1 and 9, so we will represent empty cells using a value of 0.
board = [[0, 0, 3, 0, 2, 0, 6, 0, 0],
[9, 0, 0, 3, 0, 5, 0, 0, 1],
[0, 0, 1, 8, 0, 6, 4, 0, 0],
[0, 0, 8, 1, 0, 2, 9, 0, 0],
[7, 0, 0, 0, 0, 0, 0, 0, 8],
[0, 0, 6, 7, 0, 8, 2, 0, 0],
[0, 0, 2, 6, 0, 9, 5, 0, 0],
[8, 0, 0, 2, 0, 3, 0, 0, 9],
[0, 0, 5, 0, 1, 0, 3, 0, 0]]If we download collections of sudoku puzzles, chances are they will be stored in a .txt file. A puzzle will represented using a string containing 81 numbers. In this case, we can use a helper function to process our string and get a 2D puzzle board like the one above.
Solving the Puzzle
We will create a Python class for our sudoku solver. It will contain three core methods: find_next_empty, is_valid_number, and solve. We can also add a helper method that will print the board in a nice format.
For our __init__ method, we only need to pass a board , which is a list of lists, representing our sudoku puzzle board.
To find the empty cells in our board, we will iterate through the board one row at a time, moving from left to right, checking for zeros. We will return the position of the first zero we find, or if there aren’t any, we return None.
We must check whether or not it is valid to insert a particular number at a specified position on the board. We check if the number we are placing is already present in the row, in the column, or in the 3x3 square. If any of these criteria are satisfied, the digit is invalid and so we return False, otherwise we return True.
Now we can write our recursive function for solving the puzzle. When we write recursive functions, we must define a base case. The function will call itself until the base case is reached, at which point further recursive calls will not be made. For our application, the base case occurs when there are no empty cells left on the board (and so a puzzle solution has been found.)
In our solve method, in lines 12–20, we examine the numbers 1 to 9, and check if it is valid to place the number in the current board position. If a number is valid, we place it on the board and call solve again.
Notice that in each recursive call to solve, our board has fewer empty positions, so we are solving a simpler version of the same problem.
If we try every value from 1 to 9, and we do not find a valid number for the current board position, then we have reached a dead end and we must backtrack. In this case, execution moves to line 24 where we set the current cell’s value back to 0 (representing an empty cell).
On line 25, our current call to solve returns False. This causes execution to return to our previous call to solve, and we go back to the previous cell to continue trying numbers, picking up where we left off.
Finally, let’s create a helper method that will print our board to the console in a nice format that resembles the puzzle board.
Here is how our print_board method displays an unsolved board:
0 0 3 | 0 2 0 | 6 0 0
9 0 0 | 3 0 5 | 0 0 1
0 0 1 | 8 0 6 | 4 0 0
- - - - - - - - - - -
0 0 8 | 1 0 2 | 9 0 0
7 0 0 | 0 0 0 | 0 0 8
0 0 6 | 7 0 8 | 2 0 0
- - - - - - - - - - -
0 0 2 | 6 0 9 | 5 0 0
8 0 0 | 2 0 3 | 0 0 9
0 0 5 | 0 1 0 | 3 0 0We are now ready to use our class to solve a puzzle! We provide a string with 81 digits and use our helper function to get a list of lists representing our board. Next we can create an instance of our SudokuSolver class and use its solve method to solve the puzzle. Once solved, we can print the board to the console using the print_board method.
Now that our board is solved, our call to print_board prints this:
4 8 3 | 9 2 1 | 6 5 7
9 6 7 | 3 4 5 | 8 2 1
2 5 1 | 8 7 6 | 4 9 3
- - - - - - - - - - -
5 4 8 | 1 3 2 | 9 7 6
7 2 9 | 5 6 4 | 1 3 8
1 3 6 | 7 9 8 | 2 4 5
- - - - - - - - - - -
3 7 2 | 6 8 9 | 5 1 4
8 1 4 | 2 5 3 | 7 6 9
6 9 5 | 4 1 7 | 3 8 2Conclusion
In this post, we built a sudoku solver that uses a recursive backtracking algorithm to solve sudoku puzzles.
In the next post (part 2), we will build a deep learning model using Keras, to classify the numbers found in the puzzle. This allows us to obtain a 2D array of integers, just like board, which we can pass to our SudokuSolver instance.
In part 3, we will look at how we can use the OpenCV library to employ computer vision methods to locate and interpret sudoku puzzles from our own pictures of sudkou puzzles. We will also see how we can use OpenCV to annotate our original natural image with the solved puzzle!
In part 4, we will build a fully functional sudoku game using Pygame. We can either use a pre-loaded list of puzzles, or we can drag-and-drop our own image of a puzzle and solve the puzzle in our game! (Check out this video preview of the game!)