IBM Journal of Research and Development
IBM Skip to main content
  Home     Products & services     Support & downloads     My account  

  Select a country  
Journals Home  
  Systems Journal  
Journal of Research
and Development
    Current Issue  
    Recent Issues  
    Papers in Progress  
    Recent publications  
    Author's Guide  
  Contact Us  
  Related links:  
     IBM Research  

IBM Journal of Research and Development  
Volume 31, Number 4, Page 464 (1987)
Aspects of Computer Performance
  Full article: arrowPDF   arrowCopyright info


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

by H. S. Stone, J. M. Stone
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.
Related Subjects: Algorithms; Checkers and chess; Game theory; Performance analysis