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

91–100 of 101 posts

Re: Solving Every Sudoku Puzzle (2006)

#91

Post by 53x15 »

OskarS wrote: post #89
53x15 wrote: post #40

Earlier quoted context omitted.

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/2…

Seems pretty competitive to me if the third fastest in your benchmark uses dancing links. I do think it's probably true that dancing links wont be literally the fastest, but the neat thing is that it's a generic algorithm that solves ALL total cover problems, not just Sudoku. Of course a tuned Sudoku solver could probably beat it (optimizing around the Sudoku-specific parts), but it's nice to see that it's at least i…

Bear in mind that JSolve was 5x faster than the fastest DLX solver in the attractivechaos 2011 benchmarks, and today there are several solvers that are 2x faster than JSolve (https://github.com/t-dillon/tdoku/tree/master/benchmarks). If the difference is really an order of magnitude, that's pretty non-competitive.

I certainly don't mean do disparage DLX. It's a powerful and general algorithm. But if you need a fast Sudoku solver (for puzzle mining or studying Sudoku research questions) then it's not the tool I'd reach for. The backtracking solvers just get a lot of mileage out of tuning their representation to play nicely with hardware. They also blow general purpose CDCL SAT solvers out of the water, at least for 9x9 Sudoku.

Re: Solving Every Sudoku Puzzle (2006)

#92

Post by Tehdasi »

billpg wrote: post #90

I'd like to see a solver that works in a similar way to how a human would solve a puzzle. "This square must be a 5 because a 5 can't appear in any other cell in this row."

The algo described in the 'constraint propigation' section was basically how I implemented my sodoku solver, and it basically can do 99% of all puzzles thrown at it. And it wasn't particularly complicated.

Re: Solving Every Sudoku Puzzle (2006)

#93

Post by the_af »

tptacek wrote: post #54
the_af wrote: post #42

Earlier quoted context omitted.

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

> I think he acknowledged it pretty clearly; he claimed it as one of his most public failures, didn't he?

He did? All I see is a series of articles where he randomly flails towards no clear goal, with no clear understanding of Sudoku and gaining no insight either. At the end it just peters out. The last article claims "Sudoku will not ship", and that's it for a post-mortem.

Unless he wrote another article elsewhere explaining how TDD failed him, or how he employed it wrong, or owning up to any mistakes, I think he acknowledged nothing.

Watching Norving vs Jeffries writing a Sudoku solver is watching someone who understands the field vs a novice who doesn't know what he doesn't know. Except this novice is a self-proclaimed expert. It's embarrassing, really.

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

Jeffries "sold" TDD as a design and problem exploration technique (aka "TDD is not about testing"), which it really is not suitable for, or at least not for algorithms (I've no doubt you can TDD a CRUD application, but how uninteresting is that?). It's a lot less sexy if he had said "yeah, all the TDD in the world won't save you researching the problem, maybe actually reading the literature on the subject or learning about specific techniques (like constraint propagation) will help". TDD as a design/discovery method for algorithms doesn't work -- you won't learn constraint propagation by doing TDD. Did Jeffries acknowledge anything of the sort?

You know why TDD is often demonstrated in toy examples with the Fibonacci sequence or similar algorithms? It's because everyone already understands them. It's easy to "arrive" at a solution you already know beforehand.

Be wary of anyone who proposes some procedure X, and when it fails claims "yeah, well, this is not a failure of X because ".

Re: Solving Every Sudoku Puzzle (2006)

#94

Post by the_af »

dws wrote: post #47
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…

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

I think that's understood. But what's telling is that no single step of Jeffries' series of articles seems to be approaching any kind of sensible solution. It reads like an amateur -- e.g. me -- trying to write a game and getting stuck in the low hanging but inconsequential fruit.

Because Jeffries' series is about TDD, and not really Sudoku, the process is important. And the process failed him spectacularly.

Re: Solving Every Sudoku Puzzle (2006)

#95

Post by the_af »

mannykannot wrote: post #73
tptacek wrote: post #54

Earlier quoted context omitted.

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.

> You could TDD constraint propagation and it'd work fine. That's exactly why I call it naive TDD, and not a failing of TDD in general. Jeffries deserves credit for making it public.

He deserves some credit, but he would have deserved full credits had he acknowledged the limitations of TDD. Which are the ones you mentioned in your first post.

Re: Solving Every Sudoku Puzzle (2006)

#96

Post by zwkrt »

zwkrt wrote: post #75
antod wrote: post #69

Earlier quoted context omitted.

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.

There are sudoku puzzles which have a unique solution but which also force a “guess” in the solving process, so your approach doesn’t work in the general case.

More info: https://puzzling.stackexchange.com/questions/12/are-there-pu...

Re: Solving Every Sudoku Puzzle (2006)

#97

Post by lostcolony »

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?

Yeah; the one I implemented used a different algorithm, and would have noted that there was no solution.

I basically just kept a "possibility space" for each empty cell (containing a list of all possible values it could be), started with the one with the smallest size > 0, tried a value as 'true', removed that possible value from all related cells (same row, column, 3x3), recursed. If an empty cell had a possibility space of 0, it would pop back off the stack, removing that prior 'possibility' and resume from there. If I ever got back to an empty stack, there was no solution.

I threw a few dozen puzzles at it, trying to pull ones that were hard both for humans and, ostensibly, for machines, but I never saw it take more than a couple seconds, and that in the most degenerate "had to try every possible permutation" cases. Hence why I really wish I'd kept the code to throw that one at.

Re: Solving Every Sudoku Puzzle (2006)

#99

Post by war1025 »

lostcolony wrote: post #97
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?

Yeah; the one I implemented used a different algorithm, and would have noted that there was no solution. I basically just kept a "possibility space" for each empty cell (containing a list of all possible values it could be), started with the one with the smallest size > 0, tried a value as 'true', removed that possible value from all related cells (same row, column, 3x3), recursed. If an empty cell had a possibility…

That doesn't seem any different than the algorithm my solver uses. From what a sibling poster commented, it looks like the thing that causes the trouble is that the square that makes it unsolvable basically lets you solve it down to just that square in many different ways, which then just ends up with you enumerating an absolutely enormous state space because the solvers don't have enough tricks built in to recognize it as an unsolvable board from the start.

Re: Solving Every Sudoku Puzzle (2006)

#100

Post by lostcolony »

war1025 wrote: post #99
lostcolony wrote: post #97

Earlier quoted context omitted.

Yeah; the one I implemented used a different algorithm, and would have noted that there was no solution. I basically just kept a "possibility space" for each empty cell (containing a list of all possible values it could be), started with the one with the smallest size > 0, tried a value as 'true', removed that possible value from all related cells (same row, column, 3x3), recursed. If an empty cell had a possibility…

That doesn't seem any different than the algorithm my solver uses. From what a sibling poster commented, it looks like the thing that causes the trouble is that the square that makes it unsolvable basically lets you solve it down to just that square in many different ways, which then just ends up with you enumerating an absolutely enormous state space because the solvers don't have enough tricks built in to recognize…

Right; I am saying it's different than the original post's because it -could- handle unsolvable boards (maybe I misread; it sounded like that was an unhandled case in it).

I knew that there could be degenerate cases like that that would cause it to take O(n!) time, but the ones that I ran into still didn't take -that- long, which was what surprised me.

Post reply on HN