Complexity of n-Queens Completion
Complexity of n-Queens Completion
复制标题
DOI：
10.1613/jair.5512
复制
发表时间：
2017-01-01
影响因子：
5
通讯作者：
Nightingale, Peter
中科院分区：
文献类型：
--
作者：
Gent, Ian P.;Jefferson, Christopher;Nightingale, Peter
N-Queens的问题是将N国际象棋皇后放在N的N棋盘上，以便没有两个皇后在同一行，列或对角线上。 N-Queens的完成问题是一种变体，可追溯到1850年，其中已经放置了一些皇后，并要求求解器放置其余的（如果可能）。我们表明，N-Queens的完成既是NP完整的，又是＃P-Complete。推论的是，皇后区的任何非攻击安排都可以作为较大N- Queens问题解决方案的一部分。我们介绍了N-Queens完成的随机实例的生成器，以及密切相关的n-Queens和排除的对角线问题。我们描述了这些问题的三个求解器，并经验分析了随机生成的实例的硬度。对于被阻塞的N-Queens和排除的对角线问题，我们显示了与硬实例相关的相变的存在，如在其他NP完整问题中所见，但是N-Queens完成的天然生成器并没有产生始终如一的硬实例。这项工作的意义在于，N- Queens问题已被广泛用作人工智能的基准，但是由于决策问题的简单复杂性，因此结论通常是有争议的。我们的结果提供了理论上和经验上很难的替代基准，但是针对N-Queens设计的解决技术需要最小或没有变化。
The n-Queens problem is to place n chess queens on an n by n chessboard so that no two queens are on the same row, column or diagonal. The n-Queens Completion problem is a variant, dating to 1850, in which some queens are already placed and the solver is asked to place the rest, if possible. We show that n-Queens Completion is both NP-Complete and #P-Complete. A corollary is that any non-attacking arrangement of queens can be included as a part of a solution to a larger n-Queens problem. We introduce generators of random instances for n-Queens Completion and the closely related Blocked n-Queens and Excluded Diagonals Problem. We describe three solvers for these problems, and empirically analyse the hardness of randomly generated instances. For Blocked n-Queens and the Excluded Diagonals Problem, we show the existence of a phase transition associated with hard instances as has been seen in other NP-Complete problems, but a natural generator for n-Queens Completion did not generate consistently hard instances. The significance of this work is that the n-Queens problem has been very widely used as a benchmark in Artificial Intelligence, but conclusions on it are often disputable because of the simple complexity of the decision problem. Our results give alternative benchmarks which are hard theoretically and empirically, but for which solving techniques designed for n-Queens need minimal or no change.