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 othe

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.