  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.
