带有预定义皇后的 N 皇后
N Queen with predefined queen(s)
最初的 N 皇后问题是关于在 N*N 棋盘上放置 N 个皇后。
然而，我的一位学术朋友对我提出了质疑：
有预定义皇后的 N 皇后问题的 NP 完备性证明吗？
定义为：
假设：
N = 8,
棋盘已经在 (0,0)、(2,7)、(7,4) 上放置了 3 个皇后。
问题：
是否有任何多项式算法可以知道电路板是否有解？
或者上面问题最快的算法？
附录：
- 由于预定义的皇后，显式解决方案将不起作用。
An Image Example Link
非常感谢您的帮助。非常感谢！
是的。
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.
最初的 N 皇后问题是关于在 N*N 棋盘上放置 N 个皇后。
然而，我的一位学术朋友对我提出了质疑：
有预定义皇后的 N 皇后问题的 NP 完备性证明吗？
定义为：
假设：
N = 8,
棋盘已经在 (0,0)、(2,7)、(7,4) 上放置了 3 个皇后。
问题：
是否有任何多项式算法可以知道电路板是否有解？
或者上面问题最快的算法？
附录：
- 由于预定义的皇后，显式解决方案将不起作用。
An Image Example Link
非常感谢您的帮助。非常感谢！
是的。
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.