Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
2  
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
show 4 more comments

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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.