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

Question

最初的 N-Queen 问题是关于在 N*N 棋盘上放置 N 个皇后。

然而，我却被一位学界 friend 质疑:

有预定义皇后的 N 皇后问题的 NP 完备性证明吗？

定义是:

假设:

1. N = 8，

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

问题:

1. 是否有任何多项式算法可以知道棋盘有/没有解？

2. 或者上述问题最快的算法？

附录:

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

An Image Example Link

非常感谢您的帮助。非常感谢!

Answer 1

是的。

Complexity of n-Queens Completion

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

Ian P. Gent

Christopher Jefferson

Peter Nightingale

Abstract

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.