An almost perfect heuristic for the N nonattacking queens problem

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)173-178
Number of pages6
JournalInformation Processing Letters
Issue number4
StatePublished - Apr 24 1990


  • Combinatorial problems
  • N queens
  • backtracking
  • heuristic search

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


Dive into the research topics of 'An almost perfect heuristic for the N nonattacking queens problem'. Together they form a unique fingerprint.

Cite this