10 ms·
Solving Every Sudoku Puzzle (2006)
- foobaw 7y agoMy first ever CS assignment was to build a sudoku solver using MIPS. I remember reading this then and being inspired by the beauty of computer science!
- war1025 7y agoWrote a solver using basically the same idea back in college. Was kind of fun. Probably some stupid things in there that I would do differently now with more experience. https://github.com/war1025/sudoku-solver/blob/master/Sudoku/Sudoku.vala https://github.com/war1025/sudoku-solver/blob/master/Sudoku/...
- lostcolony 7y agoSame. 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).
- war1025 7y agoI 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.
- mxz3000 7y agoHmm it's weird. I tried my solver on it and it tells me that it can't find a solution (in 13 seconds). My solver is pretty well tested (on some very difficult sudokus as well). Maybe this guy's solver is bugged?
- deleted 7y ago[deleted]
- war1025 7y agoI guess you should be able to verify pretty easily that the solution he posted is valid, right? But I guess he didn't actually post the solution his code came up with, so who knows...
- barbegal 7y agoIt's trivial to know that it has more than one possible solution since less than 8 of the possible numbers are on the initial board meaning any valid solution that is found has a mirrored solution with all of one number swapped for all of another number.
- war1025 7y agoTheoretically a board with multiple solutions should be easier to find a solution for though, right?
- whataboutist 7y agoTheoretically a board with multiple solutions isn't a sudoku.
- mxz3000 7y agoSure. My solver is designed to return the first solution it finds (it doesn't check for solution uniqueness, just that there is one). However currently my solver is saying that it can't find _any_ solution at all.
- knorrke 7y agoWell the text says it doesn't have a solution, so...
- war1025 7y agoHadn'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 :)
- 53x15 7y agoIt'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 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.
- RantyDave 7y agoAnother! https://github.com/RantyDave/sudoku https://github.com/RantyDave/sudoku
- jmpman 7y agoFirst time I saw a sudoku, was so intrigued, I wrote a solver using simulated annealing. Solved any puzzle in a couple second.
- makomk 7y agoThis is pretty much exactly the algorithm that https://www.ioccc.org/2005/aidan/aidan.c https://www.ioccc.org/2005/aidan/aidan.c uses, except obviously much more clearly expressed. There's also a reasonably straightforward extension of this technique that can test for solution uniqueness, and so generate random valid puzzles; I can't remember how it was implemented exactly but it involves continuing the search after finding the first solution and seeing if it succeeds.
- yeldarb 7y agoSudoku solvers are near and dear to my heart. 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 https://twitter.com/braddwyer/status/910030265006923776?s=21
- pj_mukh 7y agoThat’s a really great way to learn a new language. Maybe take a Swift 101 course and then drag through a sudoku solver. Very cool!
- ashtonbaker 7y agoI do the same thing! The first program I ever wrote was a very simple sudoku solver on a TI-84 calculator (it performed the constraint propagation logic that Norvig describes), and for every programming language I have learned since I have re-written that code.
- opnitro 7y agoFor me, my go to problem tends to be a simplistic lisp interpreter.
- jsjohnst 7y agoI’ve always used an authoritative DNS server as my go to. Almost all code I write has to do some kind of network IO, so learning the nuances of how TCP and UDP sockets work is important to me. It also happens to touch on bitwise operations, data structures, and parsing, so it’s a great project to quickly become competent in a language (assuming you already know DNS well at a protocol layer).
- opnitro 7y agoThat's a great one! I might steal it.
- 7y ago
- jhncls 7y agoI love it how with the Z3Py solver you just write down a few constraints (rows, columns, 3x3 boxes and the given values) and you immediately get an answer. [0] https://ericpony.github.io/z3py-tutorial/guide-examples.htm https://ericpony.github.io/z3py-tutorial/guide-examples.htm [1] https://yurichev.com/writings/SAT_SMT_by_example.pdf https://yurichev.com/writings/SAT_SMT_by_example.pdf
- bgilroy26 7y agoRaymond Hettinger has a great video introduction to SAT solvers in python [47m] https://www.youtube.com/watch?v=_GP9OpZPUYc https://www.youtube.com/watch?v=_GP9OpZPUYc
- elquimico 7y agoI wrote a TypeScript implementation of this algorithm https://www.khrapov.org/sudoku/solver.html https://www.khrapov.org/sudoku/solver.html
- jessegee 7y agoI 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. ;)
- deleted 7y ago[deleted]
- ernesth 7y agoSimilar 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-part-3-a-game-of-falling-shapes/ https://www.filfre.net/2017/06/a-tale-of-the-mirror-world-pa...
- RcouF1uZ4gsC 7y agoContrast this with the TDD approach: http://ravimohan.blogspot.com/2007/04/learning-from-sudoku-solvers.html http://ravimohan.blogspot.com/2007/04/learning-from-sudoku-s...
- mannykannot 7y agoDo you mean the series of posts linked to from the one you give, beginning with [1]? They are an excellent demonstration of two of the pitfalls of naive TDD: 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. [1] https://ronjeffries.com/xprog/articles/oksudoku/ https://ronjeffries.com/xprog/articles/oksudoku/
- the_af 7y ago> They are an excellent demonstration of two of the pitfalls of naive TDD 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.
- tptacek 7y agoI think he acknowledged it pretty clearly; he claimed it as one of his most public failures, didn't he? 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.
- mannykannot 7y ago> You could TDD constraint propagation and it'd work fine. That's exactly why I call it naive TDD, and not a failing of TDD in general. Jeffries deserves credit for making it public.
- pge 7y agoOn a related note, Knuth has a cool algorithm to solve exact coverage problems like sudoku (similar logic as Norvig's DFS but implemented very differently). It's more work to code it than Norvig's but worth it for the education:) (and it solves faster) Here's the paper describing the algorithm: https://arxiv.org/pdf/cs/0011047.pdf https://arxiv.org/pdf/cs/0011047.pdf
- CJefferson 7y agoWhile dancing links is cool, when benchmarking it turns out using bits to represent values, and just copying, ends up being faster. This is because on modern CPUs about the worst thing you can do is lots of pointer following.
- sjaak 7y agoI 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
- CJefferson 7y agoCounting based on problems is tricky, as it depends how hard the problem is. When I implemented, I got about 4x faster with bit packing.
- emerent 7y agoThere is a collection of benchmarks of the fastest sudoku solvers here: https://github.com/t-dillon/tdoku/tree/master/benchmarks 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.
- 53x15 7y agoI'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/2011/06/19/an-incomplete-review-of-sudoku-solver-implementations/ https://attractivechaos.wordpress.com/2011/06/19/an-incomple...
- gopalv 7y ago> I can copy values with values.copy() which is simple and efficient. If I implemented a possibility as a Python set or list I would need to use copy.deepcopy(values), which is less efficient. 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. [1] - http://notmysock.org/code/sudoku/solver.py http://notmysock.org/code/sudoku/solver.py [2] - http://notmysock.org/code/sudoku/ http://notmysock.org/code/sudoku/
- dahart 7y ago> As computer security expert Ben Laurie has stated, Sudoku is "a denial of service attack on human intellect". Several people I know (including my wife) were infected by the virus, and I thought maybe this would demonstrate that they didn't need to spend any more time on Sudoku. That's hilarious! But what puzzles, or even activities wouldn't be classified by Ben as a DOS on humans?
- jedberg 7y agoTic-tac-toe? :)
- drcode 7y agoWhat I wonder is: In what way is chess different from sudoku that it is not a DOS?
- billforsternz 7y agoThere's beauty in chess.
- jedberg 7y agoAn oldie but a goodie. 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.
- jpwagner 7y agoA long time ago I did high school math instruction. I used Sudoku for an initial introduction to proofs - something where the student knew they were implicitly going through a "proof" process.
- kccqzy 7y agoAha yes! When I wrote my first sudoku solver a decade ago I was having fun and decided to stress test my solver with bigger N. I found a site dedicated to these and with puzzles as large as 64x64.
- brian_spiering 7y agoBinary Sudoku - https://xkcd.com/74/ https://xkcd.com/74/
- rurp 7y agoYou might want to check out KenKen puzzles. They are similar to Sudoku and were created by a math teacher as a fun learning tool. IMO, they are quite a bit more interesting than Sudoku puzzles.
- antod 7y agoAs well as Kenken, I also like Killer Sudoku as a more interesting option than vanilla Sudoku. It's basically 9x9 Kenken with addition as the only operator, it uses a bunch of the same thought processes as Kakuro which I like too.
- Stenzel 7y agoMuch faster if constraints are represented by single bits in an integer mask and binary masking operations are used - even the hardest soduko solves instantly.
- skizm 7y agoThe key insight when writing a sudoku solver is that it is just depth first search. Once someone told me that it just sort of clicked. Just guess each possible number at each open square and if you ever get to an un-solvable state, just undo the last change you made and try the next one. I was extremely satisfied with myself after writing my first really clean solver with backtracking. 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.
- jkaptur 7y agoI don't think there are, actually. Some algorithms might run faster in practice, but, since the game is NP-complete, brute force is pretty much as good as it gets for exact solutions.
- war1025 7y agoThe constraint propagation bit is the main key. It still ends up being a DFS, but at most steps along the way, finding one number leads causally to several other spaces being found. 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.
- 53x15 7y agoIt can be done with just depth first search, but if you want it to be fast you can go pretty far down the rabbit hole. The details of your representation, your heuristics, and the kinds of constraint propagation you support all matter a lot. Here's a long walk through these issues in developing a fast solver: https://t-dillon.github.io/tdoku https://t-dillon.github.io/tdoku
- antod 7y agoI've only ever written one solver in Python about 10yrs ago. But it wasn't a search and never made guesses, it was an enumeration of all the analog elimination methods I'd ever figured out when solving them on paper. 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.
- dang 7y agoA thread from 2015: https://news.ycombinator.com/item?id=9901214 https://news.ycombinator.com/item?id=9901214 2011: https://news.ycombinator.com/item?id=3096922 https://news.ycombinator.com/item?id=3096922
- jazzychad 7y agoFor a mind-melting good time, check out this sudoku solver written in APL: https://www.youtube.com/watch?v=DmT80OseAGs https://www.youtube.com/watch?v=DmT80OseAGs
- pdonis 7y agoI always thought one of the requirements for published Sudoku puzzles was that no trial and error should be required; it should be possible to deduce the single unique solution from the clues given. This would mean the "search" part of Norvig's algorithm would not be required; constraint propagation alone would be enough.
- mcphage 7y ago> no trial and error should be required; it should be possible to deduce the single unique solution from the clues given Any sufficiently advanced solving heuristic is indistinguishable from trial and error.
- pdonis 7y agoHeuristic, yes. But I specifically said "deduce" to eliminate heuristics.
- l_t 7y agoI think technically, if constraint propagation can't solve the puzzle, that means it's either contradictory (zero solutions) or ambiguous (multiple solutions). 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.
- T-hawk 7y agoIf there is one unique solution, then constraint propagation always works, yes. 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.
- catpolice 7y agoA 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 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.
- 53x15 7y agoThis sounds like Crook's Algorithm (https://www.ams.org/notices/200904/tx090400460p.pdf 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.
- deleted 7y ago[deleted]
- carapace 7y agoFWIW, here's what I call "Boring Sudoku" in Prolog. It is just 81 vars constrained to be 1..9 and then twenty-seven applications of the Pigeonhole principle. https://swish.swi-prolog.org/p/Boring%20Sudoku.swinb https://swish.swi-prolog.org/p/Boring%20Sudoku.swinb
- drudru11 7y agoA lot of people here have built solvers. What about Sudoku generators?
- billpg 7y agoI'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."
- Tehdasi 7y agoThe algo described in the 'constraint propigation' section was basically how I implemented my sodoku solver, and it basically can do 99% of all puzzles thrown at it. And it wasn't particularly complicated.
- mrcactu5 7y agolast year's US Sudoku Team Qualifier was held online at some point. Possibly in May or July. http://wpc.puzzles.com/ussq2019/ http://wpc.puzzles.com/ussq2019/