sudoku - 数独如何np完全？

Question

数独如何成为 np 完全问题？根据 wiki，要被归类为 np 完全问题，它必须满足 2 个条件

1. 问题必须在 np 中
2. np 中的所有其他问题都必须可以在多项式时间内还原为给定问题

第二个条件如何满足？你能给个例子吗？例如，我没有看到数独问题和旅行商问题或背包问题之间有任何关联

(请原谅我在移动设备上输入此问题时格式不当)

Answer 1

NP-completeness of SUDOKU部分注释:

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 PDF 格式论文的链接。