Take the 2-minute tour ×

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.

share|improve this question
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

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
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

Your Answer


