Solving Every Sudoku Puzzle (2006)
norvig.com
norvig.com
They’re my go to problem when learning a new programming language because they’re just complex enough to exercise a whole bunch of different language features.
I built this when I wanted to learn Swift and dip my toe into machine learning: https://twitter.com/braddwyer/status/910030265006923776?s=21
Edit: The book was 'The Ruby Programming Language' by O'Reilly Publishing, not 'Programming Python' as I originally thought, also published by O'Reilly.
The other day we were at a restaurant and they gave my four year old a kids menu. One of the activities was a modified sudoku that went up to 6. My first thought was that I'd never realized you could do sudokus with other values of N.
But the really cool part was that once I taught her the rules (the constraints) she was actually able to figure it out without much help at all!
Turns out sudoku is a good way to teach kids logic, even at four years old.
https://github.com/war1025/sudoku-solver/blob/master/Sudoku/...
Amusingly, my rationale was much like the author's; I freakin' hate Sudoku. So the fact it's such an obvious candidate to have an automated solver for meant I wrote one (it was also an excuse to do something more meaningful than the intro to CS exercises that class had me doing).
It's also easy to see why this presents a problem for the Norvig solver (and many solvers like it). If you squint at the algorithm you'll see that it behaves like DPLL (https://en.wikipedia.org/wiki/DPLL_algorithm) given a CNF encoding of the Sudoku exactly-one constraints. In this scheme constraint propagation only occurs via unit resolution. i.e., when a positive clause is reduced to a single literal because the domain of a cell is reduced to a single digit or a unit/group is reduced to having a single place for a given digit. In Sudoku land these are known as naked and hidden singles.
Unfortunately, the conclusion that none of 2,4,7,8,9 can occupy G5 arises from the interaction of multiple non-unit clauses. It is simply not reachable by unit resolution. As a result, the conflict won't be discovered until the algorithm actually attempts to assign G5, and, since there are many cells that initially have fewer possibilities than G5, this is not likely to happen early in the search.
Some of the faster solvers can handle this by adding checks for "locked candidates", or by representing the logic in a way that's equisatisfiable, but that makes these inferences available to unit resolution. In such cases this puzzle is recognized as unsatisfiable in microseconds.
I basically just kept a "possibility space" for each empty cell (containing a list of all possible values it could be), started with the one with the smallest size > 0, tried a value as 'true', removed that possible value from all related cells (same row, column, 3x3), recursed. If an empty cell had a possibility space of 0, it would pop back off the stack, removing that prior 'possibility' and resume from there. If I ever got back to an empty stack, there was no solution.
I threw a few dozen puzzles at it, trying to pull ones that were hard both for humans and, ostensibly, for machines, but I never saw it take more than a couple seconds, and that in the most degenerate "had to try every possible permutation" cases. Hence why I really wish I'd kept the code to throw that one at.
I knew that there could be degenerate cases like that that would cause it to take O(n!) time, but the ones that I ran into still didn't take -that- long, which was what surprised me.
[0] https://ericpony.github.io/z3py-tutorial/guide-examples.htm
I'm sure there are other, more efficient, ways to write sudoku solvers, but the simplicity and clarity the DFS solver offers is pretty cool IMO.
Here's a long walk through these issues in developing a fast solver: https://t-dillon.github.io/tdoku
In most easy / medium puzzles, there are actually no points where you need to guess (i.e. recurse down the tree).
In many hard puzzles, there are only one of two guesses, which is where you would recurse down the decision tree.
Things get a bit more intense once you move into the puzzles specifically designed to be a pain in the neck for programs, but often those inputs aren't actually valid Sudoku puzzles.
It was fast, but there were a few difficult puzzles it couldn't solve - obviously there were some real world techniques/alogrithms I hadn't managed to figure out.
1) The things you can test first (before you have figured out the central problem) are not necessarily the things that matter most. The author should have addressed the algorithm for solving the puzzle first; everything else is secondary.
2) This is an example of those cases where having tests for what you are going to write does not provide much guidance into how to solve the problem.
Because Jeffries' series is about TDD, and not really Sudoku, the process is important. And the process failed him spectacularly.
I think it's particularly interesting because Ron Jeffries is not a novice but one of the creators of Extreme Programming, an expert TDD practitioner and evangelist. And to my knowledge, he never acknowledged clearly that he failed in this exercise because he approached it the wrong way, or that he was naive about TDD.
He did? All I see is a series of articles where he randomly flails towards no clear goal, with no clear understanding of Sudoku and gaining no insight either. At the end it just peters out. The last article claims "Sudoku will not ship", and that's it for a post-mortem.
Unless he wrote another article elsewhere explaining how TDD failed him, or how he employed it wrong, or owning up to any mistakes, I think he acknowledged nothing.
Watching Norving vs Jeffries writing a Sudoku solver is watching someone who understands the field vs a novice who doesn't know what he doesn't know. Except this novice is a self-proclaimed expert. It's embarrassing, really.
> But also, where's the TDD naivete? The problem isn't TDD, the problem is knowing how to apply constraint propagation. You could TDD constraint propagation and it'd work fine.
Jeffries "sold" TDD as a design and problem exploration technique (aka "TDD is not about testing"), which it really is not suitable for, or at least not for algorithms (I've no doubt you can TDD a CRUD application, but how uninteresting is that?). It's a lot less sexy if he had said "yeah, all the TDD in the world won't save you researching the problem, maybe actually reading the literature on the subject or learning about specific techniques (like constraint propagation) will help". TDD as a design/discovery method for algorithms doesn't work -- you won't learn constraint propagation by doing TDD. Did Jeffries acknowledge anything of the sort?
You know why TDD is often demonstrated in toy examples with the Fibonacci sequence or similar algorithms? It's because everyone already understands them. It's easy to "arrive" at a solution you already know beforehand.
Be wary of anyone who proposes some procedure X, and when it fails claims "yeah, well, this is not a failure of X because <reasons>".
That's exactly why I call it naive TDD, and not a failing of TDD in general. Jeffries deserves credit for making it public.
He builds a data type that encodes the constraint space. Any value this cell contains can not be present in these other 20 cells, so let's build upon that.
And then he builds the process of elimination structure that so many sudoku puzzlers used that it started showing up in many of the implementations.
> It turns out that the fundamental operation is not assigning a value, but rather eliminating one of the possible values for a square
You could substitute "Sudoku" with most social media platforms and it would be equally true. ;)
Second-hand Reference: https://www.filfre.net/2017/06/a-tale-of-the-mirror-world-pa...
However, it seems Norvig was feeding his program with all three types of puzzles -- zero, one, and multiple solutions -- so perhaps that led him to implement a more robust search.
But a propagated constraint isn't always just a single value at a time. There are cases where a solver (human or machine) needs to identify that a group of two or three or more cells mutually creates a constraint. ("Naked twins" and other such configurations, in Sudoku jargon.) Which can recursively cause to exist another such mutual constraint, and so on. Identifying every possible way such a constraint can arise isn't a simple operation either to implement or to execute, computationally speaking.
For both Norvig's programmatic solver and for a human, it's possible and common for trial and error to be faster and more expedient than trying to identify and execute every possible means a constraint can arise. Norvig's aim was for implementational simplicity more so than computational elegance, deciding to care about only the simplest possible type of constraint, and let trial and error handle everything else.
Any sufficiently advanced solving heuristic is indistinguishable from trial and error.
It is just 81 vars constrained to be 1..9 and then twenty-seven applications of the Pigeonhole principle.
One of the key insights comes from noticing a feature of groups of numbers in cells. For example, suppose you notice two cells in a given row and they're the only cells in that row that the numbers 1 and 2 can be placed in - then one of them is going to have 1 and the other will have 2, and you don't know which but you can eliminate any other possibilities in those two cells. This generalizes to groups of any size in rows/columns/squares. I think that and maybe one other heuristic along with the basic rules about number placement is enough to solve everything.
The array deepcopy isn't too bad, at least when writing code, it compressed into a neat slice [:]
I wrote a hinter[2] which was more fun than the actual solver too, because it shows the "minimum remaining values" as a colour coded chart.
Here's the paper describing the algorithm: https://arxiv.org/pdf/cs/0011047.pdf
How much faster does it get? I'm genuinely curious
How fast they are depends on the difficulty of the sudoku and on your machine, but it's typically a few thousand/s on the hardest known and several 100k/s to a million/s on very easy.
If anyone has a well optimized DLX implementation I'd love to add it to the comparison. The few I've sampled from github were not competitive, but I have no idea how much effort when into them.
This page from 2011 has some comparisons of backtracking and DLX solvers from that era, but it would be interesting to update: https://attractivechaos.wordpress.com/2011/06/19/an-incomple...
I do think it's probably true that dancing links wont be literally the fastest, but the neat thing is that it's a generic algorithm that solves ALL total cover problems, not just Sudoku. Of course a tuned Sudoku solver could probably beat it (optimizing around the Sudoku-specific parts), but it's nice to see that it's at least in the running.
I certainly don't mean do disparage DLX. It's a powerful and general algorithm. But if you need a fast Sudoku solver (for puzzle mining or studying Sudoku research questions) then it's not the tool I'd reach for. The backtracking solvers just get a lot of mileage out of tuning their representation to play nicely with hardware. They also blow general purpose CDCL SAT solvers out of the water, at least for 9x9 Sudoku.
That's one of the cool things about a dlx solver: it can do that while still being very fast.
Handily, pretty much the same code solves polyonimoes too (and other exact cover problems, though I haven't written any other front ends).
That's hilarious! But what puzzles, or even activities wouldn't be classified by Ben as a DOS on humans?
"This square must be a 5 because a 5 can't appear in any other cell in this row."