Finding First and Most-Beautiful Queens by Integer Programming
From MaRDI portal
Publication:6322346
DOI10.1007/978-3-319-93031-2_16arXiv1907.08246MaRDI QIDQ6322346FDOQ6322346
Authors: Matteo Fischetti, Domenico Salvagnin 
Publication date: 18 July 2019
Abstract: The n-queens puzzle is a well-known combinatorial problem that requires to place n queens on an n x 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 <= 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. One of the proposed algorithms is a pure cutting plane method based on a combinatorial variant of classical Gomory cuts. We also address an intriguing "lexicographic bottleneck" (or min-max) variant of the problem that requires finding a most beautiful (in a well defined sense) placement, and report its solution for n up to 176.
This page was built for publication: Finding First and Most-Beautiful Queens by Integer Programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6322346)
