3 ms·

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 ge

• war1025 7y ago
  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.