Efficient search techniques—An empirical study of the N-Queens Problem

Abstract

This paper investigates the cost of finding the first solution to the N-Queens Problem using various backtrack search strategies. Among the empirical results obtained are the following: 1) To find the first solution to the N-Queens Problem using lexicographic backtracking requires a time that grows exponentially with increasing values of N. 2) For most even values of N < 30, search time can be reduced by a factor from 2 to 70 by searching lexicographically for a solution to the N+1-Queens Problem. 3) By reordering the search so that the queen placed next is the queen with the fewest possible moves to make, it is possible to find solutions very quickly for all N < 97, improving running time by dozens of orders of magnitude over lexicographic backtrack search. To estimate the improvement, we present an algorithm that is a variant of algorithms of Knuth and Purdom for estimating the size of the unvisited portion of a tree from the statistics of the visited portion.