Projects per year
Abstract
The nQueens 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 nQueens 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 nQueens Completion is both NPComplete and #PComplete. A corollary is that any nonattacking arrangement of queens can be included as a part of a solution to a larger nQueens problem. We introduce generators of random instances for nQueens Completion and the closely related Blocked nQueens and Excluded Diagonals Problem. We describe three solvers for these problems, and empirically analyse the hardness of randomly generated instances. For Blocked nQueens and the Excluded Diagonals Problem, we show the existence of a phase transition associated with hard instances as has been seen in other NPComplete problems, but a natural generator for nQueens Completion did not generate consistently hard instances. The significance of this work is that the nQueens 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 nQueens need minimal or no change.
Original language  English 

Pages (fromto)  815848 
Number of pages  34 
Journal  Journal of Artificial Intelligence Research 
Volume  59 
DOIs  
Publication status  Published  30 Aug 2017 
Keywords
 Constraint satisfaction problem
 Constraint programming
 Formal methods
Fingerprint
Dive into the research topics of 'Complexity of nQueens Completion'. Together they form a unique fingerprint.Projects
 2 Finished

Combining Constraints and Verification: Combining Constraints and Verification
Jefferson, C. A. (PI)
31/07/14 → 30/07/17
Project: Standard

University Research Fellowship 2013: University Research Fellowship 2013
Jefferson, C. A. (PI)
1/10/13 → 30/09/18
Project: Fellowship