algorithm - N 个带有预定义皇后的皇后

Question

起源 N-Queen 问题是关于在 N*N 板上放置 N 个皇后。

然而，我的一位学术朋友向我提问：

有预定义皇后的 N Queen 问题的任何 NP 完全性证明吗？

定义是：

假设：

1. N = 8,

2. 棋盘已经在 (0,0), (2,7), (7,4) 放置了 3 个皇后。

问题：

1. 是否有任何多项式算法可以知道董事会是否有/没有解决方案？

2. 还是上述问题上最快的算法？

附录：

1. 由于预定义的皇后，显式解决方案将不起作用。

图像示例链接

您的帮助将不胜感激。非常感谢！

标签： algorithmnpn-queens

Answer 1

是的。

n-Queens 完成的复杂性

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

伊恩·P·根特

克里斯托弗·杰斐逊

彼得·南丁格尔

抽象的

n-Queens 问题是将 n 个棋后放置在 n × n 棋盘上，这样没有两个皇后在同一行、同一列或同一对角线上。n-Queens Completion 问题是一个变体，可以追溯到 1850 年，其中已经放置了一些皇后，并且如果可能的话，要求求解者放置其余的。我们证明 n-Queens Completion 既是 NP-Complete 又是#P-Complete。一个推论是任何非攻击性的皇后排列都可以作为解决更大的 n 皇后问题的一部分。我们为 n-Queens Completion 和密切相关的 Blocked n-Queens and Excluded Diagonals Problem 介绍了随机实例的生成器。我们针对这些问题描述了三个求解器，并根据经验分析了随机生成实例的难度。对于阻塞的 n-Queens 和排除对角线问题，我们展示了与硬实例相关的相变的存在，正如在其他 NP-Complete 问题中所看到的那样，但是 n-Queens Completion 的自然生成器并没有生成始终如一的硬实例。这项工作的意义在于 n-Queens 问题已被非常广泛地用作人工智能中的基准，但由于决策问题的简单复杂性，关于它的结论往往是有争议的。我们的结果给出了替代基准，这些基准在理论上和经验上都很难，但为 n-Queens 设计的求解技术需要很少或不需要更改。这项工作的意义在于 n-Queens 问题已被非常广泛地用作人工智能中的基准，但由于决策问题的简单复杂性，关于它的结论往往是有争议的。我们的结果给出了替代基准，这些基准在理论上和经验上都很难，但为 n-Queens 设计的求解技术需要很少或不需要更改。这项工作的意义在于 n-Queens 问题已被非常广泛地用作人工智能中的基准，但由于决策问题的简单复杂性，关于它的结论往往是有争议的。我们的结果给出了替代基准，这些基准在理论上和经验上都很难，但为 n-Queens 设计的求解技术需要很少或不需要更改。