6
$\begingroup$

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.

  • 3
    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?2011-04-09
  • 0
    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.)2011-04-09
  • 0
    We can certainly bound it by 9^Y where Y is the number of unfilled squares ;).2011-04-09
  • 0
    @Pete: There's no difference, it's just to emphasize that some of the squares may be empty.2011-04-09
  • 0
    @yuval, what do you mean by "fast"? are you measuring time or steps?2011-04-10
  • 0
    @picakhu: it's the same thing (up to a constant).2011-04-10
  • 0
    @Yuval, I meant to say that perhaps the computer is what is fast and may not be detected, but that is probably not what you intended in your question, how many steps did it take you on average, and in the worst case?2011-04-10
  • 0
    @picakhu: I don't remember the exact figures, but 100s of steps seems typical; you can look at bwkaplan's link, though it's a different algorithm. The point is that the search space is huge, and going over all of it would certainly take lots of time...2011-04-10
  • 0
    @Yuval, I looked through that page, it would be nice if you could do that type of analysis on your method too, perhaps your answer will pop out that way. i.e. create random puzzles and solve them.2011-04-10

1 Answers 1

3

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.

  • 0
    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.2011-04-10