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

51–60 of 101 posts

Re: Solving Every Sudoku Puzzle (2006)

#51

Post by mcphage »

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.

Re: Solving Every Sudoku Puzzle (2006)

#52

Post by l_t »

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.

Re: Solving Every Sudoku Puzzle (2006)

#53

Post by mxz3000 »

barbegal wrote: post #48
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?

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

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

Re: Solving Every Sudoku Puzzle (2006)

#54

Post by tptacek »

the_af wrote: post #42
mannykannot wrote: post #38

Earlier quoted context omitted.

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

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

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

Re: Solving Every Sudoku Puzzle (2006)

#55

Post by femto113 »

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.

Re: Solving Every Sudoku Puzzle (2006)

#56

Post by catpolice »

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

Re: Solving Every Sudoku Puzzle (2006)

#57

Post by rurp »

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.

Re: Solving Every Sudoku Puzzle (2006)

#58

Post by rude_dude »

kregasaurusrex wrote: post #43
yeldarb wrote: post #6

Sudoku 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

The first one I'd seen was implemented in a Ruby book, and I agree it's a good yet moderately challenging problem to do. Once you're done solving the base case, making improvements like implementing a more efficient backtracking algorithm or drawing a board within a GUI can be added as well. Edit: The book was 'The Ruby Programming Language' by O'Reilly Publishing, not 'Programming Python' as I originally thought, al…

Seems this is a common theme... I wrote a (no search) solver in Perl for a class a while back. Mostly wanted to see how far my own solution finding rules would get me without having to follow through on solving hundreds of puzzles myself.

Re: Solving Every Sudoku Puzzle (2006)

#59

Post by whataboutist »

war1025 wrote: post #50
barbegal wrote: post #48

Earlier quoted context omitted.

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

Theoretically a board with multiple solutions should be easier to find a solution for though, right?

Theoretically a board with multiple solutions isn't a sudoku.

Re: Solving Every Sudoku Puzzle (2006)

#60

Post by T-hawk »

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.

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

Post reply on HN