how is sudoku np-complete?

Question

how is Sudoku an np-complete problem? according to wiki, to be classed as an np-complete problem it must satisfy 2 conditions

1. problem must be in np
2. every other problem in np must be reducible to given problem in polynomial time

how is the second condition satisfied? can you give an example? for instance, I don't see any correlation between Sudoku problem and the travelling salesman problem or knapsack problem

(kindly forgive poor formatting as I'm typing this question on my mobile device)

Scow

This would probably be a better question for Computer Science, and is probably going to be closed as off-topic, but basically, there is a polynomial-time reduction from the Latin Square Completion problem (you can see that reduction here) which has a polynomial-time reduction from SAT. You can reduce any NP problem to SAT, and, since you can solve SAT by solving Latin Square Completion and you can solve Latin Square Completion by solving Sudoku, you can solve any NP problem by solving Sudoku. – Moorhead

Answer 1

NP-completeness of SUDOKU notes in part:

This result was first shown in this master’s thesis by reduction from the NP-complete problem LATIN SQUARE COMPLETION. Sudoku wikipedia page.

Here is how it works (simplified, without reference to ASP-completeness, which I don’t cover in this course).

Suppose we have a n×n instance of LATIN SQUARE COMPLETION. We construct a n2×n2 instance of SUDOKU, that encodes the instance of LATIN SQUARE COMPLETION. Moreover, the encoding is very direct.

http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/MasterThesis.pdf being a link to the thesis in PDF.

Hospitalize