188宝金博页面版

Journal of Artif i cial Intelligence Research 59 (2017) 815 – 848 Submitted 03/17; published 08/17Complexity of n-Queens CompletionIan P. Gent ian.gent@st-andrews.ac.ukChristopher Jef f erson caj21@st-andrews.ac.ukPeter Nightingale pwn1@st-andrews.ac.ukSchool of Computer Science, University of St Andrews,St Andrews, Fife KY16 9SX, UKAbstractThe n-Queens problem is to place n chess queens on an n by n chessboard so that notwo queens are on the same row, column or diagonal. The n-Queens Completion problem isa variant, dating to 1850, in which some queens are already placed and the solver is askedto place the rest, if possible. We show that n-Queens Completion is both NP-Completeand #P-Complete. A corollary is that any non-attacking arrangement of queens can beincluded as a part of a solution to a larger n-Queens problem. We introduce generators ofrandom instances for n-Queens Completion and the closely related Blocked n-Queens andExcluded Diagonals Problem. We describe three solvers for these problems, and empiricallyanalyse the hardness of randomly generated instances. For Blocked n-Queens and theExcluded Diagonals Problem, we show the existence of a phase transition associated withhard instances as has been seen in other NP-Complete problems, but a natural generator forn-Queens Completion did not generate consistently hard instances. The signif i cance of thiswork is that the n-Queens problem has been very widely used as a benchmark in Artif i cialIntelligence, but conclusions on it are often disputable because of the simple complexity ofthe decision problem. Our results give alternative benchmarks which are hard theoreticallyand empirically, but for which solving techniques designed for n-Queens need minimal orno change.1. IntroductionThe n-Queens problem is to place n chess queens on an n by n chessboard so that notwo queens are on the same row, column or diagonal. This puzzle dates to 1848, andonly two years later a variant was introduced by Nauck (1850) in which some number ofqueens are pre-placed and the solver is asked to place the rest, if possible. This is the n-Queens Completion problem and Figure 1 shows the f i rst known instance studied. We willshow that the n-Queens Completion problem is NP-Complete and #P-Complete, discusssolvers for the problem, and empirically analyse randomly generated instances. The n-Queens Completion problem may be one of the simplest NP-Complete problems to explainto people who understand the rules of chess. The problem is “Given an n × n chessboardon which some queens are already placed, can you place a queen in every remaining row sothat no two queens attack each other?”The n-Queens problem has an extraordinary history for such an apparently unassum-ing problem, both generally and inside Artif i cial Intelligence. Formerly, and incorrectly,attributed to Gauss, the problem’s history was clarif i ed by Campbell (1977). The 8-Queensproblem was introduced by Bezzel (1848) and by Nauck (1850) (possibly independently).The latter publication attracted the interest of Gauss, who even made a small mistake inc ?2017 AI Access Foundation. All rights reserved.