kleemans.ch

I was always equally annoyed and fascinated by Sudokus - a simple problem, but not that trivial for a human to find a solution (fast or at all).

Coming back to old problems

Inspired by Ali Spittel's post, I decided to give it another try and start over once again.

Over the years, I wrote a lot of Sudoku solvers, with more or less successful variants. Some of them were in C, some in JavaScript and most were in Python, as that is my go-to language for small projects like this.

Most of my solvers were always trying to imitate human behaviour and apply certain techniques which you already might know, like "Hidden Single", "Naked Pair", "Block-Block interactions", "X-Wing", "Swordfish" etc., which get more and more complicated to implement (without mistakes).

The only one that was not was just using a Brute force approach, which got annoyingly slow quickly on Sudokus with many open cells / possibilities.

The problem with all of my Solvers was that they would work well with simple or even medium puzzles, but fail when trying to solve hard or very hard puzzles.

On all of them, I eventually gave up, also because debugging was just a pain. Having an almost correct algorithm which then only fails for very few puzzles is just not something to do for fun in your free time.

Backtracking

This time, I wanted to solve Sudoku once and for all (for me). I started again with Peter Norvigs page, which was very inspiring. The approach is just so elegant and simple to understand that I just had to try to do it like that.

The algorithm itself is pretty simple and consist of two steps, which are repeated:

1. Constraint propagation
2. Search

For constraint propagation, with some simple techniques (naked/hidden single) it's checked whether some candidates should be removed. For example, if a cell is the only in a row/column/3x3-block being able to have a certain number, it must be there. Really simple Sudokus can already be solved with this, although only the simplest.

Then, for Search, some kind of heuristic is applied to guess the next cell (from its possible candidates). It's best to make a guess with a high probability, for example if a cell has only 2 candidates, the probability of being right is 50%.

After this, propagation again, and we either end up with:

a) A solved Sudoku, in which case we are finished b) A valid but unsolved Sudoku, in which case we just repeat once more c) An invalid Sudoku, in which case we roll back

That's it.

Building it

As I don't like recursion that much, I decided to use an iterative approach using a stack. For search, a depth first search (DFS) is performed with "minimum remaining values" heuristic.

I ended up with the following (pseudocode):

1. Propagate rows, columns, blocks ("naked" and "hidden")

2. While not solved:

   a) If valid: Search for best guess and "do it" (add guess and current Sudoku state to stack)

   b) If invalid: Roll back to state before last guess and take next guess

   c) Propagate

Using a stack was a bit of experimenting (what exactly do I need to preserve a state of a Sudoku), but manageable. It also turned out to be very handy for debugging, as I could just look at the state, which contained the decisions made for the search and tweak / fix it until everything worked out.

For actually testing the Solver, I needed some test data. Sudokus (for machines) mostly look like this:

7.18.43.......2.....453..7.6.....7..1...9...5..8.....38...195....23........6.89.4

It's just all the available numbers from top left to bottom right, line by line, with "." for an empty number. (You can see this particular Sudoku below in the grid.)

I also did myself a favour and implemented support for displaying a partially solved grid with candidates (using tkinter):

Insights

1. Only work with candidates

In earlier version of my solvers, I used to track candidates and the "final" number, which appears in the cell, separately. This leads to redundancies and complicated updates between the two, which is completely unnecessary.

If one candidate is left, it is the number of the cell. If a cell has more than one candidate, it's not yet decided. If a cell has no candidates, the Sudoku is in an invalid state.

The "only work with candidates" also applies for "setting" numbers. Take for for example the following situation: A cell can only hold 1, 2 and 3 and then propagation says that this cell should contain a 4.

• If we just set the 4, we run into some kind of invalid state, but might only notice later on.
• But if we remove all candidates except for 4, it's obvious after one step that the cell can't hold any candidate (as "4" was not a candidate anymore), the Sudoku is in an invalid state and we can roll back and try something different.

2. Don't think, just propagate

When implementing this approach (and also earlier), I was very careful in "filling in" cells - would the number comply with the other requirements by the 3x3 block, row and column? If not, I wouldn't fill in the number and just search further.

As it turns out, this is unnecessary, complicated (and redundant) to check, and also much slower. A cell is the last cell in a block to contain a "3"? Just remove the other candidates and run into an invalid state earlier.

3. If a random cell cannot hold any number, the Sudoku is in an invalid state

A crucial insight for me and for making the Solver efficient was the guessing. If we have any unsolved Sudoku and take a random, unsolved cell and try guessing it's candidates, it's really enough to just try this one single cell. If we run into invalid Sudokus every time we guess and set a candidate, we know that, also if we would start with another cell, there is just no possibility for the Sudoku to be still solvable.

Benchmarking

Some Sudokus for testing and benchmarking can be found in the Sudoku folder:

• magictour_easy.csv: 1011 easy puzzles (without solutions), source
• magictour_hard.csv: 95 hard puzzles (without solutions), source
• menneske_random.csv: 90 puzzles from all difficulties (with solutions), source
• norvig_hardest.csv: 10 "hardest" puzzles, source

Solving times

On my 2015 MacBook Pro (2.7 GHz Dual-Core Intel Core i5), the solver performs like this:

• magictour_easy.csv: 1011 puzzles in 28.26 seconds (0.028s per puzzle)
• magictour_hard.csv: 95 puzzles in 20.68 seconds (0.218s per puzzle)
• menneske_random.csv: 90 puzzles in 2.35 seconds (0.026s per puzzle)
• norvig_hardest.csv: 10 puzzles in 0.44 seconds (0.044 per puzzle)

You can find the code on Github: sudoku-backtracking

Thanks for reading!