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

31–40 of 101 posts

Re: Solving Every Sudoku Puzzle (2006)

#31

Post by mxz3000 »

war1025 wrote: post #17
lostcolony wrote: post #7

Earlier 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.

Hmm 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?

Re: Solving Every Sudoku Puzzle (2006)

#33

Post by [deleted] »

mxz3000 wrote: post #31
war1025 wrote: post #17

Earlier quoted context omitted.

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.

Hmm 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]

Re: Solving Every Sudoku Puzzle (2006)

#35

Post by drcode »

dahart wrote: post #20

> 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?

What I wonder is: In what way is chess different from sudoku that it is not a DOS?

Re: Solving Every Sudoku Puzzle (2006)

#37

Post by kybernetikos »

pge wrote: post #14

On 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

Here's my implementation of it in (ancient) javascript: http://dancing-links.herokuapp.com/ It works nicely in the browser.

Handily, pretty much the same code solves polyonimoes too (and other exact cover problems, though I haven't written any other front ends).

Re: Solving Every Sudoku Puzzle (2006)

#38

Post by mannykannot »

RcouF1uZ4gsC wrote: post #11

Contrast this with the TDD approach: http://ravimohan.blogspot.com/2007/04/learning-from-sudoku-s...

Do 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/

Re: Solving Every Sudoku Puzzle (2006)

#39

Post by jkaptur »

skizm wrote: post #30

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

I 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.

Re: Solving Every Sudoku Puzzle (2006)

#40

Post by 53x15 »

emerent wrote: post #25
sjaak wrote: post #19

Earlier 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'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-incomple...

Post reply on HN