数独 np 是如何完成的？
how is sudoku np-complete?
数独怎么是np完全问题？根据 wiki，要归类为 np-complete 问题，它必须满足 2 个条件
- 问题一定出在 np
- np 中的所有其他问题都必须可以在多项式时间内归结为给定问题
第二个条件是怎么满足的？能给我举个例子吗？例如，我看不出数独问题与旅行商问题或背包问题之间有任何关联
（请原谅我在移动设备上输入此问题时格式不当）
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 论文的 link。
数独怎么是np完全问题？根据 wiki，要归类为 np-complete 问题，它必须满足 2 个条件
- 问题一定出在 np
- np 中的所有其他问题都必须可以在多项式时间内归结为给定问题
第二个条件是怎么满足的？能给我举个例子吗？例如，我看不出数独问题与旅行商问题或背包问题之间有任何关联
（请原谅我在移动设备上输入此问题时格式不当）
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 论文的 link。