pith. sign in

arxiv: 1907.08246 · v1 · pith:J36DLLZ7new · submitted 2019-07-18 · 💻 cs.DS · cs.DM· math.CO· math.OC

Finding First and Most-Beautiful Queens by Integer Programming

Matteo Fischetti , Domenico Salvagnin This is my paper

Pith reviewed 2026-05-24 19:16 UTC · model grok-4.3

classification 💻 cs.DS cs.DMmath.COmath.OC
keywords n-queensinteger linear programminglexicographic optimizationcutting planescombinatorial optimizationGomory cuts
0
0 comments X

The pith

Integer linear programming computes the lexicographically first n-queens placements for n from 56 to 115.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper applies integer linear programming to the classic n-queens problem of placing n non-attacking queens on an n by n board. It focuses on the hard variant of finding the lexicographically smallest solution, which had only been solved up to n=55. The authors test several ILP formulations and show they produce new optimal solutions for many larger boards. They also solve a related min-max version that seeks the most balanced placement under a specific ordering criterion.

Core claim

Integer linear programming formulations of the n-queens non-attacking constraints, solved via commercial solvers with branching and a combinatorial variant of Gomory cuts, yield many new lexicographically optimal solutions for n between 56 and 115 and solve the lexicographic bottleneck variant up to n=176.

What carries the argument

ILP model of non-attacking queen constraints together with cutting planes and branching rules that the solver uses to certify lex-minimal solutions.

If this is right

  • Solutions for n=56 to 115 are now known and certified optimal.
  • The min-max variant is solved for all n up to 176.
  • A pure cutting-plane algorithm based on combinatorial Gomory cuts works for this problem.
  • ILP can close previously open instances of the lex-first n-queens problem.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same modeling approach may extend to other lex-optimization tasks on placement or permutation problems.
  • Further scaling could be tested by increasing solver time limits or adding symmetry-breaking constraints.
  • If the method works here, it may apply to related chess-piece placement problems with ordering objectives.

Load-bearing premise

The chosen ILP encoding plus the solver's branching and cut rules are enough to prove global optimality on these instances without numerical problems or incomplete search.

What would settle it

Discovery of any lexicographically smaller valid placement for an n in 56-115 that the reported ILP runs did not find.

Figures

Figures reproduced from arXiv: 1907.08246 by Domenico Salvagnin, Matteo Fischetti.

