On: Zero-Knowledge Sudoku: Verifying solution without looking at it.

"When one says Sudoku is NP-complete, one should keep in mind that this refers only to an unusual type of Sudoku puzzle in which there might be multiple solutions."

http://11011110.livejournal.com/23221.html