Advertisement
Published in:
2018 | OriginalPaper | Chapter
Chasing First Queens by Integer Programming
Authors : Matteo Fischetti, Domenico Salvagnin
Published in: Integration of Constraint Programming, Artificial Intelligence, and Operations Research
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
The n-queens puzzle is a well-known combinatorial problem that requires to place n queens on an \(n\times n\) chessboard so that no two queens can attack each other. Since the 19th century, this problem was studied by many mathematicians and computer scientists. While finding any solution to the n-queens puzzle is rather straightforward, it is very challenging to find the lexicographically first (or smallest) feasible solution. Solutions for this type are known in the literature for \(n\le 55\), while for some larger chessboards only partial solutions are known. The present paper was motivated by the question of whether Integer Linear Programming (ILP) can be used to compute solutions for some open instances. We describe alternative ILP-based solution approaches, and show that they are indeed able to compute (sometimes in unexpectedly-short computing times) many new lexicographically optimal solutions for n ranging from 56 to 115.