sudoku np如何完整? [英] how is sudoku np-complete?

问题描述

数独如何成为np完全问题?根据Wiki的规定，要归类为np完全问题，必须满足2个条件

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

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

第二个条件如何满足?你能给个例子吗?例如，我看不出数独问题和旅行推销员问题或背包问题之间的相关性

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)

推荐答案

该结果首先在本硕士论文中以减少 NP完全问题拉丁方完成.数独维基百科 页.

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

这是它的工作方式(简化，不参考 ASP完整性，这是我不会在本课程中介绍的内容.

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

假设我们有一个n×n的拉丁方补全实例.我们 构造SUDOKU的n2×n2实例，该实例对的实例进行编码 拉丁广场完成.而且，编码非常直接.

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.su-tokyo.ac.jp/~yato/data2/MasterThesis.pdf 是PDF论文的链接.

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

这篇关于sudoku np如何完整?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！