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

61–70 of 101 posts

Re: Solving Every Sudoku Puzzle (2006)

#61

Post by T-hawk »

femto113 wrote: post #55
pdonis wrote: post #49

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

The search part is definitely considered “bad form” by human solvers. Author apparently lacked the insight that elimination is generalizable to “if any set of N peers contains exactly N distinct values you can eliminate those values from all peers not in the set”, rather than just “if 1 square contains 1 value ...”. That alone would solve all but the hardest puzzles with just a few more lines of code.

I think the author had that insight, just chose not to use that route because it wasn't necessary. For either a human or machine solver, the trial and error route may well be simpler / less code / faster at runtime than implementing and executing every way to recognize a set of N peers for N values.

Re: Solving Every Sudoku Puzzle (2006)

#62

Post by knorrke »

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?

Well the text says it doesn't have a solution, so...

Re: Solving Every Sudoku Puzzle (2006)

#63

Post by hinkley »

RcouF1uZ4gsC wrote: post #11

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

I think Norvig reveals the difference in his opening paragraph. He jumps straight to constraint propagation.

He builds a data type that encodes the constraint space. Any value this cell contains can not be present in these other 20 cells, so let's build upon that.

And then he builds the process of elimination structure that so many sudoku puzzlers used that it started showing up in many of the implementations.

> It turns out that the fundamental operation is not assigning a value, but rather eliminating one of the possible values for a square

Re: Solving Every Sudoku Puzzle (2006)

#64

Post by [deleted] »

l_t wrote: post #52
pdonis wrote: post #49

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

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

[deleted]

Re: Solving Every Sudoku Puzzle (2006)

#65

Post by pdonis »

mcphage wrote: post #51
pdonis wrote: post #49

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

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

Heuristic, yes. But I specifically said "deduce" to eliminate heuristics.

Re: Solving Every Sudoku Puzzle (2006)

#66

Post by war1025 »

knorrke wrote: post #62
mxz3000 wrote: post #31

Earlier quoted context omitted.

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?

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

Re: Solving Every Sudoku Puzzle (2006)

#67

Post by billforsternz »

drcode wrote: post #35
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?

There's beauty in chess.

Re: Solving Every Sudoku Puzzle (2006)

#68

Post by antod »

rurp wrote: post #57
jedberg wrote: post #21

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

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

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

Re: Solving Every Sudoku Puzzle (2006)

#69

Post by antod »

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

Re: Solving Every Sudoku Puzzle (2006)

#70

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]
Post reply on HN