I'm turning over in my mind a Sudoku solver at the moment. My naive algorithm is this:
For each cell, determine the set of possible digits it can contain. At the end of this scan, if there are 'easy' cells (with only one possible solution), fill these in and re-scan the grid until there are no more easy cells. Take the cell with the smallest number of solutions and try the first. Continue scanning until either the grid is complete or we encounter a cell with no possible solutions. In this case, backtrack to the faulty decision and choose the next alternative solution. If there are no remaining alternative solutions, the puzzle is invalid.
This is rather unsatisfying, though; is there a more elegant procedure?
That sounds like exactly the recursive solver algorithm used in Solo. I actually have two solvers embedded in the program: that one, and a non-recursive one supporting all the reasoning techniques I know of short of guesswork. The non-recursive one is used to gauge the difficulty of a puzzle so that I can be sure of not accidentally setting one that requires recursive (guessing/backtracking) reasoning. But precisely because of this (and by design), the non-recursive solver cannot solve all puzzles that have a unique solution, while the recursive one can in principle.
I use the recursive solver to generate a filled grid to begin with (if you feed it no clues at all, randomise its choice of next square if there are more than one with the same smallest number of solutions, and randomise the order in which it works through the solutions for each square, then it will generate a random filled grid from nothing), and also to check solubility when deliberately generating Unreasonable-level (backtracking required) puzzles. I use the non-recursive solver to check solubility at all other levels.
I see what you mean about it being unsatisfying - certainly when I was told about this as a viable grid generation algorithm I felt disappointment because I'd been hoping for something much more interestingly combinatorial - but on reflection it's quite a clever recursive algorithm, because of the way it avoids running through all 10^23-odd possible filled grids. By always selecting the most constrained square to recurse into next, it prunes the search tree early and often, and thereby ends up running quite a lot faster than a more naive recursive approach.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
For each cell, determine the set of possible digits it can contain.
At the end of this scan, if there are 'easy' cells (with only one possible solution), fill these in and re-scan the grid until there are no more easy cells.
Take the cell with the smallest number of solutions and try the first. Continue scanning until either the grid is complete or we encounter a cell with no possible solutions. In this case, backtrack to the faulty decision and choose the next alternative solution. If there are no remaining alternative solutions, the puzzle is invalid.
This is rather unsatisfying, though; is there a more elegant procedure?
I use the recursive solver to generate a filled grid to begin with (if you feed it no clues at all, randomise its choice of next square if there are more than one with the same smallest number of solutions, and randomise the order in which it works through the solutions for each square, then it will generate a random filled grid from nothing), and also to check solubility when deliberately generating Unreasonable-level (backtracking required) puzzles. I use the non-recursive solver to check solubility at all other levels.
I see what you mean about it being unsatisfying - certainly when I was told about this as a viable grid generation algorithm I felt disappointment because I'd been hoping for something much more interestingly combinatorial - but on reflection it's quite a clever recursive algorithm, because of the way it avoids running through all 10^23-odd possible filled grids. By always selecting the most constrained square to recurse into next, it prunes the search tree early and often, and thereby ends up running quite a lot faster than a more naive recursive approach.