An Almost Perfect Heuristic for the N-queens Problem

Laxmikant Vasudeo Kale

Information Processing Letters (Information Processing Letters) 1990

Pulication Type: Paper

Download: pdf ps

Abstract

We present a heuristic technique for finding solutions to the N nonattacking queens problem that is almost perfect in the sense that it finds a first solution without any backtracks in most cases. In addition to previously known variable-ordering heuristics and their extensions, it uses a value-ordering heuristic, which contributes dramatically to its success. Using these heuristics, solutions have been found for all values of N between 4 and 1000.

Research Areas

Text Ref

L.V. Kale, "An Almost Perfect Heuristic or the N-queens Problem",
Information Processing Letters, Publ: North Holland, vol. 34, pp. 173-178,
April 1990.

BibTex

@ARTICLE{HeuristicNQueenIPL90,
  author = "L.V. Kal{\`e}",
  title = "An Almost Perfect Heuristic or the {N}-queens Problem",
  journal = "Information Processing Letters",
  publisher = "North Holland",
  volume = 34,
  number = 4, 
  pages = "173-178",
  month = "April",
  year = "1990",
  annote = "90-7",
  group = Y,
}