Solving Every Sudoku Puzzle (2006)
norvig.com59 points by djoldman 6 days ago
59 points by djoldman 6 days ago
I've seen this article every now and then, and it's always fun to read. Something jumped out at me this time, though:
> 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.
Ah, yes... remember the halcyon days of 2006, when something as benign as Sudoku was considered to be a "denial of service attack on human intellect"?
> As computer security expert Ben Laurie has stated, Sudoku is "a denial of service attack on human intellect". […] I thought maybe this would demonstrate that [my wife doesn’t] need to spend any more time on Sudoku.
The same could be said about every logic puzzle, or other types of puzzles.
People don't do them so actually solve any sort of new problem, or achieve some sort of productivity.
The same reason people don’t jog to get from point A to point B, or to learn how to get around more quickly.
Logic puzzles are exercising parts of our brain that don’t get exercised regularly.
Feels like the "demonstrated it's no longer necessary to solve sudokus" statement may have been a joke :)
Probably a joke... nevertheless I had the same reaction ! It exercises your deduction, binary thinking, also stochastic vs systematic methodology (first look around randomly find the most obvious before going number by number). Getting to discover all the tricks and reasoning in various "dimensions" is very satisfactory as well. But above all sudokuing puts you in a sort of meditative state : focusing your mind on this micro deductive world gets rid of all the noise and can be very relaxing between 2 pomodoros :)
>denial of service attack on human intellect
Sounds like social media feeds these days
If you want to see a master craftsman, check out the fastest sudoku solver.
Uses constraint propagation, not any specialized sudoku solving algorithms. But this person is a CSP expert and finds ways to optimize CSP for sudoku in particular.
… And then does it all in SIMD.
That is an interesting post. However, a much more interesting challenge is solving larger Sudoku puzzles, as 9x9 is (as evidenced in the pos) a trivial problem to solve. 16x16 starts to get somewhat interesting, but at 25x25 it gets really interesting. Most solvers are trivially extensible to larger sizes, making it quite easy to benchmark.
In my testing, 25x25 Sudokus are algorithmically challenging. Solving times for a naive but well-tuned algorithm with reasonable heuristics can easily be on the order of an hour for a single puzzle. A smart system with advanced reasoning can be many orders of magnitude faster.
Then check out perhaps the worst sudoku solver, which works by translating the puzzle to a series of Python package requirements and then asking the package manager to resolve them: https://github.com/konstin/sudoku-in-python-packaging
I was a bit disappointed that he did not in fact solve all billions/trillons of possible sudoku puzzles.
You'd appreciate "Every 5x5 Nonogram": https://news.ycombinator.com/item?id=44140918
[dead]