Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Solving Every Sudoku Puzzle (2006)

norvig.com

Post reply on HN
Print view View original

11–20 of 29 posts

Re: Solving Every Sudoku Puzzle (2006)

#11

Post by mzl »

boat-of-theseus wrote: post #2

[dead]

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.

Re: Solving Every Sudoku Puzzle (2006)

#12

Post by fnands »

wat10000 wrote: post #9
boat-of-theseus wrote: post #2

[dead]

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

That's incredible and completely unhinged. I love it.

Re: Solving Every Sudoku Puzzle (2006)

#13

Post by charlysisto »

jader201 wrote: post #4
johnfn wrote: post #3

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 t…

> 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 do…

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 :)

Re: Solving Every Sudoku Puzzle (2006)

#15

Post by boat-of-theseus »

wat10000 wrote: post #9
boat-of-theseus wrote: post #2

[dead]

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 will propose marriage to whoever wrote this: “you NP-complete me”

Re: Solving Every Sudoku Puzzle (2006)

#16

Post by anthk »

jader201 wrote: post #4
johnfn wrote: post #3

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 t…

> 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 do…

Most logic puzzles such as the software pack made from SGT (or under the paper puzzle booklets, same concept but with pens and paper) are trivially solvable with computers and often STEM people will get bored with them fast. Solve it once, solve it for all.

If any, the challenge and fun would come by solving them with an algorithm under its favourite programming language.

Also, lateral thinking based riddles/puzzles are often more fun to solve, such as the crime related ones.

Re: Solving Every Sudoku Puzzle (2006)

#18

Post by senfiaj »

mzl wrote: post #11
boat-of-theseus wrote: post #2

[dead]

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 f…

Some time ago I wrote a 9x9 Killer Sudoku solver (you can solve ordinary as well, the cages are optional) in JavaScript https://github.com/surenenfiajyan/killer-sudoku-solver

It does backtracking with recursion. It uses bitwise operations for fast conflict detection in rows, columns and 3x3 blocks. But one very important heuristics is that it firstly sorts the cells in such a way that the backtracking brute force starts from the most densely filled side. This eliminates a lot of wrong branches early, and actually helps a lot. I'm thinking maybe I can extend this to 16x16 or 25x25 as well. Not sure if this will scale up adequately. But this one usually cracks puzzles in a fraction of second. It only become slow for extremely hard killer sudoku puzzles.

Re: Solving Every Sudoku Puzzle (2006)

#19

Post by DannyB2 »

johnfn wrote: post #3

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 t…

It was a denial of service attack, not in the sense of soaking up my brain cells solving puzzles, but in causing me to devise and program my own solver. (In Java, text console only.) Once I wrote a solver, I felt as if I had solved all puzzles.

Then I got interested in devising puzzles with multiple solutions. Not too difficult. But making a few puzzles with two solutions was fun.

Experiment_203(

   " 1 . . | 2 . 8 | . . 9 "+
   " . 8 . | . . . | . 3 . "+
   " . . 7 | . 1 . | 2 . . "+
   //------+-------+--------
   " 4 . . | 1 2 3 | . . 6 "+
   " . . 2 | 4 5 6 | 9 . . "+
   " 6 . . | 7 8 9 | . . 4 "+
   //------+-------+--------
   " . . 6 | . 4 . | 8 . . "+
   " . 2 . | . . . | . 7 . "+
   " 9 . . | 8 . 2 | . . 1 "
  ),
// Solution #1. Found in 0 days 00:00:00.004.

// 245 boards examined so far.

   1 6 5 | 2 3 8 | 7 4 9
   2 8 4 | 6 9 7 | 1 3 5
   3 9 7 | 5 1 4 | 2 6 8
   ------+-------+------
   4 7 9 | 1 2 3 | 5 8 6
   8 3 2 | 4 5 6 | 9 1 7
   6 5 1 | 7 8 9 | 3 2 4
   ------+-------+------
   7 1 6 | 3 4 5 | 8 9 2
   5 2 8 | 9 6 1 | 4 7 3
   9 4 3 | 8 7 2 | 6 5 1
// Solution #2. Found in 0 days 00:00:00.001.

// 287 boards examined so far.

   1 6 5 | 2 3 8 | 7 4 9
   2 8 4 | 9 6 7 | 1 3 5  //
Then I got to looking at difficult puzzles on the web. Apparently AI escargot is the world's most difficult. (And the site http://www.aisudoku.com/index_en.html says I can't publish the board). So I'll only publish the stats of applying my solver to it.

  Solution #1.  Found in 0 days 00:00:00.029.
  3,906 boards examined so far.

  1 total solutions found.
  7,832 total boards examined.
  Total time 0 days 00:00:00.085.

Re: Solving Every Sudoku Puzzle (2006)

#20

Post by boat-of-theseus »

wat10000 wrote: post #9
boat-of-theseus wrote: post #2

[dead]

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

you know what the actual most interesting thint about this is for me?

this is the example that made me finally understand how to embed NO complete problems into other NP complete problems.

and this mofo wrote zero code yet tricked a programming language into doing work anyway

Post reply on HN