# How many steps does it take the computer to solve a Sudoku puzzle?

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.

-
I don't see any difference between a "Sudoku puzzle" and a "partial solution": in both cases we have some unfilled squares and there is a unique way to complete them subject to the rules of Sudoku. Am I missing something? – Pete L. Clark Apr 9 '11 at 21:34
I believe a sudoku puzzle (under this definition) has a solution, but a "partial solution" might not be able to be completed. (Technically, a Sudoku puzzle is supposed to have only one completion, but the poster here seems to allow for multiple.) – Thomas Andrews Apr 9 '11 at 22:33
We can certainly bound it by 9^Y where Y is the number of unfilled squares ;). – JSchlather Apr 9 '11 at 23:14
@Pete: There's no difference, it's just to emphasize that some of the squares may be empty. – Yuval Filmus Apr 9 '11 at 23:31
@yuval, what do you mean by "fast"? are you measuring time or steps? – picakhu Apr 10 '11 at 0:01

 Being NP-Complete for arbitrary ${n^2}\times{n^2}$ puzzles doesn't much affect the question for a particular $n=3.$ We could, with enough memory, create a lookup table of the $9^81$ partials and find out if there is a solution to a particular partial in relatively brief time, assuming we had that much memory. – Thomas Andrews Apr 10 '11 at 5:39