N女王与预定义的女王

Question

起源N-Queen问题是将N Queens放在N * N板上。

但是，我的一位学术朋友向我提问：

对于具有预定义女王的N Queen问题，是否有任何NP完整性证明？

定义是：

假设：

1. N = 8，
2. 董事会已经在（0,0），（2,7），（7,4）上放置了3个女王。

题：

1. 是否有任何多项式算法可以知道电路板是否有/没有解决方案？
2. 或者上述问题的最快算法？

附录：

1. 由于预定义的女王，显式解决方案无效。

An Image Example Link

非常感谢您的帮助。非常感谢你！

Answer 1

是。

n-Queens完成的复杂性

DOI https://doi.org/10.1613/jair.5512

伊恩P.根特

克里斯托弗杰斐逊

彼得南丁格尔

抽象

n-Queens问题是将n个国际象棋皇后放在n个棋盘上，这样就不会有两个皇后在同一行，列或对角线上。 n-Queens完成问题是一个变体，可追溯到1850年，其中已经放置了一些皇后，并且如果可能的话，要求解算器放置其余的。我们证明n-Queens完成既是NP-Complete又是#P-Complete。一个必然结果是，任何非攻击性的皇后安排都可以作为更大的n-Queens问题解决方案的一部分。我们介绍了n-Queens完成的随机实例的生成器以及密切相关的阻塞n-Queens和Excluded Diagonals问题。我们描述了这些问题的三个解算器，并凭经验分析随机生成的实例的硬度。对于阻塞的n-Queens和排除的对角线问题，我们显示存在与其他NP-Complete问题中所见的硬实例相关的相变，但是n-Queens完成的自然生成器不会生成一致的硬实例。这项工作的重要性在于，n-Queens问题已被广泛用作人工智能的基准，但由于决策问题的简单复杂性，对其的结论通常是有争议的。我们的结果给出了理论上和经验上都很难的替代基准，但是针对n-Queens设计的求解技术需要很少或没有变化。