[Computational Complexity] Sudoku Revisited
Robin Houston writes
Although I'm not a complexity theorist, I very much enjoy reading your weblog. I also enjoy solving the Sudoku puzzles published in the British press, so it was doubly nice to see your May 25 post about the complexity of Sudoku!Good question. Since Yato's reductions preserve solutions the problem is equivalent to finding a satisfying assignment of a Boolean formula that has exactly one satisfying assignment (Unique SAT).
As far as I can tell, it follows from Yato's work that the problem:
Given a partially completed grid, find a valid completion if
there is one; otherwise report that there isn't one.
is solvable in polynomial time iff P=NP.
That's interesting of course, and it's a problem that faces those who set the puzzles; but the problem that we solvers are faced with is not quite (1). It's:
- Given a partially completed grid that has a unique valid completion, find that completion.
We don't know if Unique SAT is NP-complete in the traditional sense. However Valiant and Vazirani have a nice paper that shows how to randomly reduce SAT to Unique SAT. Putting it together we get the following equivalence:
- Given a partially completed grid that has a unique valid completion, probabilistically find that completion in polynomial time.
- NP=RP (i.e. all NP problems have efficient probabilistic solutions).
Posted by Lance to Computational Complexity at 8/11/2005 07:33:00 AM
- Given a partially completed grid, find a valid completion if there is one; otherwise report that there isn't one.