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)
by jkaptur on Wednesday September 04, 2019 @04:41PM
(#20881202)
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.
Re:Solving Every Sudoku Puzzle (2006)
by war1025 on Wednesday September 04, 2019 @11:26PM
(#20883617)
The 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.
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.
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.