An almost perfect heuristic for the N nonattacking queens problem

Research output: Contribution to journalArticlepeer-review

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.

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

Keywords

  • Combinatorial problems
  • N queens
  • backtracking
  • heuristic search

ASJC Scopus subject areas

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

Fingerprint

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

Cite this