We all know what Sudoku is. Given a Sudoku puzzle, one can use a simple recursive procedure to solve it using a computer. Before describing the algorithm, we make some definitions.
A partial solution is a Sudoku puzzle with only some of the numbers entered.
Given an empty square in a partial solution, an assignment of a digit to the square is consistent if it doesn't appear in the same row, column or $3\times 3$ square.
The algorithm is as follows:
- If there is any square for which there is no consistent assignment, give up.
- Otherwise, pick an empty square $S$ (*).
- Calculate the set of all consistent assignments $A$ to this square.
- Go over all assignments $a \in A$ in some order (**):
- Put $a$ in $S$, and recurse.
We have two degrees of freedom: choosing an empty square, and choosing and order for the assignments to the square. In practice, it seems that whatever the choice is, the algorithm reaches a solution very fast.
Suppose we give the algorithm a partial Sudoku with a unique solution. Can we bound the number of steps the algorithm takes to find the solution?
To make life easier, you can choose any rule you wish for ( * ) and (**), even a random rule (in that case, the relevant quantity is probably the expectation); any analyzable choice would be interesting.
Also, if it helps, you can assume something about the input – say at least $X$ squares are filled in. I'm also willing to relax the restriction that there be a unique solution – indeed, even given an empty board, the algorithm above finds a complete Sudoku very fast. Analyzes for random inputs (in whatever meaningful sense) are also welcome.
Best Answer
Since Sudoku is known to be NP-complete for arbitrarily large grid sizes, it's highly unlikely that your algorithm has any 'good' bound. As to why it works so well, I suspect the reason is simply that Sudoku puzzles are designed to be cleanly solved by humans; humans in general are really mediocre at backtracking searches (particularly once the depth gets to more than a small handful of steps), so most human Sudoku puzzles in fact have nearly-linear solutions with very little branching needed, just because those make for more interesting puzzles.