A lot of people here have built solvers. What about Sudoku generators?
https://sites.math.washington.edu/~morrow/mcm/team2280.pdf Is my favorite paper on the subject. Section 8.3 describes a generator.
Awesome - thx!
Solving Every Sudoku Puzzle (2006)
81–90 of 101 posts
Re: Solving Every Sudoku Puzzle (2006)
#82Earlier quoted context omitted.
I wrote a (straightforward) dancing links implementation that solves 17.000 puzzles/sec/core. It also validates uniqueness of the found solution. How much faster does it get? I'm genuinely curious
There is a collection of benchmarks of the fastest sudoku solvers here: https://github.com/t-dillon/tdoku/tree/master/benchmarks 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.
I see, do those solvers explore the entire solution space to also validate that a puzzle has exactly 1 solution?
That's one of the cool things about a dlx solver: it can do that while still being very fast.
Re: Solving Every Sudoku Puzzle (2006)
#83Earlier quoted context omitted.
Well the text says it doesn't have a solution, so...
Hadn't noticed that. I assumed when he said it to 1400 seconds then it did come up with a solution. Makes me feel less bad then :)
Oh that explains everything. That's what I get for being too lazy and not reading the fine print I feel happy now at the fact that my solver is about 2 orders of magnitude faster than his!
Re: Solving Every Sudoku Puzzle (2006)
#84Earlier quoted context omitted.
Same. Didn't save the code; wish I had just so I could see if I got a better execution time than his 1439 second example. 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).
I left my solver running for 28 minutes and it never found a solution to that puzzle. Guess whatever corner case it's hitting in his program is the same as my program runs into.
It's easy to see why this puzzle has no solution. Looking at columns 4-6 we see that none of the digits 1,5,6 can occur in cells G4,H4,I4 or G6,H6,I6. So some permutation of these digits occupies G5,H5,I5 and all digits other than 1,5,6 can be eliminated from these cells. But we also see that all the digits 1,5,6 have already been placed in row G, leaving no candidates for G5.
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.
Re: Solving Every Sudoku Puzzle (2006)
#85Earlier quoted context omitted.
There is a collection of benchmarks of the fastest sudoku solvers here: https://github.com/t-dillon/tdoku/tree/master/benchmarks 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.
I see, do those solvers explore the entire solution space to also validate that a puzzle has exactly 1 solution? That's one of the cool things about a dlx solver: it can do that while still being very fast.
All of them do.
Re: Solving Every Sudoku Puzzle (2006)
#86A while back I wrote a solver that uses no backtracking, just constraint propagation, and it wasn't substantially more complex than this. 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 ha…
This sounds like Crook's Algorithm (https://www.ams.org/notices/200904/tx090400460p.pdf), which is a perfectly reasonable thing to do, especially for pencil-and-paper puzzle solving since pigeonhole inferences are easy for people to spot. But this inference rule does not suffice on its own for many hard puzzles. Crook's algorithm still requires backtracking.
Re: Solving Every Sudoku Puzzle (2006)
#87I love the quote near the bottom: "Sudoku is a denial of service attack on human intellect." You could substitute "Sudoku" with most social media platforms and it would be equally true. ;)
Similar to how tetris was (jokingly ?) described as a plot of the soviet to ruin the productivity of the west by hijacking the minds.
Second-hand Reference: https://www.filfre.net/2017/06/a-tale-of-the-mirror-world-pa...
Re: Solving Every Sudoku Puzzle (2006)
#88Earlier quoted context omitted.
There is a collection of benchmarks of the fastest sudoku solvers here: https://github.com/t-dillon/tdoku/tree/master/benchmarks 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.
I'm the author of Tdoku and maintainer of those benchmarks. 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/2…
Thanks, it's nice to have something to point to about DLX, other than "mine was slow".
Re: Solving Every Sudoku Puzzle (2006)
#89Earlier quoted context omitted.
There is a collection of benchmarks of the fastest sudoku solvers here: https://github.com/t-dillon/tdoku/tree/master/benchmarks 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.
I'm the author of Tdoku and maintainer of those benchmarks. 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/2…
Seems pretty competitive to me if the third fastest in your benchmark uses dancing links.
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.
Re: Solving Every Sudoku Puzzle (2006)
#90I'd like to see a solver that works in a similar way to how a human would solve a puzzle.
"This square must be a 5 because a 5 can't appear in any other cell in this row."