71–80 of 101 posts
Wrote a solver using basically the same idea back in college. Was kind of fun. Probably some stupid things in there that I would do differently now with more experience. https://github.com/war1025/sudoku-solver/blob/master/Sudoku/...
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.)
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.
That's exactly why I call it naive TDD, and not a failing of TDD in general. Jeffries deserves credit for making it public.
It is just 81 vars constrained to be 1..9 and then twenty-seven applications of the Pigeonhole principle.
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.
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 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.
In most easy / medium puzzles, there are actually no points where you need to guess (i.e. recurse down the tree).
In many hard puzzles, there are only one of two guesses, which is where you would recurse down the decision tree.
Things get a bit more intense once you move into the puzzles specifically designed to be a pain in the neck for programs, but often those inputs aren't actually valid Sudoku puzzles.
A lot of people here have built solvers. What about Sudoku generators?
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
I know someone who likes to create a fractal generator when learning a new language. He says it gives you a bit of exposure to the strengths of quirks in the language from implementing algorithms, working with data structures, and displaying a GUI to render an image to screen.