Figure 1
Figure 1. Figure 1: Lexicographically optimal solution for n = 10. A compact way to represent a feasible solution is to use a permutation π = (π1, . . . , πn) of the integers 1, . . . , n defined as follows: πi := Xn j=1 j xij , i = 1, . . . , n. (2) Among all permutations π that correspond to a feasible x, we then look for the lexicographically smallest one. For example, the lex-optimal solution for n = 10, depicted in [PIT… view at source ↗
Figure 2
Figure 2. Figure 2: Three different families of clique cuts for [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Example of odd-cycle inequality for n-queens: no more than two of the five positions can be occupied by a queen. 3 Solution methods We next describe the solution algorithms that we implemented. 3.1 Using a Constraint Programming solver The n-queens puzzle can be easily modeled as a Constraint Programming (CP) problem. Indeed, working directly on the variables πi , the puzzle can be formulated by just three… view at source ↗
Figure 4
Figure 4. Figure 4: Most beautiful n-queens costs and a feasible (actually, optimal) arrangement for n = 6, with fingerprint (34, 34, 26, 26, 10, 10). 5 Most-beautiful queens In the most-beautiful version of the n-queens problem, each blackboard cell (i, j) has a cost defined as dij = (2i − n − 1)2 + (2j − n − 1)2 that gives (4 times the squared) distance of cell (i, j) from the center of the blackboard, for i, j = 1, . . . ,… view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper formulates the n-queens problem as 0-1 integer programs to find the lexicographically smallest feasible placement and a lexicographic-bottleneck (min-max) variant. It reports that standard MIP solvers and a custom pure cutting-plane algorithm using combinatorial Gomory cuts compute and certify new lex-optimal solutions for all n from 56 to 115 and bottleneck solutions up to n=176.

Significance. If the reported optimality certificates hold, the work extends the known solution table for these variants of the classic n-queens problem and supplies concrete evidence that polynomially sized ILP models plus combinatorially derived cuts can close previously open instances at moderate computational cost. The pure cutting-plane result is of independent interest because it demonstrates that branching can be avoided on this family of instances.

major comments (2)
  1. [Computational results section] The central claim rests on the solver returning zero-gap certificates for n up to 115. The manuscript should state the precise solver version, all non-default parameters (including cut-generation limits and numerical tolerances), and the final primal/dual bounds for each newly solved instance; without these data, independent verification that numerical instability did not affect the reported optimality is impossible.
  2. [Pure cutting-plane method description] For the pure cutting-plane algorithm, the description of how the combinatorial Gomory cuts are separated and added must include a short validity argument or reference showing that the cuts are valid for the n-queens assignment polytope; the current exposition leaves open whether the cut generation is guaranteed to produce only valid inequalities.
minor comments (2)
  1. Table captions should explicitly indicate whether the reported times include preprocessing or only the MIP phase.
  2. The lexicographic objective is implemented via sequential optimization; a brief remark on how ties are broken in the secondary objectives would clarify the exact ordering used.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and the recommendation for minor revision. We address the two major comments below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Computational results section] The central claim rests on the solver returning zero-gap certificates for n up to 115. The manuscript should state the precise solver version, all non-default parameters (including cut-generation limits and numerical tolerances), and the final primal/dual bounds for each newly solved instance; without these data, independent verification that numerical instability did not affect the reported optimality is impossible.

    Authors: We agree that these details are necessary for reproducibility and verification. In the revised manuscript we will report the exact solver version, all non-default parameters (including cut-generation limits and tolerances), and the final primal/dual bounds for each instance n=56 to 115. We will also make the full instance data and log files available as supplementary material. revision: yes

  2. Referee: [Pure cutting-plane method description] For the pure cutting-plane algorithm, the description of how the combinatorial Gomory cuts are separated and added must include a short validity argument or reference showing that the cuts are valid for the n-queens assignment polytope; the current exposition leaves open whether the cut generation is guaranteed to produce only valid inequalities.

    Authors: We will insert a concise validity argument (with a supporting reference to the n-queens assignment polytope) in the description of the combinatorial Gomory cuts to confirm that only valid inequalities are generated. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper formulates the n-queens problem as explicit 0-1 ILPs with row/column/diagonal non-attacking inequalities, then reports solutions obtained by feeding these models to a commercial MIP solver (with custom cuts). The central results are direct solver outputs on polynomially sized instances; no parameters are fitted to subsets of the target solutions, no equations are defined in terms of their own outputs, and no load-bearing premise reduces to a self-citation chain. The derivation is therefore self-contained against external benchmarks (the model itself plus the solver's optimality certificate).

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on the correctness of standard ILP theory and the non-attacking constraint encoding; no new entities, fitted constants, or ad-hoc axioms are introduced beyond solver behavior.

axioms (1)
  • standard math The standard ILP relaxation plus Gomory cuts can be used to solve 0-1 integer programs to proven optimality.
    Invoked when describing the pure cutting-plane method.

pith-pipeline@v0.9.0 · 5755 in / 1202 out tokens · 20790 ms · 2026-05-24T19:16:52.908109+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

  1. [1]

    Constraint Integer Programming

    Tobias Achterberg. Constraint Integer Programming . PhD thesis, Technische Universit ¨at Berlin, 2007

    work page 2007

  2. [2]

    Embedding {0, 1/2}-cuts in a branch-and-cut framework: A computational study

    Giuseppe Andreello, Alberto Caprara, and Matteo Fischetti. Embedding {0, 1/2}-cuts in a branch-and-cut framework: A computational study. INFORMS Journal on Computing , 19(2):229–238, 2007. 13

    work page 2007

  3. [3]

    On the enumerative nature of Gomory’s dual cutting plane method

    Egon Balas, Matteo Fischetti, and Arrigo Zanette. On the enumerative nature of Gomory’s dual cutting plane method. Mathematical Programmming, 125:325–351, 2010

    work page 2010

  4. [4]

    A hard integer program made easy by lexicography

    Egon Balas, Matteo Fischetti, and Arrigo Zanette. A hard integer program made easy by lexicography. Mathematical Programmming, 135(1-2):509–514, 2012

    work page 2012

  5. [5]

    A survey of known results and research areas for n-queens

    Jordan Bell and Brett Stevens. A survey of known results and research areas for n-queens. Discrete Mathematics, 309(1):1–31, 2009

    work page 2009

  6. [6]

    Proposal of 8-queens problem

    Max Bezzel. Proposal of 8-queens problem. Berliner Schachzeitung, 3:363, 1848

    work page

  7. [7]

    {0, 1 2}-Chv´atal-Gomory cuts

    Alberto Caprara and Matteo Fischetti. {0, 1 2}-Chv´atal-Gomory cuts. Mathematical Program- ming, 74:221–235, 1996

    work page 1996

  8. [8]

    Odd cut-sets, odd cycles, and 0-1/2 Chvatal-Gomory cuts

    Alberto Caprara and Matteo Fischetti. Odd cut-sets, odd cycles, and 0-1/2 Chvatal-Gomory cuts. Ricerca Operativa, 26:51–80, 1996

    work page 1996

  9. [9]

    Chasing first queens by integer programming

    Matteo Fischetti and Domenico Salvagnin. Chasing first queens by integer programming. In Willem-Jan van Hoeve, editor, Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 232–244. Springer, 2018

    work page 2018

  10. [10]

    L. R. Foulds and D. G. Johnston. An application of graph theory and integer programming: Chessboard non-attacking puzzles. Mathematics Magazine, 57:95–104, 1984

    work page 1984

  11. [11]

    Gecode: Generic constraint development environment, 2017

    Gecode Team. Gecode: Generic constraint development environment, 2017. Available at http://www.gecode.org

    work page 2017

  12. [12]

    Gent, Christopher Jefferson, and Peter Nightingale

    Ian P. Gent, Christopher Jefferson, and Peter Nightingale. Complexity of n-queens completion. Journal of Artificial Intelligence Research, 59:815–848, 2017

    work page 2017

  13. [13]

    Ralph E. Gomory. Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society, 64:275–278, 1958

    work page 1958

  14. [14]

    Ralph E. Gomory. An algorithm for the mixed integer problem. Technical Report RM-2597, The RAND Cooperation, 1960

    work page 1960

  15. [15]

    Geometric Algorithms and Com- binatorial Optimization

    Martin Gr ¨otschel, L´aszl´o Lov´asz, and Alexander Schrijver. Geometric Algorithms and Com- binatorial Optimization. Springer, 1988

    work page 1988

  16. [16]

    Frank Hsu, and Yuh-Pyng Shieh

    Jieh Hsiang, D. Frank Hsu, and Yuh-Pyng Shieh. On the hardness of counting problems of complete mappings. Discrete Mathematics, 277(1-3):87–100, 2004

    work page 2004

  17. [17]

    ILOG CPLEX 12.7 User’s Manual, 2017

    IBM. ILOG CPLEX 12.7 User’s Manual, 2017

    work page 2017

  18. [18]

    Donald E. Knuth. Private communication, June 2018

    work page 2018

  19. [19]

    Donald E. Knuth. Private communication, November 2017

    work page 2017

  20. [20]

    Franc ¸ois J.E. Lionnet. Question 963. Nouvelles Annales de Math´ematiques, 8:560, 1869

    work page

  21. [21]

    A filtering algorithm for constraints of difference in CSPs

    Jean-Charles R ´egin. A filtering algorithm for constraints of difference in CSPs. In Artificial Intelligence, volume 1, pages 362–367, 1994

    work page 1994

  22. [22]

    Wolfram Schubert’s N-Queens page, http://m29s20.vlinux.de/ ~wschub/nqueen.html, accessed on December 2017

    Wolfram Schubert. Wolfram Schubert’s N-Queens page, http://m29s20.vlinux.de/ ~wschub/nqueen.html, accessed on December 2017

    work page 2017

  23. [23]

    Neil J.A. Sloane. The on-line encyclopedia of integer sequences, 2017

    work page 2017

  24. [24]

    The alldifferent constraint: A survey

    Willem Jan van Hoeve. The alldifferent constraint: A survey. CoRR, 2001

    work page 2001

  25. [25]

    Lexicography and degeneracy: can a pure cutting plane algorithm work? Mathematical Programmming, 130:153–176, 2011

    Arrigo Zanette, Matteo Fischetti, and Egon Balas. Lexicography and degeneracy: can a pure cutting plane algorithm work? Mathematical Programmming, 130:153–176, 2011. 14

    work page 2011