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

41–50 of 101 posts

Re: Solving Every Sudoku Puzzle (2006)

#41

Post by jsjohnst »

opnitro wrote: post #29
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

For me, my go to problem tends to be a simplistic lisp interpreter.

I’ve always used an authoritative DNS server as my go to. Almost all code I write has to do some kind of network IO, so learning the nuances of how TCP and UDP sockets work is important to me. It also happens to touch on bitwise operations, data structures, and parsing, so it’s a great project to quickly become competent in a language (assuming you already know DNS well at a protocol layer).

Re: Solving Every Sudoku Puzzle (2006)

#42

Post by the_af »

mannykannot wrote: post #38
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 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.

Re: Solving Every Sudoku Puzzle (2006)

#43

Post by kregasaurusrex »

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, also published by O'Reilly.

Re: Solving Every Sudoku Puzzle (2006)

#44

Post by 53x15 »

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…

It can be done with just depth first search, but if you want it to be fast you can go pretty far down the rabbit hole. The details of your representation, your heuristics, and the kinds of constraint propagation you support all matter a lot.

Here's a long walk through these issues in developing a fast solver: https://t-dillon.github.io/tdoku

Re: Solving Every Sudoku Puzzle (2006)

#45

Post by opnitro »

jsjohnst wrote: post #41
opnitro wrote: post #29

Earlier quoted context omitted.

For me, my go to problem tends to be a simplistic lisp interpreter.

I’ve always used an authoritative DNS server as my go to. Almost all code I write has to do some kind of network IO, so learning the nuances of how TCP and UDP sockets work is important to me. It also happens to touch on bitwise operations, data structures, and parsing, so it’s a great project to quickly become competent in a language (assuming you already know DNS well at a protocol layer).

That's a great one! I might steal it.

Re: Solving Every Sudoku Puzzle (2006)

#46

Post by war1025 »

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?

I guess you should be able to verify pretty easily that the solution he posted is valid, right? But I guess he didn't actually post the solution his code came up with, so who knows...

Re: Solving Every Sudoku Puzzle (2006)

#47

Post by dws »

mannykannot wrote: post #38
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 o…

When making this comparison, it's worth noting that Jeffries is showing his work process. Norvig is showing a cleaned up version of his final result after throwing away some earlier attempts. (Source: I spoke with Peter about Sudoku solvers shortly after he'd published.)

Re: Solving Every Sudoku Puzzle (2006)

#48

Post by barbegal »

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?

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.

Re: Solving Every Sudoku Puzzle (2006)

#49

Post by pdonis »

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.

Re: Solving Every Sudoku Puzzle (2006)

#50

Post by war1025 »

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.

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