## [Computational Complexity] Sudoku Revisited

Expand Messages
• 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
Message 1 of 1 , Aug 11, 2005
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!

As far as I can tell, it follows from Yato's work that the problem:

1. 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:

2. Given a partially completed grid that has a unique valid completion, find that completion.

Can anything be said about problem (2)? If there were a polynomial- time algorithm for (2), would it follow that P=NP? If not, would there be any other significant consequences for complexity theory?

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).

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).
Since we don't believe that NP has fast probabilistic algorithms, we expect that there are no efficient procedures to completing a generalized Sudoku grid, even if there is only one such completion.

--
Posted by Lance to Computational Complexity at 8/11/2005 07:33:00 AM

Your message has been successfully submitted and would be delivered to recipients shortly.