This post describes a Sudoku solver in Python. Even the most challenging Sudoku puzzles can be quickly and efficiently solved with depth first search and constraint propagation.
Recently the Sudoku bug bit me. According to Wikipedia, this popular brain teaser puzzle rose to prominence in 2004. “Sudoku” is Japanese for “single number”. The goal of Sudoku is to full a 9x9 grid where each row, column and 3x3 region contains each of the numbers from 1 to 9. These puzzles range in difficulty, and some can be surprisingly hard to solve by hand. But all are remarkably easy to solve with computers.
After a few days of manually playing Sudoku, I naturally decided to write a solver for it. I tackled this problem by myself, before comparing it to other online solvers.
There are two articles I would like to mention that were particularly helpful. The first article is by Ali Spittel. I liked the overall structure of her code, and used it to refactor some of mine. Her code however cannot solve hard puzzles because it only follows a simple constraint propagation strategy. The second article is by Peter Norvig. He uses a more comprehensive search and constraint propagation strategy and provides a thorough analysis with multiple puzzles. I used his set of 95 hard puzzles and 11 hardest puzzles to test my code. However, I found his structure unintuitive. For example, he stores the board as a dictionary instead of a 9x9 array.
Raghav Virmani’s augmented reality solver is very cool. This program solves and overlays solutions on pictures of unsolved Sudokus in real time. It does this by combining Norvig’s solver with a Convolutional Neural Network that can read pictures of numbers.
There are many solvers which refrain from search or any other trial and error strategies. One of the more complex of these is Andrew Stuart’s solver which implements 38 different strategies for solving Sudokus. A major drawback of this type of solver is, despite the complexity, it cannot solve every type of Sudoku puzzle.
Before describing my solver, I’d like to give a quick overview of difficulty levels in Sudoku. I’ve gained an appreciation of them over the last few weeks.
The difficulty levels are:
This is from a human viewpoint. Because the solver uses search, these levels don’t affect its performance. For a computer, all puzzles can be described as “easy”.
This section only considers puzzles with a unique solution or no solution. Any given Sudoku puzzle might have multiple solutions, but most published Sudokus only have one. My solver can find all solutions for any given puzzle.
The New York Times publishes daily Sudokus at www.nytimes.com/puzzles/sudoku/. There are three levels: easy, medium and hard. Here is an example of an easy puzzle (left) and a hard puzzle (right).
The easy puzzle has 39 clues. At the start, there are 13 singles. These are cells where there is a candidate that is unique to that row, column, or box. These can be filled in immediately. This will create other singles, until the very end of the puzzle. I can solve such a puzzle in 3-5 minutes.
The hard puzzle has 23 clues. At the start, there are only 2 singles. To solve the rest of the puzzle, one should compare rows, columns and boxes to eliminate candidates. It is very easy to rediscover the other basic strategies: pairs, triples, pointing pairs and box-line reduction. I can solve these puzzles in 20-30 minutes.
It is enough to use the simplest of these strategies combined with depth first search to solve any Sudoku puzzle very quickly.
People however like to challenge themselves. Is it possible to solve a hard Sudoku without any guessing? There are many more complex strategies for solving Sudoku puzzles. For example, constructing chains across multiple rows, columns and boxes to eliminate candidates. Or comparing multiple cells and candidate combinations to eliminate only a single candidate. In general, it is more work for less.
Some puzzles require at least one of these strategies for solving (with no guessing). Andrew Stuart rates them from Tough to Extreme to Diabolical. I don’t solve these puzzles.
Here is a diabolical puzzle with 26 clues:
This one is particularly nasty. Try put it in Stuart’s solver. It takes multiple steps of small eliminations before the puzzle can be solved. Meanwhile my solver takes only six guesses to solve it.
Ok. So you’ve become a Sudoku master. You abhor guessing. You’ve learnt all the complex techniques. You can create chains across the entire board and swordfishes remind you of your more innocent days. Can you now solve every possible puzzle with logic alone? No guessing? It turns out, no. Stuart himself posts weekly ‘unsolvables’. These puzzles cannot be solved with his logic-only solver. But they are very much solvable with search.
In 2012, this 21-clue puzzle by mathematician Arto Inkala was labelled the hardest Sudoku puzzle in the world:
Is it the hardest? I do not know. But it is certainly a monster. At the very start, one cell has two candidates, and the rest have three. You’re forced to make a guess in the cell with the two candidates. And then at best, another two guesses before you can use any of the techniques in Stuart’s solver. That is a $1$ in $2^3 = 8$ probability of guessing correctly with no wrong guesses. My solver takes 39 guesses to solve this, of which 29 are wrong^{1}. So in other words, even an amateur like me can solve the hardest Sudoku puzzle in the world by hand, as long as they are willing to do it 40 times.
If you search for this term on the internet, you’ll probably find a lot of hard, but certainly solvable, Sudokus. People like to exaggerate the difficulty of these puzzles. There is, however, a very large set of puzzles that are truly impossible. They’re trivially easy to construct. The easiest way to do so, is to play a game of Sudoku and make a mistake XD. Here are two puzzles which are impossible from the start:
Very amusingly, Norvig passed the puzzle on the right to his solver, and it took almost 24 minutes to conclude that it was impossible. His solver otherwise takes less than a second to solve ultra-hard Sudokus. As an amateur Sudoku player, it took me less than a minute to verify that it was impossible^{2}.
To solve even the most challenging of these puzzles, our Sudoku solver only needs to follow three strategies:
In order to check number 2, we have to keep a list of candidates for each block, and update it as values are placed. This adds complexity. We could leave it out - the solver will require more guesses but will still work. However it is easy to find these hidden singles and this step makes the algorithm much faster. So the added complexity is well justified.
My Sudoku class stores two 9x9 arrays: one is for integers with the final value and another is for candidate values.
I also wrote a few helper functions to extract rows, columns and boxes from the grid.
The __repr__
function overrides the default string for the print
function.
These functions are for editing the candidates
array. They are also part of the Sudoku
class.
Below is the find_options
function which is called by __init__
.
I’ve chosen to work with the Python set type for working with candidates.
The set functions union
(operator |
) and difference (operator -
) make it easy to find distinct candidates between intersecting rows, columns and boxes.
As we place values, we’ll need to erase them as candidates in neighbouring blocks. This might then unlock new values elsewhere, so it is useful to do constraint propagation at the same time. While there are many different strategies for constraint propagation, it is sufficient to use only the simplest strategy, hidden singles.
Here is the full solving algorithm. The code scans through all 9x9 blocks, and tries to place easy candidates following step 1 or 2. It repeats this process until no changes are made. Then either the Sudoku is solved, or we should move onto search through strategy 3. If the latter, the code looks for the block with the smallest number of candidates, and takes a guess there. It then starts with step 1 again. If at any time a block has no candidates, it means a mistake was made, and the code backtracks.
Puzzles can be represented in serial format by concatenating rows instead of stacking them. Then instead of storing it as array, it could be stored as a string. This makes it easy to store and retrieve many different puzzles. For example, here is the hard Inkala puzzle:
800000000003600000070090200050007000000045700000100030001000068008500010090000400
Or with ‘.’ instead of ‘0’ for blanks:
8……….36……7..9.2…5…7…….457…..1…3…1….68..85…1..9….4..
The following functions convert between these serial formats and a grid.
This code takes 0.15s and 39 calls to solve to solve the Inkala puzzle. The maximum call depth is 10.
For Norvig’s 95 hard puzzles, the code takes a total of 30.504s, with an average time of 0.321s per puzzle. The average number of calls is 93.0, while the maximum number of calls is 588. This is slower than Norvig’s code. I am unsure if this is because of the algorithm, the implementation or because of my hardware. For Norvig’s 11 hardest puzzles, the total time is 0.671s, with an average of 0.061s per puzzle. The average number of calls is also much lower, at 15.6, with a maximum number calls of 55.
Out of curiosity, I added more advanced strategies: pairs, triples and pointing pairs. For the 95 puzzles, this reduces the total solving time to 8.658s and it reduces the average time to 0.091s. The average number of calls is just 13.7 and the maximum number of calls is 129. For the 11 hardest puzzles, these extra strategies required more time and slow the solving time slightly to 0.072s per puzzle. The average number of calls decreased to 11.6, while the maximum number of calls increased to 74. This shows there are only marginal gains for a lot more effort. Also, they make no difference to the solving path for the Inkala puzzle.
The full code with the advanced strategies can be viewed at my GitHub repository at: https://github.com/LiorSinai/SudokuSolver-Python.
There are also additional functions which are not described here. For example, check_possible
which will flag impossible puzzles like the ones shown earlier.
I hope you enjoyed reading about my Sudoku solver. In some ways, being able to solve every Sudoku puzzle in under a second trivialises the appeal of Sudoku. But I still like to solve mildly challenging Sudokus by hand. It helps me to take my mind off things and relax.
This is a high ratio of 3:1 for wrong:correct guesses. It arises because after a wrong guess is taken all the guesses after that are also wrong until the algorithm backtracks. If we only count the first wrong guess, then the ratio is 4:6. ↩
Look at the middle column. The three sets of 1, 5 and 6 require that the three numbers 1, 5 and 6 fit in the two blocks of H5 and J5. Impossible. ↩