3,000,000 Queens in less than one minute

✍ Scribed by Sosic, Rok; Gu, Jun

• Book ID: 120601925
• Publisher: Association for Computing Machinery
• Year: 1991
• Weight: 250 KB
• Volume: 2
• Category: Article
• ISSN: 0163-5719
• DOI: 10.1145/122319.122325

✦ Synopsis

The
n

• queens problem is a classical combinatorial search problem. In this paper we give a linear time algorithm for this problem. The algorithm is an extension of one of our previous local search algorithms [3, 4, 6]. On an IBM RS 6000 computer, this algorithm is capable of solving problems with 3,000,000 queens in approximately 55 seconds.