3 ms·
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
by skizm 7y ago
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 efficient, ways to write sudoku solvers, but the simplicity and clarity the DFS solver offers is pretty cool IMO.
- jkaptur 7y agoI 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.
- war1025 7y agoThe constraint propagation bit is the main key. It still ends up being a DFS, but at most steps along the way, finding one number leads causally to several other spaces being found. 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.
- 53x15 7y agoIt 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 https://t-dillon.github.io/tdoku
- antod 7y agoI'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.
- zwkrt 7y agoThere 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.
- zwkrt 7y agoMore info: https://puzzling.stackexchange.com/questions/12/are-there-published-sudoku-puzzles-that-require-guessing https://puzzling.stackexchange.com/questions/12/are-there-pu...