Simple Sudoku with Backtracking
Experience with backtracking
When I first started preparing for technical interviews, I was spending tons of time learning different data structures, algorithms and time complexity. I was able to get a general grasp on different concepts through amazing medium articles and hacker rank problems, but I was unable to get a good grasp on the concept of backtracking because it was so theoretical and most of the problems were complex interview problems.
This article hopes to be that missing piece that allows you to use a real-world example with simple explanations so you can quickly get back to interview preparation, or use backtracking in your own program to do something cool!
The Problem
Note: If you are already aware of the rules of Sodoku, feel free to skip down to the section labeled “Backtracking”.
Through the course of this article, we are going to explore the principle of backtracking by using it to solve a game of Sudoku. If you have never heard of Sudoku before, it is a logic-based puzzle game that requires you to combine numbers to come completely fill the board. The objective is for you to fill a 9x9 grid so that each column, each row, and each of the nine 3x3 subgrids that compose the grid contain all the digits from 1–9. When starting, some of the grids are partially filled in. Here is an example of a starting board.
And here is the solution to the above board. Notice that every row and every column have the digits from 1 to 9.
Aside, Sudoku is a perfect puzzle to explore backtracking with, since it is very logic-based. However, this article is not about how to solve a Sudoku board manually, however. If you would like to learn how to do that, I recommend this article that I also used for the images seen above.
Backtracking
Note: If you already know what backtracking is and are just here for its use in backtracking, feel free to skip to the section labeled “Solving Sudoku” below.
So far I have mentioned the term “backtracking” a fair amount, but what the hell is it? Backtracking is a general algorithm for finding all (or some) solutions to a problem that incrementally builds candidates to the solution. As soon as it determines that a candidate can not possibly be the solution to the problem, it abandons it (“backtracks”).
When the algorithm abandons a candidate, it will typically return to a previous stage in the problem-solving process. This is the key to the algorithm and also where it gets its name.
Eight Queens (N-Queens) and other problems
The most common example of this, one that you have probably heard of, and one that is very theoretical is the eight queens puzzle. Eight queens asks for an arrangement of eight chess queens on a standard chessboard so that no queen attacks any of the others.
In the common backtracking approach to this problem, the partial candidates are arrangements of k queens in the first k rows of the board, all in different rows and columns. Any partial solution that contains two mutually attacking queens can be abandoned.
I won't go very deep into N-Queens because it is fairly theoretical and the goal of this article is to use simple real-word examples, but if you would like to read more, here is a fantastic article from Sachin Malhotra that digs deeper into it.
Other common problems that you have already probably heard of in regards to backtracking are its use in crosswords, verbal arithmetic, and finding a path through a maze. It is also the most convenient (if not most efficient) technique for parsing, the knapsack problem combinatorial optimization problems. It is also the basis of so-called “logic programmings” languages such as Prolog, Icon, and Planner.
More details about the algorithm
Apart from the original problem and end goal, backtracking usually has a set of constraints that the program must also follow to be effective.
The most simple (and ‘dumbest’) implementations of backtracking will often use very little “logic” or have very little “insight” into the problem. Instead of being an efficient solution, this will typically lead to the program guessing randomly and will often be no better than a straight-up brute force solution.
Solving Sudoku
Now that you know what Sudoku is and what backtracking is, let's go over the constraints and the goal that our algorithm will need to solve Sudoku, and then we will walk through a simple 3x3 problem as if we were the algorithm. The following are the constraints and goals for our backtracking algorithm.
Constraints
Remember, the constraints for the project are defined by verifying each individual candidate. For Sudoku, a candidate is valid if the following constraints are true.
- Each row has unique numbers from 1–9 or empty spaces.
- Each column has unique numbers from 1–9 or empty spaces.
- Each sub-grid of 1–9 has the numbers 1–9 or empty spaces.
Goal and Termination Conditions
The goal of our algorithm is also the goal of the game, as well as being very similar to our constraints. In Sudoku, we only have one goal.
- Fill in the numbers from 1–9 exactly once in each row, column, and 3x3 region.
Most backtracking algorithms also have some sort of termination condition so that they do not loop infinitely looking for a solution to a problem that has no solution. In the case of Sudoku, we only have two termination conditions.
- The board is already filled, meaning there is no white space.
- There are no more empty spots left for the algorithm to check, and the current candidate does not reach our goal.
The Code
The above link links to a trinket that contains the code, and an example, of the Sudoku Solver in action. It shows you when the algorithm backtracks when a candidate is no longer viable.
I hope that this visualization will show you how the backtrack works in action, and the code provides a nice step by step with the added comments on how the backtracking process works.
I would like to thank https://www.101computing.net/ for their nice visualization and base for the code that is above, I just made some modifications to make it easier to read and understand what is going on.
Resources & Closing Notes
So now that you are a master of solving Sudoku, where should you go next? If you want to check out some other problems that you can solve, I would recommend the following two to really cement your knowledge of backtracking.
- N-Queens: More theoretical, but a common interview question. I mentioned it earlier, but a great article on this specific problem can be found here.
- Maze Solving: Another practical, fun example that backtracking can also solve. A classmate of mine wrote a good article on this which can be found here. If you want to check out the algorithm now, here is a great visualization I found.
If you want to learn more about backtracking and its use cases, here are a few varying articles to help deepen your understanding.
Thanks for reading. I hope you now have a deeper understanding of backtracking a useful case for it!
If you want to check out other stuff that I have done, check me out on Github.
