The $n$-Queens Problem in Higher Dimensions

Masterarbeit unter der Betreuung von

Prof. Dr. Thorsten Koch
Institut für Mathematik
Technische Universität Berlin

vorgelegt von

Tim Kunt

Berlin, 20.12.2023

###### Contents

  1. 1 Introduction
    1. 1.1 Motivation
    2. 1.2 Contribution
    3. 1.3 Notation and Definitions
      1. 1.3.1 Board
      2. 1.3.2 Pieces
    4. 1.4 Problem Definitions
      1. 1.4.1 Solutions
  2. 2 The Classical $(n,2)$-Queens Problem
    1. 2.1 Existence and Construction of Solutions
    2. 2.2 Enumeration of Solutions
      1. 2.2.1 Density of Solutions
  3. 3 The $(n,3)$-Queens Problem
    1. 3.1 Existence and Construction of Solutions
      1. 3.1.1 Regular Solutions
      2. 3.1.2 Colouring the Queen Graph
      3. 3.1.3 Stacking Superimposable Solutions
    2. 3.2 Lower Bounds
      1. 3.2.1 Subcube Heuristic
    3. 3.3 Enumeration of Solutions
      1. 3.3.1 Lower Bounds
    4. 3.4 Open Questions
  4. 4 Generalization to Higher Dimensions
    1. 4.1 Existence and Construction of Solutions
    2. 4.2 Lower Bounds
      1. 4.2.1 Subscube Heuristic
    3. 4.3 Upper Bounds
      1. 4.3.1 Subsolution Inequalities
    4. 4.4 Enumeration of Solutions
      1. 4.4.1 Lower Bounds
      2. 4.4.2 Upper Bounds
    5. 4.5 Related Problems
      1. 4.5.1 $(n,d)$-Queens Completion
    6. 4.6 Open Questions
  5. 5 Integer Programming Formulation
    1. 5.1 Base Model
      1. 5.1.1 The Partial $(n,d)$-Queens Problem
      2. 5.1.2 The $(n,2)$-Queens Problem
      3. 5.1.3 The Partial $(n,3)$-Queens Problem
    2. 5.2 Strengthening the IP
      1. 5.2.1 Subsolution Inequalities
      2. 5.2.2 Layer Inequalities
      3. 5.2.3 Cube and Star Cliques
      4. 5.2.4 Odd Cycle Inequalities
  6. 6 Computational Results
    1. 6.1 The Partial $(n,3)$-Queens Problem
      1. 6.1.1 Base Model
      2. 6.1.2 LMR
      3. 6.1.3 Cube Cliques
      4. 6.1.4 Star Cliques
      5. 6.1.5 Cube and Star Cliques
      6. 6.1.6 Infeasibility for $|Q_{max}|+1$
      7. 6.1.7 Infeasibility for $|Q_{max}|+1$, Cube Cliques
      8. 6.1.8 Infeasibility for $|Q_{max}|+1$, Cube and Star Cliques
      9. 6.1.9 Warmstarts with Base Model
      10. 6.1.10 Warmstarts with Cube and Star Cliques
      11. 6.1.11 Comparison of IP Formulations
    2. 6.2 The Partial $(n,4)$-Queens Problem
      1. 6.2.1 Base Model
      2. 6.2.2 LMR
      3. 6.2.3 All additional Inequalities
      4. 6.2.4 Infeasibility for $|Q_{max}|+1$
      5. 6.2.5 Infeasibility for $|Q_{max}|+1$, all additional Inequalities
      6. 6.2.6 Warmstarts with Base Model
      7. 6.2.7 Warmstarts with all additional Inequalities
      8. 6.2.8 Comparison of IP Formulations
    3. 6.3 The Partial $(n,5)$-Queens Problem
      1. 6.3.1 Base Model
      2. 6.3.2 LMR
      3. 6.3.3 All additional Inequalities
      4. 6.3.4 Infeasibility for $|Q_{max}|+1$
      5. 6.3.5 Infeasibility for $|Q_{max}|+1$, all additional Inequalities
      6. 6.3.6 Comparison of IP Formulations
    4. 6.4 Density of Solutions
      1. 6.4.1 $d=3$
      2. 6.4.2 $d=4$
  7. 7 Conclusions and Future Work
  8. 8 Bibliography

## Acknowledgments

Two years ago, I unsuspectingly visited the lecture ’Industrial Data Science’
at Technical University Berlin, hoping to learn more about the field I had
pivoted towards. The lecture contained a few applications of mathematical
optimization, and to my surprise, these parts were very much relevant for the
final oral exam (I had most of my attention focused on the probability theory
and modeling parts, where I felt comfortable). Thorsten Koch and Charlie
Vanaret, who had been responsible for my weekly mathematical entertainment,
allowed me to repeat the exam after I had barely passed it, unable to write
down the IP formulation for a given problem.
Regardless, I enjoyed Thorsten’s teaching style, the tangents and stories, and
the terrors of applied mathematics, so that I would join the following two
seminars on integer programming, still mostly clueless about the topic. Trying
to catch up, the first IP model I came up with was regarding three-dimensional
chess after having played 5D Chess With Multiverse Time Travel [Pet20] and
through the visual intuition (see Fig. 1) of how to model a sudoku using
integer programming.

Figure 1: ILP formulation of a sudoku [KB20]

What started as a coding and learning project for the seminar turned out to be
an easy-to-understand yet complex-to-solve problem. Having picked up the
$n$-queens problem again for this thesis, I have learned to appreciate the
torture of seemingly unsolvable instances and the excitement of incremental
progress.

I thank Michael Simkin for his comments on my questions and ideas regarding
the $n$-queens problem in 3D and its enumeration. As the known results on the
$n$-queens problem in higher dimensions are quite scattered or unpublished,
the Al Zimmermann’s Attacking Queens Contest [Zim02] turned out to be a
valuable source and starting point. Thanks to Michael Ecker, who was able to
find and share the original announcement of the contest. I thank Stephen
Montgomery-Smith, Joe Zbiciak and Karl Grill, all of whom were involved in the
contest, for their notes and help regarding the contest’s history.

I am very grateful to the entire A2IM department at ZIB, in particular Milena
Petkovic, Janina Zittel and Thorsten Koch for their trust and support
throughout our work and during this thesis. I greatly appreciate the creative
freedom we are given and hope to find and work on many more diverse research
topics and projects.

Thanks to Mark Ruben Turner, whom I could confront with questions at any time.
Your advice helped me in both the technical implementation and gaining
confidence and insight. When I learned that Timo Berthold would be supervising
this thesis together with Thorsten Koch, I was reassured and scared at the
same time. With your expertise, Timo, you will surely spot all the loose ends
and opportunities for improvement in this thesis. Thank you for listening and
for your help at all times. Lastly, I thank my professor and supervisor,
Thorsten Koch. You sparked my interest in the topic in the first place and are
the reason I ended up at ZIB.

"I think that I may personally be done with the n-queens problem for a while,
not because there isn’t anything more to do with it but just because of I’ve
been dreaming about chess and I’m ready to move on with my life."

Michael Simkin [Sil22]

##  1 Introduction

###  1.1 Motivation

The $n$-queens problem asks whether it is possible to place $n$ mutually non-
attacking queens on an $n\times n$ chessboard. This thesis considers the
$n$-queens problem in higher dimensions with the goal of solving its instances
or obtaining bounds towards their solutions.

The classical $n$-queens problem, while over 150 years old, is the source of
various optimization and decision problems. While solving the classical
$n$-queens problem (i.e., finding a certificate to the decision problem) can
be achieved through various constructions in linear time, the generalization
of the $n$-queens problem to higher dimensions turns out to be highly non-
trivial.

$n$-queens and its many variations can be explained in just a few sentences,
and its mathematical formulation is quite compact, yet it poses interesting,
hard and unsolved questions. For this reason, the topic is well-suited for
benchmarks that compare different methodologies and algorithms. Throughout the
long history of the problem, there have been steady and incremental
advancements. Both the innovation in technology and algorithms, as well as new
theoretical results, enable this progress.
At the same time, the $n$-queens problem allows emerging technologies to prove
themselves, comparing them to classical methods. Several publications on
solving the problem with neural networks were published in the past few
decades, and the first ones are tackling the problem using quantum computing
now. Thus, we are also interested in stating and comparing our integer
programming methods on instances of the $n$-queens problem in higher
dimensions.

There are (at least) three angles from which the $n$-queens problem in 3D and
higher dimensions can be motivated:

  * 1)

Chess problems in higher dimension
The first and most intuitive one is through the imagination of three- (or
higher-) dimensional chess. This opens up the question of how different chess
pieces move in higher dimensions and provides a starting point for a great
variety of generalizations of mathematical- and chess problems into higher
dimensions.

  * 2)

Higher dimensional permutations with additional constraints
Second, the $n$-queens problem in 3D can be described as a Latin square with
additional constraints. This will be described later on in detail, but it has
a similar visual intuition as it is demonstrated by Fig.1 for sudoku (which
can also be described as a Latin square with additional constraints).

  * 3)

Maximal independent sets on grid graphs
Lastly, we may interpret the chessboard for a given chess piece as a graph.
Two nodes, i.e., squares are connected through an edge if the chess piece can
move from one to the other. This is called the queen’s graph in the case of
the queen. The $n$-queens problem is equivalent to the independent set problem
on the queen’s graph. This is expanded on in 3.1.2.

While (1) is mainly helpful for an intuition of the problem and is eponymous
to its name, (2) and (3) may already hint at suitable methods for solving.

Figure 2: Three dimensional chess as shown in Star Trek [Tre66]

We differentiate between varying approaches to the $n$-queens problem, some of
which may benefit from one another. The most straightforward approach is brute
force search methods, possibly abusing the symmetries of the problem. Multiple
constructions exist that provide solutions or lower bounds to the problem in
both two and higher dimensions. Additionally, there are several interesting
insights into the problem through combinatorics. Our approach to the problem
is using integer programming. This has several advantages:

  * a)

we can prove the maximality of solutions

  * b)

we may incorporate and benefit from insights of other solution methods

  * c)

we are able to solve instances that are potentially out of reach for other
methods

Our primary focus is the IP formulation and possible strengthenings, as well
as using heuristics for warmstarts. This is complemented by lower bounds for
the instances that we cannot solve as of today.

###  1.2 Contribution

We provide a comprehensive overview of existing literature and methods for
solving the $n$-queens problem in higher dimensions. Our starting point is "A
survey of known results and research areas for n-queens" [BS08] from 2009,
which we extend with recent results and our methods regarding the variation of
the problem in higher dimensions and the solving of instances. While this
variation of the problem is not unknown, literature on the topic is partially
scattered or unpublished, which is best illustrated by the fact that several
results have been independently (re-)discovered by different authors over the
years. Thus, we consider collecting and connecting the existing results and
solving techniques necessary. We describe and briefly compare the varying
approaches to the problem and draw the connection between several related
problems.

Second, we provide an integer programming formulation for the $n$-queens
problem in higher dimensions. We discuss and compare several possible
strengthenings of the formulation. We note that the recent preprint Complexity
of Chess Domination Problems [LRMR22a] by Alexis Langlois-Rémillard, Christoph
Müßig and Érika Róldan was published during the work on this thesis. Among
their results regarding complexity of domination problems on polyminoes, they
propose an IP formulation for the $n$-queens problem in higher dimensions. In
order to incorporate their results, we compare our methods to their
formulation and achieve a speedup between $15.5\times-71.2\times$ less
computational time over all instances.111Measuring this speedup, we compare
average computational time, gurobi work, and nodes for their method and our
best-performing method and limit ourselves to instances that initially took
more than 10s to solve in order to minimize noise. See section 6 in detail..

Third, we are able to verify the maximality of existing certificates to the
problem for different $n,d$.

Fourth, we present a heuristic method to derive lower bounds for instances
still out of reach today.

Lastly, we give several preliminary results for enumeration and the density of
solutions to the $n$-queens problem in higher dimensions and point towards
insights regarding related problems.

###  1.3 Notation and Definitions

Notation follows [GJN17] and [JB09] in large parts. There are several cases of
varying names or notation for the same problem, property, or result in
different sources. In those cases, we will list and define them once and
proceed with a choice that allows for a coherent and descriptive notation.

####  1.3.1 Board

We consider boards of size $n$ in dimension $d$, where integer $n$ is the
number of squares in each dimension and integer $d$ is the number of
dimensions the board extends to. We will describe a board as $(n,d)$-board, if
not otherwise apparent from the context. As an example, following this
notation, a conventional chess board would be called an $(8,2)$-board.

A generalization of the $n$-queens and related problems to rectangular boards
or polyominoes is possible; see [LRMR22a]. Further variants of the problem
identify opposite faces of the board, creating different topologies such as
$n$-queens on a Moebius strip or a torus. For an overview see [BS08] and
[JB09]. In particular, the $n$-queens problem on the modular $n^{d}$ board
[Nud95] proves useful for the $n$-queens problem in higher dimensions and will
be expanded on in the following section.

We will refer to individual squares on such a board of dimension $d$ using a
tuple $(a_{1},a_{2},...,a_{d})$, where each element marks the position in the
respective dimension.

The $i$-th layer in the $j$-th dimension of a board is given by the set of
squares, for which the $a_{j}=i$. For $d=2$, the two possible layers are
simple rows and columns. For $d=3$, the layers are two-dimensional boards
themselves. The concept is introduced, as it naturally leads to a possible
algorithm to construct solutions for the $n$-queens problem in higher
dimensions. Layers of the $(n,d)$-board correspond to $(n,d-1)$-boards.

Figure 3: Example of one layer in each dimension of the $(8,3)$-board

We point out that developing additional variants of the $n$-queens problem is
possible using boards that do not follow a rectangular grid, such as hexagonal
chess. A generalization to other grid graphs (as we may identify the
chessboard as a square grid graph) is motivated naturally by the formulation
of the $n$-queens problem as a maximal independent set problem on grid graphs.
The queen graph is later touched on in 3.1.2. These variants may also be
formulated so that they correspond to a version of the Chvátal’s art gallery
problem (c.f. [AR21]), provided a definition of a queens vision (which equates
to their legal moves) on the chosen grid.

Figure 4: Hexagonal chess (Gliński’s variant)

####  1.3.2 Pieces

We define chess pieces through their moves, i.e., lines of attack on a board.
To avoid confusion in the context of the minimum dominating set problem, any
piece is always attacking its own square. Definitions build upon [GJN17].

Similar to boards, it is possible to come up with numerous chess pieces and
examine the resulting maximal independent set problem or other related
problems. The reason why queens are particularly interesting is that they
present the first step in complexity above rooks. For rooks, the maximal
independent sets directly correspond to permutation matrices and Latin
squares. Therefore, the cardinality of those maximal independent sets on the
$(n,d)$-board is trivially $n^{d-1}$. Enumeration of solutions may still be
non-trivial; in fact, it has only been solved recently for such permutation
matrices [Kee18], which we will expand on in section 3.3. For queens, however,
we cannot always place $n^{d-1}$ in a non-attacking configuration on the
$(n,d)$-board. That is why we are concerned with finding such maximal
independent sets of queens.

######  Definition 1 (Rook).

A rook r on a $(n,d)$-board is a tuple of integers $(a_{1},a_{2},...,a_{d})$
with $1\leq a_{i}\leq n$ for $i\in\\{1,2,...,d\\}$.

  * •

The size of $r$, written $\lVert r\rVert$ is defined by $\lVert
r\rVert:=\text{max}(a_{1},a_{2},...,a_{d})$.
We say that $r$ fits a board of size $n$ iff $\lVert r\rVert\leq n$. We extend
this to sets of rooks, so that $\lVert R\rVert:=\text{max}_{r\in R}(\lVert
r\rVert)$. Any set of rooks is pairwise distinct. We write $|R|$ for the
number of elements in $R$.

  * •

For any pair of rooks $r_{1}=(a_{1},a_{2},...,a_{d})$ and
$r_{2}=(b_{1},b_{2},...,b_{d})$ with $r_{1}\neq r_{2}$, we say that $r_{1}$
attacks $r_{2}$ if there exists some $m\in\mathbb{Z}$ and
$\epsilon=(0,...,\epsilon_{i},...,0)$ with one non-zero entry
$\epsilon_{i}\in\\{-1,0,1\\}$ such that

$\displaystyle a_{i}=\epsilon_{i}\cdot m+b_{i}\;\;\forall i\in\\{1,2,...,d\\}$
(1)

In other words, a pair of rooks $r_{1}=(a_{1},a_{2},...,a_{d})$ and
$r_{2}=(b_{1},b_{2},...,b_{d})$ attack each other if $a_{i}=b_{i}$ for all but
one $i\in 1,...,d$. The above might not be the most compact definition of a
rook’s movement in higher dimensions, but it introduces us to the concept of
hyperplanes of attacks described by the vectors $\epsilon$ and naturally leads
to the following definition for queens.

######  Definition 2 (Queen).

A queen q on a $(n,d)$-board is a tuple of integers $(a_{1},a_{2},...,a_{d})$
with $1\leq a_{i}\leq n$ for $i\in\\{1,2,...,d\\}$.

  * •

The size of $q$, written $\lVert q\rVert$ is defined by $\lVert
q\rVert:=\text{max}(a_{1},a_{2},...,a_{d})$.
We say that $q$ fits a board of size $n$ iff $\lVert q\rVert\leq n$. We extend
this to sets of queens, so that $\lVert Q\rVert:=\text{max}_{q\in Q}(\lVert
q\rVert)$. Any set of queens is pairwise distinct. We write $|Q|$ for the
number of elements in $Q$.

  * •

For any pair of queens $q_{1}=(a_{1},a_{2},...,a_{d})$ and
$q_{2}=(b_{1},b_{2},...,b_{d})$ with $q_{1}\neq q_{2}$, we say that $q_{1}$
attacks $q_{2}$ if there exists some $m\in\mathbb{Z}$ and nonzero
$\epsilon=(\epsilon_{1},\epsilon_{2},...,\epsilon_{d})$ with
$\epsilon_{i}\in\\{-1,0,1\\}$ such that

$\displaystyle a_{i}=\epsilon_{i}\cdot m+b_{i}\;\;\forall i\in\\{1,2,...,d\\}$
(2)

The attacking relation is symmetric for rooks and queens. Note that the
relation is not necessarily symmetric for all chess pieces and boards. This is
the reason why the given definition differentiates between $p_{1}$ attacking
$p_{2}$ and $p_{2}$ attacking $p_{1}$. We will call a pair of queens for which
neither $q_{1}$ is attacking $q_{2}$ nor $q_{2}$ is attacking $q_{1}$ mutually
non-attacking.

The $\epsilon\cdot m$ describe the hyperplanes a queen can attack in for
general dimensions. We will also refer to a piece $p$ attacking a set of
squares if a piece placed on each of those squares would be attacked by $p$.
In the context of chess domination problems, a square that is attacked by at
least one piece is considered dominated.

Figure 5: Dominated squares by a rook (left) and a queen (right) placed on the
square $(4,2,3)$ on the $(8,3)$-board

###  1.4 Problem Definitions

In the following, we define the $(n,d)$-queens problem as a generalization of
the $n$-queens problem and a selection of variants as decision problems. This
allows us to formulate corresponding integer program formulations as
feasibility problems and provides the necessary foundation to discuss
complexity (c.f. [GJN17] [LRMR22a]). Notation follows [GJN17] in large parts.

Problem 1 ($(n,d)$-queens).
Problem: A $(n,d)$-board, $n,d\in\mathbb{N}^{+}$ Solution: A set $Q$ of queens
such that:

  * i)

$|Q|=n^{d-1}$

  * ii)

$\lVert Q\rVert\leq n$

  * iii)

For any distinct pair of queens $q_{1}$, $q_{2}$ $\in Q$, $q_{1}$ does not
attack $q_{2}$

This is a generalization of the definition [GJN17] of the standard $n$-queens
problem to higher dimensions. In particular, the two-dimensional case $d=2$
for which (i) $|Q|=n$ is commonly known and referred to as the standard
$n$-queens problem.

Problem 2 (modular $(n,d)$-queens).
Problem: A $(n,d)$-board, $n,d\in\mathbb{N}^{+}$ Solution: A set $Q$ of queens
such that:

  * i)

$|Q|=n^{d-1}$

  * ii)

$\lVert Q\rVert\leq n$

  * iii)

For any distinct pair of queens $q_{1}=(a_{1},a_{2},...,a_{d})$,
$q_{2}=(b_{1},b_{2},...,b_{d})$ $\in Q$ and for any non-zero
$\epsilon=(\epsilon_{1},\epsilon_{2},...,\epsilon_{d})$

$\displaystyle\sum^{d}_{i=1}(\epsilon_{i}\cdot
a_{i})\neq\bigg{(}\sum^{d}_{i=1}(\epsilon_{i}\cdot b_{i})\bigg{)}\text{mod n}$

The modular $n$-queens problem, first introduced by Polya, [Pól21] is a
variation of the $n$-queens problem where opposite sides of the board are
identified, forming a torus. This generalizes to higher dimensions $d\geq 3$
as the $n$-queens problem on the $d$-torus.

Figure 6: Queens on a donut [BS08]

######  Proposition 1.

A solution to the modular $(n,d)$-queens problem is also a solution to the
$(n,d)$-queens problem.

This follows from the fact that the set of attacked squares for any queen in
the $n$-queens problem is contained in the set of attacked squares of a queen
on the same square on the modular board. Therefore any mutually non-attacking
configuration on the modular board is also a mutually non-attacking
configuration on the standard board. Analog arguments can be made for certain
sets of mutually non-attacking chess pieces, for which the move-set of one
piece is contained in the move-set of another (as is the case with queen and
superqueen or bishop, rook, and queen).

######  Proposition 2.

For a pair of pieces $p_{1}$ and $p_{2}$ for which the set of dominated
squares of $p_{2}$ is contained in the set of dominated squares of $p_{1}$, a
solution to the $(n,d)$-$p_{1}$ problem is also a solution to the
$(n,d)$-$p_{2}$ problem.

Figure 7: solution to the modular $(7,2)$-queens problem

While the standard $(n,2)$-queens problem has a solution for all $n\geq 3$
(see Theorem 1), a comparable result is not known for the $(n,d)$-queens
problem for $d\geq 3$. For $n,d$, for which no solution exists, we are
interested in finding sets of mutually non-attacking queens with maximal
cardinality. This motivates the following definition of the partial
$(n,d)$-queens problem.

Problem 3 (partial $(n,d)$-queens).
Problem: A $(n,d)$-board, $k\leq n^{d-1}$, $n,d,k\in\mathbb{N}^{+}$ Solution:
A set $Q$ of queens such that:

  * i)

$|Q|=k$

  * ii)

$\lVert Q\rVert\leq n$

  * iii)

For any distinct pair of queens $q_{1}$, $q_{2}$ $\in Q$, $q_{1}$ does not
attack $q_{2}$

The special case $k=n^{(d-1)}$ of the partial $(n,d)$-queens problem is the
$(n,d)$-queens problem. For given $n,d$, the corresponding optimization
problem asks to find the maximal $k$, for which a solution to the partial
$(n,d)$-queens problem exists. We call such a solution a maximal partial
solution [BS08]. For a given board of size $n$ in dimension $d$, we write
$Q_{max}(n,d)$ for such a solution and $|Q_{max}(n,d)|$ for its cardinality.
We distinguish between the $(n,d)$-queens problem and the partial
$(n,d)$-queens problem, as certain statements, methods, and enumeration
techniques may differ or only apply for $k=n^{(d-1)}$.

The main focus of this thesis is to find and enumerate maximal partial
solutions. We will further define a small selection of variants and related
problems. These may serve to provide lower bounds to the partial
$(n,d)$-queens problem. Others, such as the minimal independent dominating set
problem, are well suited to be solved by the integer programming methods
presented in section 5.

Problem 4 ($(n,d)$-queens completion).
Problem: A $(n,d)$-board, $n,d\in\mathbb{N}^{+}$, a set of mutually non-
attacking queens  $Q^{*}$ with $|Q^{*}|\leq n^{d-1}$, $\lVert Q^{*}\rVert\leq
n$ Solution: A set $Q$ of queens such that:

  * i)

$|Q|=n^{d-1}$

  * ii)

$\lVert Q\rVert\leq n$

  * iii)

For any distinct pair of queens ${q}_{1}$, ${q}_{2}$ $\in Q$, ${q}_{1}$ does
not attack ${q}_{2}$

  * iv)

$Q^{*}\subseteq Q$

Note that this definition differs from the definition given by [GJN17], which
allows the queens in $Q^{*}$ to be set on the same diagonal.

######  Proposition 3.

The $(n,d)$-queens completion for some given $Q^{*}$ has no solution if and
only if there does not exists a solution $Q$ to the corresponding
$(n,d)$-queens problem with $Q^{*}\subseteq Q$

In particular, for $Q^{*}$ with $|Q^{*}|=1$ this means that it is possible to
check whether a certain square may be occupied without having to check all
solutions to the $(n,d)$-queens problem exhaustively.
Again, for instances where the $(n,d)$-queens problem does not have a
solution, we are be interested in maximal partial solutions:

Problem 5 (partial $(n,d)$-queens completion).
Problem: A $(n,d)$-board, $k\leq n^{d-1}$, $n,d,k\in\mathbb{N}^{+}$, a set of
mutually non-attacking queens  $Q^{*}$ with $|Q^{*}|\leq n^{d-1}$, $\lVert
Q^{*}\rVert\leq n$ Solution: A set $Q$ of queens such that:

  * i)

$|Q|=k$

  * ii)

$\lVert Q\rVert\leq n$

  * iii)

For any distinct pair of queens ${q}_{1}$, ${q}_{2}$ $\in Q$, ${q}_{1}$ does
not attack ${q}_{2}$

  * iv)

$Q^{*}\subseteq Q$

As discussed in section 3.1.2 , the partial $(n,d)$-queens problem (or to be
precise its respective optimization problem) can be interpreted and formulated
as maximal independent set on the $(n,d)$-queen graph. Naturally one may also
ask, what the minimum dominating sets of queens for such a given board are.
This problem in turn has a visual interpretation as a variant of Chvátal’s art
gallery problem [AR21]. Hence we define the corresponding decision problem to
the minimal $n$-queen domination:

Problem 6 ($(n,d)$-queens domination).
Problem: A $(n,d)$-board, $k\leq n^{d-1}$, $n,d,k\in\mathbb{N}^{+}$ Solution:
A set $Q$ of queens such that:

  * i)

$|Q|=k$

  * ii)

$\lVert Q\rVert\leq n$

  * iii)

Every square of the board is attacked by at least one queen $q\in Q$

Analog definitions to problems 1,2,4,5, and 6 for the rook are straight
forward.

####  1.4.1 Solutions

######  Definition 3 (regular solution [JB09]).

A regular (or sometimes called linear) solution is a certificate for the
$(n,d)$-queens problem, that can be constructed by a starting square
$(s_{1},s_{2},...)$ and a fixed movement $(m_{1},m_{2},...)$ that places the
$k$-th queen at $(s_{1}+(k\cdot m_{1})\text{ mod }n,s_{2}+(k\cdot m_{2})\text{
mod }n,...)$.

Note that the existence of such regular solutions implies that the
corresponding problem is solvable in polynomial time.

######  Definition 4 (superimposable solutions [JB09]).

A disjoint set of solutions to the $(n,d)$-queens problem is called
superimposable.

In other words, a set of superimposable solutions to the $(n,d)$-queens
problem can be placed on the $(n,d)$-board without overlap. The cardinality of
a superimposable set cannot be greater than $n$.

######  Definition 5 (partial solution).

A set of queens $Q$ is called a partial solution on the $(n,d)$-board if:

  * i)

$\lVert Q\rVert\leq n$

  * ii)

For any distinct pair of queens ${q}_{1}$, ${q}_{2}$ $\in Q$, ${q}_{1}$ does
not attack ${q}_{2}$

This is a generalization of maximal partial solutions and will be used to
describe the output of heuristics, as maximality might not be proven for such
solutions.

We refer to [JB09] who introduce further classes of solutions, such as
symmetric solutions, doubly symmetric solutions and doubly periodic solutions,
which will not be of importance for this thesis but may be of use for further
research on the partial modular $(n,d)$-queens problem and for the enumeration
of regular solutions to the $(n,d)$-queens problem.

##  2 The Classical $(n,2)$-Queens Problem

The following is a brief overview of selected theoretical results regarding
the $(n,d)$-queens problem, focused on those relevant to solving and
understanding the problem in higher dimensions. For a detailed overview of all
known results on n-queens up until 2009, [JB09] remains the most comprehensive
source.

###  2.1 Existence and Construction of Solutions

######  Theorem 1 (Pauls [Pau74]).

For all $n\geq 4$ the $(n,2)$-queens problem has a solution.

Pauls provided the first proof, listing construction methods for all residue
classes of $(n\text{ mod }6)$. Throughout the history of the problem, a large
number of different authors have given different proofs for various
constructions. An overview of all construction techniques is expanded on in
[JB09]. The often cited construction of [EH69] (c.f. [Ber91]) distinguishes
between three cases:

  * (A)

$n$ even, $n\neq 6k+2$: Place queens on:
$(j,2j)$
$(n/2+j,2j-1)$, for $j=1,...,n/2$

  * (B)

$n$ even, $n\neq 6k$: Place queens on:
$(j,1+(2(j-1)+n/2-1\text{ mod }n))$
$(m+1.j,n-(2(j-1)+n/2-1\text{ mod }n))$, for $j=1,...,n/2$

  * (C)

$n$ odd: Use suitable A or B for $(n-1)$ and add one queen on (n,n)

The resulting solutions for even $n$ are regular solutions. Solutions for odd
$n$ are not regular by definition, but as they are constructed by simply
extending a regular solution, the same argument regarding complexity holds.
Thus, finding one single certificate for the $(n,2)$-queens problem is
trivial; however, finding all solutions for given $n$ is not.

Figure 8: certificates for the $(n,2)$-queens problem by [EH69], $n=12,14,15$

###  2.2 Enumeration of Solutions

Let $\mathcal{Q}(n,d)$ denote the number of solutions to the $(n,d)$-queens
problem. Table 1 shows all currently known exact values of the sequence
$\mathcal{Q}(n,2)$.

$n$ | $\mathcal{Q}(n,2)$
---|---
0 | 1
1 | 1
2 | 0
3 | 0
4 | 2
5 | 10
6 | 4
7 | 40
8 | 92
9 | 352
10 | 724
11 | 2680
12 | 14200
13 | 73712
$n$ | $\mathcal{Q}(n,2)$
---|---
14 | 365596
15 | 2279184
16 | 14772512
17 | 95815104
18 | 666090624
19 | 4968057848
20 | 39029188884
21 | 314666222712
22 | 2691008701644
23 | 24233937684440
24 | 227514171973736
25 | 2207893435808352
26 | 22317699616364044
27 | 234907967154122528

Table 1: Number of solutions to the $(n,2)$-queens problem [OEIa]

######  Theorem 2 (Hsiang, Hsu, Shieh [HHS04]).

Finding all the solutions for the $n(n,2)$-queens problem and the modular
$(n,2)$-queens problem are both beyond the #P-class.

This implies that there exists no close form to enumeration of solutions to
the $(n,2)$-queens problem in $d=2$. However, significant improvements have
been made in tightening lower and upper bounds by [Lur17] [ZL21] [Sim21] and
most recently [NAB23].

######  Theorem 3 (Nobel, Agrawal, Boyd [NAB23] and Simkin [Sim21]).

There exists a constant $1.944000752019729<\alpha<1.9440010813092217$ such
that

$\displaystyle\lim_{n\to\infty}\frac{\mathcal{Q}(n,2)^{1/n}}{n}=e^{-\alpha}$
(3)

$\alpha$ is called the $n$-queens constant [NAB23] [OEIb].

####  2.2.1 Density of Solutions

######  Theorem 4 (Simkin [Sim21]).

Let $\mathcal{R}$ be the collection of subsets of the plane of the form

$\displaystyle\\{(x,y)\in[-1/2,1/2]\^{A}{{}^{2}}:a_{1}\leq x+y\leq
b_{1},a_{2}\leq y-x\leq b_{2}\\}$

for $a_{1},a_{2},b_{1},b_{2}\in[-1,1]$. Let $\gamma_{1},\gamma_{2}$ be two
finite Borel measures on $[-1/2,1/2]\^{A}{{}^{2}}$. We define the distance
between $\gamma_{1}$ and $\gamma_{2}$ by

$\displaystyle
d_{\diamond}(\gamma_{1},\gamma_{2})=sup\\{|\gamma_{1}(\alpha)-\gamma_{2}(\alpha)|:\alpha\in\mathcal{R}\\}$

Let $Q$ be an $(n,2)$-queens solution.
Define the step function $g_{Q}:[-1/2,1/2]\^{A}{{}^{2}}\rightarrow\mathbb{R}$
by $g_{Q}\equiv n$ on every square
$((\frac{i-1}{n}-\frac{1}{2},\frac{i}{n}-\frac{1}{2})\times((\frac{j-1}{n}-\frac{1}{2},\frac{j}{n}-\frac{1}{2})$
such that $(i,j)\in Q$ and $g_{Q}\equiv 0$ elsewhere. Let $\gamma_{Q}$ the
probablity measure with density function $g_{Q}$.

Then there exists a Borel probability measure $\gamma^{*}$ on $[-1/2,1/2]^{2}$
such that the following holds: Let $\epsilon>0$ be fixed and let $q$ be a
uniformly random n-queens configuration. With high probability
$d_{\diamond}(\gamma_{Q},\gamma^{*})<\epsilon$.

Figure 9: Density $\gamma^{*}$, the distribution of queens for the
$(n,2)$-queens problem

Intuitively, one may understand this density by observing that squares near
the corners dominate fewer squares, while a queen placed in the middle of the
board dominates the maximum number of squares. At the same time, placing a
queen in a corner forbids the placement of further queens in both that row and
column, so it appears to be least expensive to place queens that min-max this
relation. Tied to this intuition, [Sim21] derives the density function through
a martingale construction that iteratively places queens on the board.

Figure 10: Illustrating the density of solutions to the $(n,2)$-queens problem
for $n=9,10,11,12$. The number in each square describes the number of
solutions that place a queen on that square.

##  3 The $(n,3)$-Queens Problem

While polynomial time construction methods exist for all $(n,2)$-boards, this
is not the case for maximal partial solutions in $d\geq 3$. This section
discusses the specific case for $d=3$, i.e., the $(n,3)$-queens problem and
different solution methods. These methods appear more intuitive when
introduced in three-dimensional space. They connect to Latin squares and the
queen’s graph. Many results naturally extend to higher dimensions $d>3$, which
will be the topic of the following section 4.

###  3.1 Existence and Construction of Solutions

######  Definition 6 (Latin Square [MW05]).

For $n\in\mathbb{N}$, a Latin square is a $n\times n$ array with entries in
$(1,2,\dots,n)$ such that the entries in each row and in each column are
distinct.

The generalization of the $n$-queens problem to the third dimension is first
proposed by McCarthy [McC78]. In his work, he draws the connection to Latin
squares:

"The placing of the $n^{2}$ non-attacking rooks into an $n$-cube is now
reduced to the filling of an $n\times n$ grid with $n$ copies of the set
$\\{1,2,...,n\\}$ such that no to element is in the same row or column twice.
This problem is equivalent to finding a Latin square of order $n$. Such a
square can be obtained, for example, by cyclically permuting the elements
$\\{1,2,...,n\\}$ and gives the desired maximal solution for any $n$."

Continuing this thought, we may describe the $(n,3)$-queens problem as
equivalent to finding Latin squares of order $n$ with additional diagonal
constraints. This representation shines light on the problem of enumerating
solutions; it suggests using methods of enumerating higher dimensional
permutations and permutations with additional constraints as discussed by
[Kee18] may be a suitable approach to determine bounds for the number of
solutions to the $(n,3)$-queens problem.
[McC78] further mentions the trivial upper bound $|Q_{max}(n,3)|\leq n^{2}$
for the maximal partial solutions for $d=3$. We formulate the following
observation:

######  Proposition 4.

Any solution $Q$ to the $(n,3)$-queens problem also yields $n$ superimposable
solutions to the $(n,2)$-queens problem in each of the three dimensions of the
cube.

###### Proof.

Given a solution to the $(n,3)$-queens problem choose one dimension without
loss of generality. Consider each of the $n$ layers in the chosen dimension as
a $(n,2)$-board, by dropping the coordinate of the chosen dimension. $n^{2}$
queens are placed on the $(n,3)$-board, so $n^{2}$ queens are placed on all
$n$ $(n,2)$-boards in total. No more than $n$ queens can be placed on a single
$(n,2)$-board and exactly $n$ have to placed on each board for them to add up
to $n^{2}$. Hence the layers of the $(n,3)$-solution yield $n$
$(n,2)$-solutions. Those $n$ solutions are superimposable due to the initial
$(n,3)$-solution being a non-attacking configuration in the chosen dimension
in particular. ∎

Every $n\times n$ layer of a partial solution of the $n\times n\times n$ cube
may only contain a maximum of $n$ queens. Conversely, every layer of a
solution to the $(n,2)$-queens problem has to contain exactly $n$ queens.

Lastly, [McC78] provides the first lower bounds on maximal partial solutions,
using search algorithms (the method is not further elaborated on) for $n$ up
to 18. The following table also includes the currently best-known bounds in
comparison:

$n$ | [McC78] | current
---|---|---
3 | 4 | 4
4 | 7 | 7
5 | 13 | 13
6 | 18 | 21
7 | 27 | 32
8 | 34 | 48
9 | 43 | 67
10 | 58 | 91
$n$ | [McC78] | current
---|---|---
11 | 68 | 121
12 | 80 | 133
13 | 96 | 169
14 | 111 | 172
15 | 132 | 199
16 | 151 | 241
17 | 171 | 289
18 | 191 | 307

Table 2: lower bounds for $|Q_{max}(n,3)|$

(bold entries are proven maximal)

The original table from [McC78] additionally includes the variable
$R(n):=\frac{|Q_{max}(n,2)|}{n^{2}}$ and asks, if there exists an upper bound
on $R(n)$. We now know that this bound is $1$ from the construction of the
following theorem 5. But we may still ask:

For given $n_{0}$, can we find a lower bound $\alpha_{n_{0}}$ for $R(n)$, such
that:

$\displaystyle\alpha_{n_{0}}\leq R(n)=\frac{|Q_{max}(n,3)|}{n^{2}}\text{ ,
}\forall n\geq n_{0}$ (4)

This question will be addressed again in section 3.2, where heuristics for
partial solutions are discussed.

####  3.1.1 Regular Solutions

######  Theorem 5 (Klarner [Kla79]).

If $\text{gcd}(n,210)=1$ then $n^{2}$ non-attacking queens can be placed on
the $(n,3)$-board, i.e. the $(n,3)$-queens problem has a solution.

###### Proof.

There is a simple construction which gives a solution to this problem for all
$n$ whose largest prime factor exceeds $7$. For any queen
$q=(q_{1},q_{2},q_{3})$, we may write $q_{3}$ as a function of $q_{1}$ and
$q_{2}$: $q_{3}(q_{1},q_{2})$. For a non-attacking placement of $n^{2}$ queens
the following equations are then both necessary and sufficient:

$\displaystyle\text{For all $k$ with }1\leq k\leq n-1$ $\displaystyle
q_{3}(q_{1}+k,q_{2})-q_{3}(q_{1},q_{2})\neq 0$ $\displaystyle
q_{3}(q_{1}+k,q_{2})-q_{3}(q_{1},q_{2})\neq k$ $\displaystyle
q_{3}(q_{1}+k,q_{2})-q_{3}(q_{1},q_{2})\neq-k$ $\displaystyle
q_{3}(q_{1},q_{2}+k)-q_{3}(q_{1},q_{2})\neq 0$ $\displaystyle
q_{3}(q_{1},q_{2}+k)-q_{3}(q_{1},q_{2})\neq k$ $\displaystyle
q_{3}(q_{1},q_{2}+k)-q_{3}(q_{1},q_{2})\neq-k$ $\displaystyle
q_{3}(q_{1}+k,q_{2}+k)-q_{3}(q_{1},q_{2})\neq 0$ $\displaystyle
q_{3}(q_{1}+k,q_{2}+k)-q_{3}(q_{1},q_{2})\neq k$ $\displaystyle
q_{3}(q_{1}+k,q_{2}+k)-q_{3}(q_{1},q_{2})\neq-k$ (5)

The construction takes the form $q_{3}(q_{1},q_{2})=(a\cdot q_{1}+b\cdot
q_{2})\text{ mod }n$ for $a,b\in\mathbb{N}$. The listed equations become the
requirement that all of the numbers $e_{0}+e_{1}a+e_{2}b$ with
$e_{0},e_{1},e_{2}\in\\{-1,0,1\\}$ have no prime factor in common with $n$. It
is easy to check that this condition cannot be met when 2, 3, 5 or 7 is a
factor of $n$. However, if all of the prime factors of $n$ exceed 7, then it
can be $a=3$, $b=5$ which yields a solution for any such $n$. ∎

[VR81] proves the same results, so does [MS21]. A slightly weaker result is
shown by [HG81], stating that for any prime $n\geq 11$, a solution exists,
following a construction using a similar knight-move pattern.

Each solution yields a set of $n$ superimposable solutions for the
$(n,2)$-queens problem. Different choices for $a,b$ other than 3, 5 are
possible, depending on $n$. The constructed solutions are regular solutions.

Figure 11: regular solution for $n=11,d=3$

Figure 11 is an example of the construction of a regular solution for $n=11$
with the choice of $a=3$ and $b=5$. Each $z$-layer is colored in the same hue,
distinguishing the 11 superimposable solutions. Figure 15 shows the same
solution viewed from above the $xy$-plane.

Figure 12: regular solution for $n=11,d=3$

Due to their regularity, we can distinguish $n$ classes of solutions by fixing
a queen on $(1,1,s)$, $s\in\\{1,2,...,n\\}$. These classes of solutions are
equivalent, as all of them can be obtained by shifting the solutions of one
class in the previously fixed dimension and applying modulo $n$ if necessary.
A visual interpretation of this is given below in Fig. 13, by identifying the
two opposing sides in said dimension with one another. This shifting property
allows us to focus on only one class of solutions, that is, to fix a queen on
$(1,1,1)$ when discussing the enumeration and density of such solutions.

Figure 13: regular solution for $n=11,d=3$, continued

While the construction by [Kla79] shows that there exists a solution to the
$(n,d)$-queens problem for $d=3$ for infinitely many $n$, a necessary
condition for the existence of solutions remains to be shown. [VR81]
conjectures that $\text{gcd}(n,210)=1$ is not only sufficient (as shown in
Theorem 5), but also a necessary condition. So far, this conjecture is only
supported by the fact that (a) no construction method for other $n$ exists and
(b) instances for $n$, $\text{gcd}(n,210)>1$, for which the decision problem
could be solved are infeasible.

####  3.1.2 Colouring the Queen Graph

Vašek Chvátal lists Colouring the queen graphs under unsolved problems on his
website [Chv]. He writes:

The $n\times n$ queen graph has the squares of an $n\times n$ chessboard for
its vertices and two such vertices are adjacent if, and only if, queens placed
on the two squares attack each other.

Figure 14: $(8,2)$-queen graph

Continuing the introduced notation, we will call such a graph the
$(n,2)$-queen graph to distinguish it from graphs corresponding to boards of
higher dimensions. An independent set of vertices on the $(n,2)$-queen graph
corresponds to a mutually non-attacking configuration on the $(n,2)$-board.
Thus, finding a solution to the $(n,2)$-queens problem is equivalent to
finding a maximum independent set on the $(n,2)$-queen graph [FJ84]. This,
again, is equivalent to finding a maximal clique in the complement of the
queens graph. We can generalize this observation for the $(n,d)$-queen graph
for $d\geq 3$, leading to the integer programming formulation as an
independent set problem. The resulting integer programming formulation and
computational results are discussed in section 5.

If we consider a vertex colouring of the $(n,2)$-queen graph $G$, called
$G_{n,2}$, it is clear that for the chromatic number $\gamma(G_{n,2})\geq n$.
This is due to all $n$ vertices of a row, column, or the two long diagonals of
the board being adjacent on the queen graph. The problem proposed by Chvátal
asks, for which $n$ there exists an $n$-colouring of the $(n,2)$-queen graph,
meaning $\gamma(G_{n,2})=n$.

An $n$-colouring of the queen graph contains exactly $n$ nodes of each color.
As each set of $n$ nodes within the same color is an independent set on the
queen graph, it directly corresponds to a solution to the $(n,2)$-queens
problem.

######  Proposition 5.

$n$-colouring the $(n,2)$-queen graph is equivalent to finding $n$
superimposable solutions to the $(n,2)$-queens problem.

###### Proof.

$\Leftarrow$: clear. $\Rightarrow$: Through contradiction; Assume one colour
appears on $k\neq n$ vertices. Then there exists at least one colour $c$ which
appears on $k_{c}<n$ vertices. That would imply that there exists at least one
row or column, in which $c$ does not appear, which leads to a contradiction as
we require $n$ colours in each row and column to colour the graph. ∎

0 | 1 | 2 | 3 | 4
---|---|---|---|---
3 | 4 | 0 | 1 | 2
1 | 2 | 3 | 4 | 0
4 | 0 | 1 | 2 | 3
2 | 3 | 4 | 0 | 1
Table 3: certificate for the $(5,2)$-queen graph [Chv]

Following Corollary 4 and Corollary 7, it is clear that for given $n$, the
existence of an $n$-colouring of $G_{n,2}$ is a necessary condition for the
existence of a solution to the $(n,3)$-queens problem. If it can be shown that
no such an $n$-colouring of $G_{n,2}$, i.e., a set of $n$ superimposable
solutions to the $(n,2)$-queens problem exists, then the $(n,3)$-queens
problem has no solution. Chvátal [Chv] discusses this in the context of
coloring the queen graph and shows that no such set exists for $n=$ 8, 9, and
10. He further lists solutions for $n=$ 12, 14, 15, 16, 18, 20, 21, 22 and 24.
[VH04] later extends this list with certificates for $n=$ 28 and 32. Given an
$r$-colouring of the $r\times r$ graph and $s$-colouring of the $s\times s$
graph, a coloring of the $rs\times rs$ can be constructed (cf. [AY86]).

Figure 15: certificate for the $(32,2)$-queen graph [VH04]

The two following theorems give insight into sufficient conditions for the
existence of an $n$-colouring. However, a necessary condition remains to be
found. The existence of such a necessary condition would have great
implications for the problem at hand; as for the case of the existence of
(infinitely many) $n$ that do not fulfill such a condition, we could conclude
that the $(n,3)$-queens problem would not have a solution for those $n$.
Conversely, the existence and construction of superimposable solutions may aid
the construction of solutions to the (partial) $(n,3)$-queens problem.

######  Theorem 6 (Iyer, Menon [IM66]).

If $n$ is not divisible by $2$ or $3$, the chromatic number of the $n$-queens
graph is $n$.

######  Theorem 7 (Vasquez [Vas06]).

There exist infinitely many integers $n$ of the form $n=2\cdot p$ or $n=3\cdot
p$ for $p$ prime, such that the $n$-queens graph is $n$-colourable.

####  3.1.3 Stacking Superimposable Solutions

Given sufficient upper bounds to $|Q_{max}(n,d|$ or searching for solutions
for which $|Q_{max}(n,d|=n^{d-1}$ a possible approach to constructing maximal
partial solutions is to stack superimposable solutions of the $(n,d-1)$-board.
First, consider the set of all solutions to the partial $(n,d-1)$-queens
problem or a suitable chosen subset thereof. Then, find a feasible order of
stacking those solutions that yields a maximal partial solution of the
required size. [PP] follows this approach for the $(n,3)$-queens problem,
choosing a subset of the regular solutions to the $(n,2)$-queens problem.

###  3.2 Lower Bounds

####  3.2.1 Subcube Heuristic

We present a simple construction method for partial solutions on the
$(n,3)$-board. This method achieves to construct the largest maximal partial
solutions known for several of the instances in question. As it follows from
the construction of solutions of Theorem 5, it allows us to directly compute a
lower bound calculating a closed expression for given $n$. In contrast to
brute-force search algorithms or other computationally expensive heuristics,
it does so for arbitrarily large $n$.

Given a partial solution to the $(n,3)$-queens problem of $k$ queens, which we
suspect also to be a maximal partial solution, we may prove its maximality by
showing that no configuration of $k+1$ queens exists using IP. This turns out
to be a time-saving strategy compared to solving an integer program that tries
to maximize the size of a valid configuration (see 5) and allows us to make
general statements about lower bounds. Additionally, partial solutions derived
through this method may be used to warmstart the IPs.

######  Theorem 8.

For any given integer $m$, find suitable $n>m$, $n=m+k$ for which
$\text{gcd}(n,210)=1$. We can construct a partial solution of $n^{2}-3k\cdot
n+3k^{2}-2p$ queens on the $(m,3)$-board under the following condition: There
exists a regular solution to the $(n,3)$-queens problem that contains a
subcube of size $k$ with $p$ queens, meaning there are exactly $p$ queens
placed in at least one $k\times k\times k$ subset of the board.

###### Proof.

By construction. The proof idea is to find the $(m,3)$-board within in one of
the regular solutions to the $(n,3)$-queens problem, that contains the maximum
amount of queens.

Figure 16: partial solution for the $(10,3)$-board (blue) contained in a
solution to the $(11,3)$-queens problem (green) - cut off queens are light
grey

Given any solution to the $(n,3)$-queens problem, we recall that it contains
$n^{2}$ queens and each of its layers contains $n$ queens.

$\displaystyle|Q_{max}(n,3)|=n^{2}$

We obtain $Q_{s}(m,3)$, a partial solution for the $(m,3)$-board by removing
$k$ layers in each dimension of the solution. The $k$ layers in each dimension
have to be outer layers of the cube or adjacent layers, as we can shift the
solution wlog. Let us call the set of queens in the removed $x$-layers
$L_{x}$, the set of queens in the removed $y$-layers $L_{y}$ and the set of
queens in the removed $z$-layers $L_{z}$.

$\displaystyle|L_{x}|=|L_{y}|=|L_{z}|=k\cdot n$ (6)

Our goal is to find a maximal subset of the initial solution that is a partial
solution for the $(m,3)$-board, i.e. to minimize the queens removed, as:

$\displaystyle|Q_{s}(m,3)|=|Q_{max}(n,3)|-|L_{x}\cup L_{y}\cup L_{z}|$ (7)

There exists an intersection between the removed $x$-layers and $y$-layers,
the $x$-layers and $z$-layers, the $y$-layers and $z$-layers and one
intersection between all three. We define:

$\displaystyle I_{xy}:=(L_{x}\cap L_{y})\setminus L_{z}$ $\displaystyle
I_{xz}:=(L_{x}\cap L_{z})\setminus L_{y}$ $\displaystyle I_{yz}:=(L_{y}\cap
L_{z})\setminus L_{x}$ $\displaystyle I_{xyz}:=L_{y}\cap L_{y}\cap L_{z}$ (8)

We can now write

$\displaystyle|Q_{s}(m,3)|$ $\displaystyle=|Q_{max}(n,3)|-|L_{x}\cup L_{y}\cup
L_{z}|$ $\displaystyle=n^{2}-|L_{x}\cup L_{y}\cup L_{z}|$
$\displaystyle=n^{2}-\big{(}|L_{x}|+|L_{y}|+|L_{z}|\big{)}+\big{(}|I_{xy}|+|I_{xz}|+|I_{yz}|+2|I_{xyz}|\big{)}$
$\displaystyle=n^{2}-3\cdot k\cdot
n+\big{(}|I_{xy}|+|I_{xz}|+|I_{yz}|+2|I_{xyz}|\big{)}$ (9)

$I_{xyz}$ is contained in a $k\times k\times k$ cube inside the initial
$(n,3)$-board. If this subcube of size $k$ contains $p$ queens in the chosen
solution to the $(n,3)$-queens problem, i.e. $|I_{xyz}|=p$, we can conclude
that the $I_{xy}$, $I_{xz}$ and $I_{yz}$ all must contain $k^{2}-p$ queens
each. They cannot contain less, as they respective rows/columns in their
layers have to contain one queen (otherwise this leads to a contradiction as
the total cube containing $n^{2}$ queens). And they cannot contain more due to
maximality.

$\displaystyle|Q_{s}(m,3)|$ $\displaystyle=n^{2}-3\cdot k\cdot
n+\big{(}|I_{xy}|+|I_{xz}|+|I_{yz}|+2|I_{xyz}|\big{)}$
$\displaystyle=n^{2}-3\cdot k\cdot n+3\cdot(k^{2}-p)+2\cdot p$
$\displaystyle=n^{2}-3\cdot k\cdot n+3\cdot k^{2}-p$ (10)

Summarizing we conclude that we have removed $(3k\cdot n-3k^{2}-p)$ queens
from a solution to the $(n,3)$-queens problem and have obtained a partial
solution for the $(m,3)$-board, containing $n^{2}-3k\cdot n+3k^{2}-p$ queens.
∎

In order to maximize the size of the derived partial solution, we want to
minimize $p$, in particular for $p=0$ we get

######  Corollary 8.1.

For any given integer $m$, find suitable $n>m$, $n=m+k$ for which
$\text{gcd}(n,210)=1$. We can construct a partial solution of $n^{2}-3k\cdot
n+3k^{2}$ queens on the $(m,3)$-board under the following condition: There
exists a regular solution to the $(n,3)$-queens problem that contains an empty
subcube of size $k$.

Note that the existence of an empty subcube of size $k$ is trivial for $k=1$.
An empty subcube of size $2$ fits in any regular solution constructed
following Theorem 5 using the choice of parameters $a=3$ and $b=5$. Larger
subcubes may fit depending on the choice of $a,b$. However, this is dependent
on $n$, as larger $n$ allow for more choices of $a,b$.

Also note that a slight variant corollary 8.1 can be applied to obtain a bound
for the $(m,3)$ board from any partial solution of the $(n,3)$ board, $m<n$,
without the latter having to be a maximal partial solution. Here, we
additionally require the empty subcube to be adjacent to a corner of the
$(n,3)$ board. We can then always construct a subset of a partial solution on
the $(n-1,3)$-board, given a partial solution on the $(n,3)$-board for which

$\displaystyle|Q_{s}(n-1,3)|\geq|Q_{p}(n,3)|-3\cdot n+3$

In this case, the result might not be the best lower bound achievable, as it
is easily demonstrated by the fact that applying the heuristic twice with
$k=1,p=0$ is strictly worse than applying it once with $k=2,p=0$:

$\displaystyle|Q_{max}(n,3)|$ $\displaystyle=n^{2}$
$\displaystyle|Q_{s}(n-1,3)|$ $\displaystyle=n^{2}-3\cdot n+3$
$\displaystyle|Q_{s}(n-1-1,3)|$ $\displaystyle=|Q_{s}(n-1,3)|-3\cdot(n-1)+3$
$\displaystyle=n^{2}-3\cdot n+3-3\cdot(n-1)+3$ $\displaystyle=n^{2}-6\cdot
n+9$ $\displaystyle<n^{2}-6\cdot n+12$ $\displaystyle=n^{2}-3\cdot 2\cdot
n+3\cdot 2^{2}$ $\displaystyle=|Q_{s}(n-2,3)|$ (11)

This underestimation is due to the fact that the partial solutions to which
the heuristic is applied do not contain a queen in each row or column, and
thus, the corresponding statement in the construction proof becomes an
inequality (lower bound) instead of an equality.

The following table 4 compares the configurations derived from this heuristic
for $p=0$ and $k=1$, $k=2$ with the best-known results to the partial
$(n,d)$-queens problem. Entries that are proven maximal are printed in bold.
All other entries are taken from the results of [Zim02].

$n$ | current | $k=1$ | $k=2$
---|---|---|---
9 | 67 |  | 67
10 | 91 | 91 |
11 | 121 |  |
12 | 133 | 133 |
13 | 169 |  |
14 | 172 |  |
15 | 199 |  | 199
16 | 241 | 241 |
17 | 289 |  |
18 | 307 | 307 |
19 | 361 |  |
20 | 364 |  |
21 | 405 |  | 403
22 | 463 | 463 |
23 | 529 |  |

Table 4: lower bounds for $|Q_{max}(n,3)|$

The heuristic matches the results from [Zim02] for all bounds obtained with
$k=1$ and up to $n=15$ with $k=2$. However, for $n=21$, a partial solution $Q$
with $405$ queens exists. As $405>403=|Q|$, which would be the maximal subset
of a solution to the $(23,3)$-queens problem that is a partial solution for
the $(21,3)$-board, we know that the configuration of $405$ queens cannot be
such a subset. Notably, this difference of two queens on the $(21,3)$-board
turned out to be the deciding difference between 1st and 2nd place in Al
Zimmermann’s contest [Zim02].

Figure 17: partial solution of $405$ queens on the $(21,3)$-board

Further, we may now state lower bounds for $n$ that exceed the instances that
have been tackled so far (see table. 5). It is unlikely that configurations
derived through this method are also maximal partial solutions for large $n$,
as demonstrated by the configuration for the $(21,3)$-board. Instead, we
expect the maximal partial solutions for larger $n$ not to be subsets of
regular solutions of larger boards.

$n$ | current | $k=1$ | $k=2$
---|---|---|---
27 |  |  | 697
28 |  | 757 |
29 | 841 |  |
30 |  | 871 |
31 | 961 |  |
… |  |  |
35 |  |  | 1159
36 |  | 1261 |
37 | 1369 |  |
… |  |  |
39 |  |  | 1447
40 |  | 1561 |
41 | 1681 |  |
… |  |  |

Table 5: lower bounds for $|Q_{max}(n,3)|$

We may now revisit the question inspired by [McC78]:

For given $n_{0}$, can we find a lower bound $\alpha_{n_{0}}$ for $R(n)$, such
that:

$\displaystyle\alpha_{n_{0}}\leq R(n)=\frac{|Q_{max}(n,3)|}{n^{2}}\text{ ,
}\forall n\geq n_{0}$ (12)

Repeatedly applying the described heuristic to regular solutions to the
$(n.3)$-queens problem one can also easily check, that
$\lim_{n_{0}\to\infty}\alpha_{n}=1$.

######  Corollary 8.2.

For all $n$, $|Q_{max}(n,3)|\geq n^{2}-10n-32$

###### Proof.

The next largest $m>n$ with $gcd(m,210)=1$ is at most $m=n+10$. Apply the
lower bound from theorem 8 once with $k=2,p=0$ and then 8 times with
$k=1,p=0$. ∎

Note that this bound can be further improved for sufficiently large $n$.

######  Corollary 8.3.

$\lim_{n_{0}\to\infty}\alpha_{n_{0}}=1$

###### Proof.

$\displaystyle
1\geq\lim_{n_{0}\to\infty}\alpha_{n_{0}}=\liminf_{n_{0}\to\infty}R(n)\geq\lim_{n_{0}\to\infty}\frac{n_{0}^{2}-10n_{0}-32}{n^{2}}=1$

∎

###  3.3 Enumeration of Solutions

####  3.3.1 Lower Bounds

Through the construction of regular solutions following theorem 5, we obtain a
lower bound on the number of solutions for the $(n,3)$-queens problem for $n$
with $gcd(n,210)=1$. For given $n$, we may fix one of the shifting classes and
observe that there are $12$ possible directions for the stepping pattern (4 in
each dimension as for $(\pm a,\pm b)$). There are $n\cdot c(n)$ such regular
solutions for all $n$, where $c(n)$ is a function that describes how many
choices of $a,b$ there are for given $n$ considering symmetries.

Table 9 shows the currently known exact results for the number of solutions
for both full and maximal partial solutions (in cursive). Results are computed
through the IP formulation described in section 5.

$n$ | $\mathcal{Q}(n,3)$ | $n\cdot{c(n)}$ |
---|---|---|---
1 | 1 |  |
2 | 8 |  |
3 | 16 |  |
4 | 1344 |  |
5 | 1056 |  |
6 | 912 |  |
7 | 96 |  |
8 |  |  |
9 |  |  |
10 |  |  |
11 | 264 | $=11\cdot 12\cdot 2$ |
12 |  |  |
13 | 624 | $=13\cdot 12\cdot 4$ |
14 |  |  |

Table 6: Known sequence of $\mathcal{Q}(n,3)$ and partial solutions

[PP] implemented a method that gives a lower bound on $\mathcal{Q}(n,3)$ by
exhaustively computing all regular solutions. The results are listed in table
7. Note, however that they may only represent a subset of the solutions.

$n$ | lb. | $n\cdot c(n)$
---|---|---
17 | 2,040 | $17\cdot 12\cdot 10$
19 | 3,192 | $19\cdot 12\cdot 14$
23 | 6,624 | $23\cdot 12\cdot 24$
29 | 35,496 | $29\cdot 12\cdot 102$
31 | 19,344 | $31\cdot 12\cdot 52$

Table 7: Lower bound on $\mathcal{Q}(n,3)$ by [PP]

For general statements on upper bounds see section 4.4.2.

###  3.4 Open Questions

In the following, we summarize and connect some of the previously mentioned
open questions regarding the $(n,3)$-queens problem.

######  Open Question 1 (Chàtal [Chv]).

Does there exists $n_{0}$, such that for all $n\geq n_{0}$ the $(n,2)$-queen
graph is $n$-colourable?

Recall that this is equivalent to the existence of $n$ superimposable
solutions. Thus, the existence of an $n$-colouring is necessary for the
existence of a solution to the $(n,3)$-queens problem.

######  Open Question 2 (Van Rees).

Is $\text{gcd}(n,210)=1$ a necessary condition for the $(n,3)$-queens problem
to have a solution?

######  Open Question 3.

Are there non-regular solutions to the $(n,3)$-queens problem?

So far there are no certificates of non-regular solutions. Note that answering
Question 1 might also help provide insights towards Question 3. We observed
that if the only solutions existing are regular, $qc(n,3)$ would be constant
and not depend on $n$.

######  Open Question 4.

Does there exist an equivalent to the $n$-queens constant (see Theorem 3) for
$d=3$ for all $n$ with $gcd(n.210)=1$. Is there a relation between this
constant and the $n$-queens constant?

This connects to the question of whether there exist non-regular solutions for
sufficiently large $n$ and the enumeration of such solutions.

######  Open Question 5.

Does the density of the solutions to the partial $(n,3)$-queens problem
converge for $n\to\infty$?

Recall from corollary 8.2 that for $n\to\infty$, one can place $n^{2}$ queens
(in limit). The density of solutions is of particular interest for $d\geq 3$,
as we differentiate between maximal partial solutions with
$|Q_{max}(n,3)|<n^{2}$ who present a density reminiscent of the density for
the $(n,2)$-queens problem as described by [Sim21] and solutions with
$|Q_{max}(n,3)|=n^{2}$ which so far showcase an equal distribution due to
their regularity.

##  4 Generalization to Higher Dimensions

######  Theorem 9 (Nudelman [Nud95]).

A queen on the $(n,d)$-board attacks in $\frac{1}{2}(3^{d}-1)$ hyperplanes.

###### Proof.

Recall the definition of attack lines for the modular $(n,d)$-queens problem
(Problem 2). Consider all $\epsilon=(\epsilon_{1},...,\epsilon_{d})$, there
are $3^{d}-1$ non-zero possibilities. $\epsilon$ and $-\epsilon$ however
define the same hyperplane of attack. ∎

######  Corollary 9.1.

A $d$-dimensional queen on the $(n,d)$-board attacks up to
$\frac{1}{2}(3^{d}-1)\cdot(n-1)+1$ squares (including its own square).

###### Proof.

For any odd $n$, place a queen on
$(\frac{n+1}{2},\frac{n+1}{2},...,\frac{n+1}{2})$. It attacks all $n$ squares
in each of its $3^{d}-1$ hyperplanes of attack. ∎

From this we can conclude that for $n=3$, the minimal dominating set problem
on the has domination number $\gamma(G_{3,d})=1$ $\forall d$, as one queen can
attack the entire board:

$\displaystyle\frac{1}{2}(3^{d}-1)\cdot(3-1)+1=3^{d}$ (13)

One can easily check this by placing a queen on $(2,2,...,2)$, as it is also
mentioned by [LRMR22a].

######  Corollary 9.2.

A $d$-dimensional queen on the $(n,d)$-board attacks at least
$(2^{d}-1)\cdot(n-1)+1$ squares (including its own square).

###### Proof.

Place a queen on $(1,1,...,1)$. This minimizes the total squares it attacks
for each pair of two orthogonal diagonal hyperplanes of attack. Its
hyperplanes of attack are described by all non-zero vectors $\epsilon$ with
positive entries. There are $2^{d}-1$ such vectors. ∎

From this corollary it trivially follows that any single queen on the
$(2,d)$-board dominates the entire board:

######  Corollary 9.3.

$|Q_{max}(2,d)|=1$ for all $d$.

###### Proof.

$(2^{d}-1)\cdot(2-1)+1=2^{d}$ ∎

###  4.1 Existence and Construction of Solutions

######  Proposition 6.

Any solution $Q$ to the $(n,d)$-queens problem also yields $n$ superimposable
solutions to the $(n,d-1)$-queens problem in each of the dimensions of the
d-dimensional hypercube.

###### Proof.

Analog to proposition 4. ∎

######  Proposition 7.

$n^{(d-1)}$-colouring the $(n,d)$-queen graph is equivalent to finding $n$
superimposable solutions to the $(n,d)$-queens problem.

######  Theorem 10 (Van Rees [VR81]).

If $\text{gcd}(n,(2^{d}-1)!)=1$ then $n^{d-1}$ non-attacking queens can be
placed on the $(n,d)$-board, i.e. the $(n,d)$-queens problem has a solution.

###  4.2 Lower Bounds

######  Proposition 8 (trivial lower bound).

For all $n,d$, $k\geq 1$

$\displaystyle|Q_{max}(n+k,d)|\geq|Q_{max}(n,d)|$
$\displaystyle|Q_{max}(n,d+k)|\geq|Q_{max}(n,d)|$ (14)

####  4.2.1 Subscube Heuristic

Recall the subcube heuristic from theorem 8. For $d=4$, it appears that we are
looking for a $k^{4}$-subhypercube containing as many queens as possible,
contrary to $d=3$, for which we wanted to minimize the number of queens in the
$k^{3}$-cube. This is also the case for the trivial case $d=2$ as one can
verify:

######  Theorem 11.

For any given integer $m$, $n>m$, $n=m+k$, we can construct a partial solution
of $n-2k+p$ queens on the $(m,2)$-board under the following condition: There
exists a regular solution to the $(n,2)$-queens problem that contains a subset
of size $k^{2}$ with $p$ queens.

###### Proof.

Analog to theorem 8. We obtain $Q_{s}(m,2)$, a partial solution for the
$(m,2)$-board by removing $k$ layers in both dimensions of the solution. The
$k$ layers in both dimension have to be outer layers of the cube or adjacent
layers, as we can shift the solution wlog. Let us call the set of queens in
the removed $x$-layers $L_{x}$ and the set of queens in the removed $y$-layers
$L_{y}$.

$\displaystyle|L_{x}|=|L_{y}|=k$ (15)
$\displaystyle|Q_{s}(m,2)|=|Q_{max}(n,2)|-|L_{x}\cup L_{y}|$ (16)
$\displaystyle I_{xy}:=(L_{x}\cap L_{y})$ $\displaystyle
I_{x}:=I_{xy}\setminus L_{y}$ $\displaystyle I_{y}:=I_{xy}\setminus L_{x}$
(17) $\displaystyle|Q_{s}(m,2)|$ $\displaystyle=|Q_{max}(n,2)|-|L_{x}\cup
L_{y}|$ $\displaystyle=n-\big{(}|I_{xy}|+|I_{x}|+|I_{y}|\big{)}$
$\displaystyle=n-\big{(}p+(k-p)+(k-p)\big{)}$ $\displaystyle=n-2\cdot k+p$
(18)

∎

This result is apparent without proof from just looking at the $(n,2)$-board,
and indeed the $p$ term is positive, meaning that we want to maximize the
amount of queens in the subset that is the intersection of all cut layers. We
believe that this is the case for all even $d$, while for odd $d$ we want that
intersection to contain as few queens as possible. A generalization of theorem
8 for all $d$ remains to be shown. For $d=4$ we get

######  Theorem 12.

For any given integer $m$, $n>m$, $n=m+k$, we can construct a partial solution
of $n^{3}-4kn^{2}+6k^{2}n+8k^{2}-12k^{3}+p$ queens on the $(m,4)$-board under
the following condition: There exists a regular solution to the $(n,4)$-queens
problem that contains a subset of size $k^{4}$ with $p$ queens.

###### Proof.

Analog to theorem 8, by construction.
∎

######  Conjecture 1.

For all $d$ and given integer $m$, $n>m$, $n=m+k$, we can construct a partial
solution of

$\displaystyle
n^{d-1}-dkn^{d-2}+\frac{(d-1)(d-2)}{2}k^{2}n^{d-3}+\dots+(-1)^{d-1}a\cdot p$
(19)

queens on the $(m,d)$-board under the following condition: There exists a
regular solution to the $(n,d)$-queens problem that contains a subset of size
$k^{d}$ with $p$ queens.

The last term of integer $a$ is negative for even $d$ and positve for odd $d$.

######  Conjecture 2.

Consider the lower bound for $R(n,d)$ (see corollary 8.3)

$\displaystyle\alpha_{n_{0},d}\leq R(n,d)=\frac{|Q_{max}(n,d)|}{n^{d-1}}\text{
, }\forall n\geq n_{0}$

Then for all $d$

$\displaystyle\lim_{n_{0}\to\infty}\alpha_{n_{0},d}=1$

Conjecture 2 would follow from the subhypercube theorem, i.e. conjecture 1.

###  4.3 Upper Bounds

######  Proposition 9 (trivial upper bound).

For all $n,d$, $k\geq 1$

$\displaystyle|Q_{max}(n,d)|$ $\displaystyle\leq n^{d-1}$
$\displaystyle|Q_{max}(n,d+k)|$ $\displaystyle\leq|Q_{max}(n,d)|\cdot n^{k}$
(20)

####  4.3.1 Subsolution Inequalities

For any subset of the $(n,d)$-board, we may apply our knowledge of maximal
partial solutions for $(m,d)$-boards, $m<n$. Let $S^{n,d}_{m}$ denote the set
of all subsets of the $(n,d)$-board that correspond to $(m,d)$-boards, i.e.,
$m^{d}$ hypercubes. We obtain the following additional valid inequalities:

$\displaystyle\sum_{s\in S}x_{s}\leq|Q_{max}(m,d)|\;\;\;\;\;\forall S\in
S^{n,d}_{m}$ (21)

There are $|S^{n,d}_{m}|=(n-m+1)^{d}$ such subsets for each $m$.
Implementation of this approach needs to be done iteratively, as it requires
knowledge (or tight upper bounds) on maximal partial solutions for $m<n$.

Figure 18: One of the 8 $S^{11,3}_{10}$ subsolutions

These inequalities are impactful for smaller $n$. They may be used to derive
upper bounds for smaller $n$:

######  Theorem 13.

For $n,m$ with $n=k\cdot m$

$\displaystyle|Q_{max}(n,d)|\leq|Q_{max}(m,d)|\cdot k^{d}$ (22)

###### Proof.

The $(n,d)$-board can be considered as disjoint union of $k^{d}$ many
$(m,d)$-boards. ∎

######  Corollary 13.1.

$|Q_{max}(2k,d)|\leq k^{d}$.

###### Proof.

$|Q_{max}(2k,d)|\leq|Q_{max}(2,d)|\cdot k^{d}=k^{d}$ by corollary 9.3. ∎

Regarding the observation from the last corollary, see also the special case
for $k=2$ as discussed by [LRMR22a]

######  Conjecture 3 (Langlois-Rémillard, Müßig, Róldan [LRMR22a]).

$|Q_{max}(4,d)|=2^{d}$ for $d\geq 4$.

It remains to be shown if the bound is tight for all $d\geq 4$.

The following table lists new upper bounds derived from theorem 13 for
unsolved instances for $n=4,6,8$ as a function of $d$. The size of maximal
partial solutions is given in brackets, if known.

d/n |  |  | 4 |  | 6 |  | 8 | 9
---|---|---|---|---|---|---|---|---
2 |  |  | 4 (4) |  | 9 (6) |  | 16 (8) | 18 (9)
3 |  |  | 8 (7) |  | 27 (21) |  | 56 (48) | 108 (67)
4 |  |  | 16 (16) |  | 81 (80) |  | 256 | 486
5 |  |  | 32 (32) |  | 243 |  | 1024 | 2673
6 |  |  | 64 (64) |  | 729 |  | 4096 | 13851
7 |  |  | 128 (128) |  | 2187 |  | 16384 | 69984
8 |  |  | 256 |  | 6561 |  | 65536 | 341172
… |  |  | … |  | … |  | … | …
d |  |  | $2^{d}$ |  | $3^{d}$ |  | $4^{d}$ | $|Q_{max}(3,d)|\cdot 3^{d}$
Table 8: Upper bounds for $|Q_{max}(n,d)|$

Applying theorem 13 for unsolved instances at smaller $n$ and increasing $d$
yields upper bounds significantly lower than the trivial upper bound
$n^{d-1}$.

######  Corollary 13.2.

For all $n$ with $n<2^{d}$ it follows that $|Q_{max}(n,d)|<n^{(d-1)}$

###### Proof.

Compare the size of full solutions $n^{d-1}$ to the upper bound

$\displaystyle\frac{(2k)^{d-1}}{k^{d}}=\frac{2^{d-1}}{k}=\frac{2^{d}}{n}$ (23)

∎

###  4.4 Enumeration of Solutions

$n$ | $\mathcal{Q}(n,2)$ | $\mathcal{Q}(n,3)$ | $\mathcal{Q}(n,4)$ | $\mathcal{Q}(n,5)$
---|---|---|---|---
1 | 1 | 1 | 1 | 1
2 | 4 | 8 | 16 | 32
3 | 8 | 16 | 4992 | 71154
4 | 2 | 1344 | 404564 |
5 | 10 | 1056 |  |
6 | 4 | 912 |  |
7 | 40 | 96 |  |
8 | 92 |  |  |
9 | 352 |  |  |
10 | 724 |  |  |
11 | 2680 | 264 |  |
12 | 14200 |  |  |
13 | 73712 | 624 |  |
14 | 365596 |  |  |

Table 9: Known sequence of $\mathcal{Q}(n,d)$ and enumeration of maximal
partial solutions with $|Q(n,d)|<n^{d-1}$ (cursive). Solutions were computed
using the methods described in section 6.

######  Proposition 10.

$\mathcal{Q}(2,d)=2^{d}$

###### Proof.

Follows from corollary 9.3. ∎

####  4.4.1 Lower Bounds

A lower bound for all $n,d$ with $gcd(n,(2^{d}-1)!)=1$ can be formulated given
$c(n)$ (see 3.3.1) for general $d$, i.e. through a function $c(n,d)$.

####  4.4.2 Upper Bounds

The recently described enumeration of higher dimensional permutations [Kee18]
gives a first weak upper bound for $\mathcal{Q}(n,3)$, as it corresponds to
the number of solutions to the $(n,d)$-rooks problem (c.f. [OEIc]).

######  Theorem 14 (Keevash [Kee18]).

The number of $d$-dimensional permutations of order $n$ is
$(n/e^{d}+o(n))^{n^{d}}$.

######  Corollary 14.1.

$\mathcal{Q}(n,d)<(n/e^{3}+o(n))^{n^{d}}$.

###### Proof.

By proposition 2; the set of solutions to the $(n,d$)-queens problem is
contained in the set of solutions to the $(n,d$)-rooks problem. ∎

Such counting results for combinatorial designs yield bounds for further
variants or generalizations of the $(n,d)$-queens problem.

Recall theorem 3 and that for all $n$ there exists $\alpha$ such that

$\displaystyle\mathcal{Q}(n,2)=\left((1+o(1))n\cdot\frac{n}{e^{\alpha}}\right)^{n}$

which yields a first tighter bound as

$\displaystyle\mathcal{Q}(n,d)<\left((1+o(1))n\cdot\frac{n}{e^{\alpha}}\right)^{n^{d-1}}$
(24)

###  4.5 Related Problems

####  4.5.1 $(n,d)$-Queens Completion

Recall the $(n,2)$-queens completion problem concerned with whether a non-
attacking set of queens can be completed to a set that is a solution to the
$(n,2)$-queens problem. We generalize the following definition by [GMCS22]:

######  Definition 7 ($(n,d)$-queens completion threshold).

Define $qc(n,d)$ as the maximum integer with the property that any partial
$(n,d)$-queens configuration $Q$ of size at most $|Q|=qc(n,d)$ can be
completed to a maximal partial configuration. We call $qc(n,d)$ the
$(n,d)$-queens completion threshold.

######  Theorem 15 (Glock, Munhá Correia, Sudakov [GMCS22]).

For all sufficiently large $n$, we have $n/60\leq qc(n,2)\leq n/4$.

######  Theorem 16 (Gent [GJN17]).

The $(n,2)$-queens completion problem is NP-complete and #P-complete.

A first observation regarding $(n,3)$-queens completion is that there exist
squares for $n=3,5,6,7$ that may not be occupied, i.e., there exists no
maximal partial solution placing a queen on that square (see section 6.4). For
increasing $d$, we expect this phenomenon to extend to higher $n$ while also
noting that it likely vanishes for sufficiently large $n$.

Second, for $n$, for which only regular solutions exist, we can construct sets
of just three queens that cannot be completed to a maximal solution. This is
due to their linearity, i.e., the placement of all solutions described by
piecewise linear functions.

$n$ | $qc(n,3)$ | $qc(n,4)$ | $qc(n,5)$
---|---|---|---
1 | 1 | 1 | 1
2 | 1 | 1 | 1
3 | 0 | 0 | 0
4 | 1 | 0 |
5 | 0 |  |
6 | 0 |  |
7 | 0 |  |
… |  |  |
11 | 2 |  |
12 | - |  |
13 | $\leq 2$ |  |

Table 10: $qc(n,d)$

######  Proposition 11.

$qc(n,d)=1$ for all $n\leq 2$

###### Proof.

Follows directly from corollary 9.3. ∎

######  Proposition 12.

$qc(3,d)=0$

###### Proof.

Follows from corollary 9.1. Let $Q^{*}=\\{(2,2,...,2)\\}$, then the entire
board is dominated. It remains to be shown that $|Q_{max}(3,d)|>1$. To prove
this place one queen on $(1,1,...,1,1,1)$ and observe that is does not attack
$(1,1,...1,2,3)$, so there exists a partial solution of size $2$. ∎

###  4.6 Open Questions

######  Open Question 6.

Does there exists $n_{d}$, such that for all $n\geq n_{d}$ the $(n,d)$-queen
graph is $n^{d-1}$-colourable?

Again, the existence of an $n$-colouring of the $(n,d)$-queen graph is
necessary for the existence of a solution to the $(n,d)$-queens problem.

######  Open Question 7 (Van Rees).

Is $\text{gcd}(n,(2^{d}-1)!)=1$ a necessary condition for the $(n,d)$-queens
problem to have a solution?

We know that there exist sufficiently many superimposable solutions for $n$
with $\text{gcd}(n,(2^{d}-1)!)>1$ by theorem 6 and theorem 7. However, there
is no known certificate for such $n$.

######  Open Question 8.

Are there non-regular solutions to the $(n,d)$-queens problem?

All known certificates are regular; a certificate as described in question 7
(if it exists) would likely be non-regular.

######  Open Question 9.

Does there exist an equivalent to the $n$-queens constant (see Theorem 3) for
given $d$ for all $n$ with $gcd(n,(2^{d}-1)!)=1$.

This connects to whether non-regular solutions for sufficiently large $n$
exist and the enumeration of such solutions. If such constants exist for given
$d$, one may ask if there is a relation between them and the $n$-queens
constant and how it may be described.

######  Open Question 10.

Does the density of the solutions to the partial $(n,d)$-queens problem
converge for given $d$ and $n\to\infty$?

First, we may note conjecture 2 is necessary for the distribution to converge.
Second, we have observed a uniform distribution for $n$ for which only regular
solutions exist and a (empirical) distributions reminiscent of Fig. 9 for all
other $n$. It is possible that for $n\to\infty$ and provided non-regular
solutions to the $(n,d)$-queens problem exist, the distribution in question is
shaped as hinted by the empirical distributions for maximal partial solutions
and that it can be described for general $d$ in closed form.

######  Open Question 11.

Does there exist a completion bound for $d>2$ (c.f. theorem 15)? In other
words, does there exist $c_{d}$, such that for sufficiently large $n$

$\displaystyle\frac{n^{d-1}}{c_{d}}\leq qc(n,d)$ (25)

For a lower bound to $qc(n,d)$ as a function of $n$, the existence of non-
regular solutions is necessary.

##  5 Integer Programming Formulation

###  5.1 Base Model

This integer programming formulation considers the $\frac{(3^{d}-1)}{2}$
hyperplanes of attack of a queen on the $(n,d)$-board. It restricts the sum
over all squares in each of those lines to be less or equal to $1$, as two or
more queens in one such line would attack each other. Thus, the proposed
inequalities are sufficient to describe non-attacking configurations.

Recall the hyperplanes of attack identified by the vectors
$\epsilon=(\epsilon_{1},...,\epsilon_{d})$. For each pair of nonzero
$\epsilon$, $\epsilon^{{}^{\prime}}$ with $\epsilon=-\epsilon^{{}^{\prime}}$,
we require one set of inequalities summing over the squares of the board in
the direction of $\epsilon,\epsilon^{{}^{\prime}}$.

####  5.1.1 The Partial $(n,d)$-Queens Problem

Denote $S$ the set of all squares on the $(n,d)$-board and $H$ the set of all
$\frac{(3^{d}-1)}{2}$ vectors of attack. Let $L_{h}$ be the superset of all
sets of squares that lie in one of the hyperplanes corresponding to vector
$h\in H$. Then the partial $(n,d)$-queens problem can be formulated as follows

max $\displaystyle\sum_{s\in S}^{n}x_{s}$ s.t $\displaystyle\;\sum_{s\in
L}^{n}x_{s}\leq 1,$ $\displaystyle\quad\forall L\in L_{h},\quad\forall h\in H$

In the following, we will write out the formulation in detail for the
classical case $d=2$ and $d=3$.

####  5.1.2 The $(n,2)$-Queens Problem

$x_{i,j}\in\\{\,0,1\,\\}$ denotes a queen at position $(i,j)$. For $n\geq 4$:

max $\displaystyle\sum_{i=1,j=1}^{n}x_{i,j}$ s.t
$\displaystyle\;\sum_{i=1}^{n}x_{i,j}=1,$ $\displaystyle\forall j=1,\dots,n$
$\displaystyle\;\sum_{j=1}^{n}x_{i,j}=1,$ $\displaystyle\forall i=1,\dots,n$
$\displaystyle\sum_{i+j=k}^{n}x_{i,j}\leq 1,$ $\displaystyle\forall
i,j=1,\dots,n\text{ and }2\leq k\leq 2n$
$\displaystyle\sum_{i-j=k}^{n}x_{i,j}\leq 1,$ $\displaystyle\forall
i,j=1,\dots,n\text{ and }-n+1\leq k\leq n-1$ $\displaystyle
x_{i,j}\in\\{0,1\\},$ $\displaystyle\forall i,j=1,\dots,n$

The first two equalities constrain rows and columns of the board; they
correspond to the vectors $(1,0)$ and $(0,1)$. The third and fourth inequality
correspond to the vectors $(1,-1)$ and $(1,1)$, the two diagonal hyperplanes
of attack on the $(n,2)$-board.

It is important to note that the first two constraints are, in fact,
equalities, as we know that solutions to the $(n,2)$-queens problem exist for
all $n\geq 4$.

####  5.1.3 The Partial $(n,3)$-Queens Problem

$x_{i,j,k}\in\\{\,0,1\,\\}$ denotes a queen at position $(i,j,k)$. For all
$n$:

max $\displaystyle\sum_{i=1,j=1,k=1}^{n}x_{i,j,k}$ s.t
$\displaystyle\;\;\;\;\;\>\sum_{i=1}^{n}x_{i,j,k}\leq 1,$
$\displaystyle\forall j,k=1,\dots,n$
$\displaystyle\;\;\;\;\;\>\sum_{j=1}^{n}x_{i,j,k}\leq 1,$
$\displaystyle\forall i,k=1,\dots,n$
$\displaystyle\;\;\;\;\;\>\sum_{k=1}^{n}x_{i,j,k}\leq 1,$
$\displaystyle\forall i,j=1,\dots,n$
$\displaystyle\;\;\;\;\sum_{i+j=m}^{n}x_{i,j,k}\leq 1,$ $\displaystyle\forall
i,j,k=1,\dots,n\text{ and }2\leq m\leq 2n$
$\displaystyle\;\;\;\;\sum_{i-j=m}^{n}x_{i,j,k}\leq 1,$ $\displaystyle\forall
i,j,k=1,\dots,n\text{ and }-n+1\leq m\leq n-1$
$\displaystyle\;\;\;\;\sum_{i+k=m}^{n}x_{i,j,k}\leq 1,$ $\displaystyle\forall
i,j,k=1,\dots,n\text{ and }2\leq m\leq 2n$
$\displaystyle\;\;\;\;\sum_{i-k=m}^{n}x_{i,j,k}\leq 1,$ $\displaystyle\forall
i,j,k=1,\dots,n\text{ and }-n+1\leq m\leq n-1$
$\displaystyle\;\;\;\;\sum_{j+k=m}^{n}x_{i,j,k}\leq 1,$ $\displaystyle\forall
i,j,k=1,\dots,n\text{ and }2\leq m\leq 2n$
$\displaystyle\;\;\;\;\sum_{j-k=m}^{n}x_{i,j,k}\leq 1,$ $\displaystyle\forall
i,j,k=1,\dots,n\text{ and }-n+1\leq m\leq n-1$
$\displaystyle\sum_{i+j=m,j+k=p}^{n}x_{i,j,k}\leq 1,$ $\displaystyle\text{*
and }2\leq m\leq 2n,2\leq p\leq 2n$
$\displaystyle\sum_{i-j=m,j+k=p}^{n}x_{i,j,k}\leq 1,$ $\displaystyle\text{*
and }-n+1\leq m\leq n-1,\leq p\leq 2n$
$\displaystyle\sum_{j+k=m,j-k=p}^{n}x_{i,j,k}\leq 1,$ $\displaystyle\text{*
and }2\leq m\leq 2n,-n+1\leq p\leq n-1$
$\displaystyle\sum_{j-k=m,j-k=p}^{n}x_{i,j,k}\leq 1,$ $\displaystyle\text{*
and }-n+1\leq m\leq n-1,-n+1\leq p\leq n-1$ $\displaystyle\text{*}\forall
i,j,k,n$ $\displaystyle x_{i,j,k}\in\\{0,1\\},$ $\displaystyle\forall
i,j,k=1,\dots,n$

The first three inequalities correspond to the vectors
$(1,0,0),(0,1,0),(0,0,1)$. Inequalities 4 to 9 correspond to all vectors with
two non-zero entries, the diagonals. Inequalities 10 to 12 correspond to all
vectors with three non-zero entries, called triagonals. It is intuitive to see
how this concept scales for larger $d$, as the vectors of attack are
characterized by their number of non-zero entries.

Note that in the particular case of the $(n,3)$-queens problem with
$|Q_{max}(m,3)|=n^{2}$, the first three inequalities are equalities, as we fit
exactly one queen in each row. This strengthens the IP formulation, if
applicable.

###  5.2 Strengthening the IP

We present a selection of valid inequalities for the partial $(n,d)$-queens
problem. The inequalities strengthen the IP by restricting the LP relaxation
and may be used to derive upper bounds. The trivial upper bound for the
partial $(n,d)$-queens problem of $n^{d-1}$ is also the solution to the LP
relaxation, for example, by placing $\frac{1}{n}$ queens on each square. The
proposed valid inequalities significantly improve the LP and, thereby, the
solving process.

Note that while well-defined for all $d$, some of the following inequalities
improve the upper bound of maximal partial configurations, particularly for
$d>2$.

####  5.2.1 Subsolution Inequalities

Recall from 4.3.1: $S^{n,d}_{m}$ denote the set of all subsets of the
$(n,d)$-board that correspond to $(m,d)$-boards, then

$\displaystyle\sum_{s\in S}x_{s}\leq|Q_{max}(m,d)|\;\;\;\;\;\forall S\in
S^{n,d}_{m}$ (26)

We may directly translate these inequalities into additional constraints,
obtaining $\sum_{m=1}^{n-1}(n-m+1)^{d}$ inequalities for given $n,d$.

####  5.2.2 Layer Inequalities

For all layer subsets of the $(n,d)$-board, we may apply our knowledge of
maximal partial solutions for $(n,d-1)$-boards. Let $L^{n,d}$ denote the set
of all layers of the $(n,d)$-board, meaning all subsets that correspond to
$(n,d-1)$-boards (recall 1.3.1). We obtain the following additional valid
inequalities:

$\displaystyle\sum_{s\in L}x_{s}\leq|Q_{max}(n,d-1)|\;\;\;\;\;\forall L\in
L^{n,d}$ (27)

These inequalities may be applied recursively for layers of layers. For layers
of dimension $2$ or less, they can be discarded due to theorem 1.

####  5.2.3 Cube and Star Cliques

[FS19] discuss a set of clique inequalities for the $(n,2)$-queens problem.
These generalize nicely to higher dimensions. For $d=3$ and for integer $h$
odd and $i+h,j+h,k+h\leq n$, we get a clique in the shape of the corners of a
cube.

$\displaystyle x_{i,j,k}+x_{i+h,j,k}+x_{i,j+h,k}+x_{i+h,j+h,k}$
$\displaystyle+$ $\displaystyle
x_{i,j,k+h}+x_{i+h,j,k+h}+x_{i,j+h,k+h}+x_{i+h,j+h,k+h}\leq 1$ (28)

For even $h$ we further get

$\displaystyle x_{i,j,k}+x_{i+h,j,k}+x_{i,j+h,k}+x_{i+h,j+h,k}$
$\displaystyle+$ $\displaystyle
x_{i,j,k+h}+x_{i+h,j,k+h}+x_{i,j+h,k+h}+x_{i+h,j+h,k+h}$ $\displaystyle+$
$\displaystyle x_{i+\frac{h}{2},j+\frac{h}{2},k+\frac{h}{2}}\leq 1$ (29)

And for $i+h,j+h,k+h\leq n$ and $i-h,j-h,k-h\geq 1$, a third family of star-
shaped cliques (corresponding to cliques in the shape of a cross-polytope in
the respective dimension) is given by

$\displaystyle x_{i,j,k}+x_{i+h,j,k}+x_{i-h,j,k}+x_{i,j+h,k}+x_{i,j-h,k}$
$\displaystyle+$ $\displaystyle x_{i,j,k+h}+x_{i,j,k-h}\leq 1$ (30)

Figure 19: Cube cliques for $h=6$ on the $(9,3)$-board Figure 20: Star clique
for $h=3$ on the $(9,3)$-board

For general $d$, we may describe the cube inequalities as follows. For integer
$h$ odd and $s_{i}+h\leq n$ for all $i\leq d$

$\displaystyle\bigg{(}\sum_{a_{1}=0}^{1}\sum_{a_{2}=0}^{1}\dots\sum_{a_{d}=0}^{1}x_{(s_{1}+a_{1}\cdot
h,s_{2}+a_{2}\cdot h,...,s_{d}+a_{d}\cdot h)}\bigg{)}\leq 1$ (31)

And further for even $h$

$\displaystyle\Bigg{(}\bigg{(}\sum_{a_{1}=0}^{1}\sum_{a_{2}=0}^{1}\dots\sum_{a_{d}=0}^{1}x_{(s_{1}+a_{1}\cdot
h,s_{2}+a_{2}\cdot h,...,s_{d}+a_{d}\cdot h)}\bigg{)}$ (32)
$\displaystyle+x_{(s_{1}+\cdot\frac{h}{2},s_{2}+\cdot\frac{h}{2},...,s_{d}+\cdot\frac{h}{2})}\Bigg{)}\leq
1$ (33)

For the star cliques we get for for $s_{i}+h\leq n$ and $s_{i}-h\geq n$ for
all $i\leq d$

$\displaystyle x_{(s_{1},s_{2},...,s_{d})}$
$\displaystyle+x_{(s_{1}+h,s_{2},...,s_{d})}+x_{(s_{1}-h,s_{2},...,s_{d})}$
$\displaystyle+x_{(s_{1},s_{2}+h,...,s_{d})}+x_{(s_{1},s_{2}-h,...,s_{d})}$
$\displaystyle+...$
$\displaystyle+x_{(s_{1},...,s_{i}+h,...,s_{d})}+x_{(s_{1},...,s_{i}-h,...,s_{d})}$
$\displaystyle+...$
$\displaystyle+x_{(s_{1},s_{2},...,s_{d}+h)}+x_{(s_{1},s_{2},...,s_{d}-h)}\leq
1$ (34)

There are $\sum_{m=2}^{n}(n-m+1)^{d}$ cube cliques and
$\sum_{m=(2k+1)}^{n}(n-m+1)^{d}$ star cliques. The family of cliques is
polynomial in $n$ and exponential in $d$.

####  5.2.4 Odd Cycle Inequalities

Given any cycle of nodes $O$ on the $(n,d)$-queen graph, it holds that:

$\displaystyle\sum_{s\in O}x_{s}\leq\frac{|O|}{2}$ (35)

In particular for odd cycles, $|O|$ odd, we get:

$\displaystyle\sum_{s\in O}x_{s}\leq\frac{|O|-1}{2}$ (36)

Odd cycles of $|O|=3$ are all contained in the previously described clique
inequalities. Implementing odd cycle inequalities with the goal of decreasing
computational time, it may be best to consider larger cycles of queens that
only attack their respective neighbors in the cycle.

##  6 Computational Results

###  6.1 The Partial $(n,3)$-Queens Problem

All instances were solved using Gurobi version 9.5.2 with 10 randomly
generated seeds on a single Intel Xeon Gold 6246 with 24 cores, 48 threads,
and 384GB RAM. We compare the following different variants of the IP regarding
runtime, gurobi work222Gurobi work is a deterministic measure that roughly
corresponds to one second of computational time on a single thread. and nodes:

  * •

Base Model
This IP formulation only contains the necessary inequalities as laid out in
section 5.

  * •

LMR
The IP formulation by [LRMR22a], see [LRMR22b].

  * •

Cube Cliques
Base model with the additional cube clique inequalities, that correspond to
cliques in the shape of a hypercube in the respective dimension.

  * •

Star Cliques
Base model with the additional star clique inequalities, that correspond to
cliques in the shape of a cross-polytope in the respective dimension.

  * •

Cube and Star Cliques
Base model with the additional cube and star clique inequalities

  * •

Infeasibility for $|Q_{max}|+1$
This formulation adds the additional constraint to set the sum over all
squares to be $|Q_{max}|+1$. Provided we know a certificate that we believe to
be maximal, this allows us to prove that it is indeed a maximal partial
solution. Additional variants add the clique as mentioned above inequalities.

  * •

Warmstarts
The solver is warmstarted with a certificate of a maximal partial solution.
Recall that we may construct candidates for such certificates with the
mentioned heuristic methods. Additional variants add the clique as mentioned
above inequalities. As all previous variants solve $n=1,2,3$ in the root node
and under one second, the comparison to warmstarts is ignored for $n<4$.

Runtime is given in seconds, work in gurobi work units.

Additionally, we list metrics for larger instances that exceeded runtimes
feasible for the above setup and were run on a PowerEdge C6520 with two Intel
Xeon Gold 6338 with 64 cores, 128 threads, and 1TB RAM in total.

####  6.1.1 Base Model

$n$ | $|Q_{max}|$ | avg. time |  avg. min |  avg. max | avg. work |  avg. min |  avg. max | avg. nodes |  avg. min |  avg. max
---|---|---|---|---|---|---|---|---|---|---
1 | 1 | $0.00$ | $0.00$ | $0.00$ | 0.00 | $0.00$ | $0.00$ | 0.0 | 0 | 0
2 | 1 | $0.00$ | $0.00$ | $0.00$ | 0.00 | $0.00$ | $0.00$ | 0.0 | 0 | 0
3 | 4 | $0.00$ | $0.00$ | $0.00$ | 0.00 | $0.00$ | $0.00$ | 1.0 | 1 | 1
4 | 7 | $1.03$ | $0.40$ | $1.42$ | 0.05 | $0.03$ | $0.07$ | 7.1 | 4 | 12
5 | 13 | $3.66$ | $2.51$ | $5.42$ | 0.53 | $0.41$ | $0.72$ | 728.5 | 630 | 886
6 | 21 | $135.71$ | $63.11$ | $155.28$ | 22.66 | $10.32$ | $25.30$ | 41885.7 | 26876 | 47010
7 | 32 | $3351.14$ | $2830.59$ | $3612.67$ | 623.63 | $524.40$ | $664.00$ | 616683.6 | 509878 | 686108
8 | 48 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
9 | 67 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
10 | 91 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
11 | 121 | $894.79$ | $41.78$ | $1469.94$ | $159.29$ | $16.96$ | $232.51$ | $663.1$ | $1$ | $2590$
12 | 133 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
13 | 169 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
14 | $\geq 172$ |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
Table 11: Base IP for $(n,3)$

####  6.1.2 LMR

$n$ | $|Q_{max}|$ | avg. time |  avg. min |  avg. max | avg. work |  avg. min |  avg. max | avg. nodes |  avg. min |  avg. max
---|---|---|---|---|---|---|---|---|---|---
1 | 1 | $0.00$ | $0.00$ | $0.00$ | 0.00 | $0.00$ | $0.00$ | 0.0 | 0 | 0
2 | 1 | $0.00$ | $0.00$ | $0.00$ | 0.00 | $0.00$ | $0.00$ | 0.0 | 0 | 0
3 | 4 | $0.00$ | $0.00$ | $0.00$ | 0.00 | $0.00$ | $0.00$ | 1.0 | 1 | 1
4 | 7 | $1.20$ | $1.09$ | $1.27$ | $0.04$ | $0.04$ | $0.04$ | $10.9$ | $7$ | $13$
5 | 13 | $3.25$ | $2.50$ | $3.87$ | $0.42$ | $0.34$ | $0.51$ | $767.2$ | $698$ | $822$
6 | 21 | $101.12$ | $73.44$ | $183.16$ | $14.41$ | $10.25$ | $28.24$ | $31556.6$ | $23033$ | $62215$
7 | 32 | $6225.06$ | $5529.80$ | $7516.79$ | $913.89$ | $843.55$ | $1084.02$ | $870128.1$ | $774062$ | $1076920$
8 | 48 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
9 | 67 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
10 | 91 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
11 | 121 | $2029.97$ | $399.52$ | $3819.09$ | $377.67$ | $108.57$ | $560.04$ | $659.3$ | $1$ | $2520$
12 | 133 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
13 | 169 |  0000.00- | $9656.33$ |  0000.00- |  0000.00- | $1705.20$ |  0000.00- |  0000.00- | $2420$ |  0000.00-
14 | $\geq 172$ |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
Table 12: [LRMR22b] for $(n,3)$

####  6.1.3 Cube Cliques

$n$ | $|Q_{max}|$ | avg. time |  avg. min |  avg. max | avg. work |  avg. min |  avg. max | avg. nodes |  avg. min |  avg. max
---|---|---|---|---|---|---|---|---|---|---
1 | 1 | $0.00$ | $0.00$ | $0.00$ | 0.00 | $0.00$ | $0.00$ | 0.0 | 0 | 0
2 | 1 | $0.00$ | $0.00$ | $0.00$ | 0.00 | $0.00$ | $0.00$ | 0.0 | 0 | 0
3 | 4 | $0.00$ | $0.00$ | $0.00$ | 0.00 | $0.00$ | $0.00$ | 1.0 | 1 | 1
4 | 7 | $0.81$ | $0.73$ | $1.16$ | 0.02 | $0.02$ | $0.05$ | 6.2 | 4 | 11
5 | 13 | $1.61$ | $1.37$ | $1.88$ | 0.34 | $0.29$ | $0.42$ | 37.0 | 25 | 49
6 | 21 | $15.44$ | $9.38$ | $20.74$ | 2.98 | $3.64$ | $2.06$ | 1091.6 | 678 | 1688
7 | 32 | $574.01$ | $346.55$ | $1063.55$ | 138.91 | $77.66$ | $308.37$ | 62032.8 | 27419 | 106960
8 | 48 | $11343.43$ | $4532.57$ | $20103.97$ | $2029.25$ | $918.91$ | $3855.79$ | $519285.6$ | $166974$ | $1090404$
9 | 67 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
10 | 91 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
11 | 121 | $1164.61$ | $158.65$ | $2159.88$ | $277.87$ | $63.24$ | $416.13$ | $169.0$ | $1$ | $564$
12 | 133 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
13 | 169 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
14 | $\geq 172$ |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
Table 13: IP with cube cliques for $(n,3)$

####  6.1.4 Star Cliques

$n$ | $|Q_{max}|$ | avg. time |  avg. min |  avg. max | avg. work |  avg. min |  avg. max | avg. nodes |  avg. min |  avg. max
---|---|---|---|---|---|---|---|---|---|---
1 | 1 | $0.00$ | $0.00$ | $0.00$ | 0.00 | $0.00$ | $0.00$ | 0.0 | 0 | 0
2 | 1 | $0.00$ | $0.00$ | $0.00$ | 0.00 | $0.00$ | $0.00$ | 0.0 | 0 | 0
3 | 4 | $0.00$ | $0.00$ | $0.00$ | 0.00 | $0.00$ | $0.00$ | 1.0 | 1 | 1
4 | 7 | $0.76$ | $0.67$ | $0.85$ | $0.02$ | $0.02$ | $0.02$ | 6.6 | 5 | 9
5 | 13 | $3.48$ | $2.47$ | $6.25$ | $0.50$ | $0.36$ | $0.84$ | $675.2$ | $621$ | $750$
6 | 21 | $163.24$ | $149.44$ | $176.04$ | $26.68$ | $22.78$ | $30.11$ | $41836.9$ | $37195$ | $46049$
7 | 32 | $3714.34$ | $3198.91$ | $4064.65$ | $667.38$ | $576.75$ | $721.11$ | $647698.5$ | $535591$ | $614444$
8 | 48 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
9 | 67 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
10 | 91 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
11 | 121 | $1246.48$ | $62.50$ | $3011.27$ | $295.68$ | $30.98$ | $614.68$ | $800.7$ | $1$ | $2401$
12 | 133 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
13 | 169 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
14 | $\geq 172$ |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
Table 14: IP with star cliques for $(n,3)$

####  6.1.5 Cube and Star Cliques

$n$ | $|Q_{max}|$ | avg. time |  avg. min |  avg. max | avg. work |  avg. min |  avg. max | avg. nodes |  avg. min |  avg. max
---|---|---|---|---|---|---|---|---|---|---
1 | 1 | $0.00$ | $0.00$ | $0.00$ | 0.00 | $0.00$ | $0.00$ | 0.0 | 0 | 0
2 | 1 | $0.00$ | $0.00$ | $0.00$ | 0.00 | $0.00$ | $0.00$ | 0.0 | 0 | 0
3 | 4 | $0.00$ | $0.00$ | $0.00$ | 0.00 | $0.00$ | $0.00$ | 1.0 | 1 | 1
4 | 7 | $0.81$ | $0.78$ | $0.85$ | $0.03$ | $0.02$ | $0.03$ | 6.2 | 4 | 9
5 | 13 | $1.58$ | $1.36$ | $1.94$ | $0.35$ | $0.25$ | $0.45$ | $30.8$ | $25$ | $36$
6 | 21 | $16.43$ | $10.41$ | $23.48$ | $3.18$ | $2.23$ | $4.24$ | $973.2$ | $775$ | $1259$
7 | 32 | $531.74$ | $399.99$ | $826.12$ | $125.17$ | $85.50$ | $185.09$ | $43436.3$ | $20449$ | $85804$
8 | 48 | $11745.36$ | $4192.13$ | $18865.56$ | $2124.57$ | $838.47$ | $3483.81$ | $449242.0$ | $136496$ | $660154$
9 | 67 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
10 | 91 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
11 | 121 | $2001.73$ | $318.61$ | $4217.57$ | $401.27$ | $124.33$ | $614.68$ | $515.3$ | $1$ | $1591$
12 | 133 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
13 | 169 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
14 | $\geq 172$ |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
Table 15: IP with cube and star cliques for $(n,3)$

####  6.1.6 Infeasibility for $|Q_{max}|+1$

$n$ | $|Q_{max}|$ | avg. time |  avg. min |  avg. max | avg. work |  avg. min |  avg. max | avg. nodes |  avg. min |  avg. max
---|---|---|---|---|---|---|---|---|---|---
1 | 1 | $0.00$ | $0.00$ | $0.00$ | 0.00 | $0.00$ | $0.00$ | $0.0$ | $0$ | $0$
2 | 1 | $0.00$ | $0.00$ | $0.00$ | 0.00 | $0.00$ | $0.00$ | $0.0$ | $0$ | $0$
3 | 4 | $0.00$ | $0.00$ | $0.00$ | 0.00 | $0.00$ | $0.00$ | $0.0$ | $0$ | $0$
4 | 7 | $0.03$ | $0.02$ | $0.09$ | $0.01$ | $0.01$ | $0.02$ | $1$ | $1$ | $1$
5 | 13 | $2.48$ | $2.35$ | $2.59$ | $0.32$ | $0.29$ | $0.35$ | $1236.5$ | $1003$ | $1493$
6 | 21 | $349.06$ | $245.60$ | $486.80$ | $41.77$ | $29.52$ | $58.22$ | $254049.9$ | $148023$ | $402077$
7 | 32 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
8 | 48 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
9 | 67 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
10 | 91 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
11 | 121 | $0.00$ | $0.00$ | $0.01$ | $0.01$ | $0.01$ | $0.01$ | $0.0$ | $0$ | $0$
12 | 133 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
13 | 169 | $0.01$ | $0.01$ | $0.01$ | $0.01$ | $0.01$ | $0.01$ | $0.0$ | $0$ | $0$
14 | $\geq 172$ |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
Table 16: Proving infeasibility for $k+1$, Base IP for $(n,3)$

####  6.1.7 Infeasibility for $|Q_{max}|+1$, Cube Cliques

$n$ | $|Q_{max}|$ | avg. time |  avg. min |  avg. max | avg. work |  avg. min |  avg. max | avg. nodes |  avg. min |  avg. max
---|---|---|---|---|---|---|---|---|---|---
1 | 1 | $0.00$ | $0.00$ | $0.00$ | 0.00 | $0.00$ | $0.00$ | 0.0 | 0 | 0
2 | 1 | $0.00$ | $0.00$ | $0.00$ | 0.00 | $0.00$ | $0.00$ | 0.0 | 0 | 0
3 | 4 | $0.00$ | $0.00$ | $0.00$ | 0.00 | $0.00$ | $0.00$ | 0.0 | 0 | 0
4 | 7 | $0.52$ | $0.02$ | $1.01$ | $0.02$ | $0.01$ | $0.04$ | $12.6$ | $1$ | $95$
5 | 13 | $1.40$ | $1.21$ | $1.73$ | $0.26$ | $0.22$ | $0.39$ | $42.6$ | $27$ | $63$
6 | 21 | $6.26$ | $5.50$ | $8.82$ | $1.34$ | $1.21$ | $1.62$ | $1051.8$ | $687$ | $2233$
7 | 32 | $168.31$ | $116.05$ | $403.87$ | $24.86$ | $17.14$ | $60.85$ | $20909.3$ | $14391$ | $45627$
8 | 48 | $4559.43$ | $1730.25$ | $10204.63$ | $714.30$ | $290.54$ | $1548.51$ | $162308.4$ | $60534$ | $386932$
9 | 67 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
10 | 91 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
11 | 121 | $0.02$ | $0.02$ | $0.02$ | $0.02$ | $0.02$ | $0.02$ | $0.0$ | $0$ | $0$
12 | 133 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
13 | 169 | $0.04$ | $0.04$ | $0.04$ | $0.03$ | $0.03$ | $0.03$ | $0.0$ | $0$ | $0$
14 | $\geq 172$ |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
Table 17: Proving infeasibility for $k+1$, IP with cube cliques for $(n,3)$

####  6.1.8 Infeasibility for $|Q_{max}|+1$, Cube and Star Cliques

$n$ | $|Q_{max}|$ | avg. time |  avg. min |  avg. max | avg. work |  avg. min |  avg. max | avg. nodes |  avg. min |  avg. max
---|---|---|---|---|---|---|---|---|---|---
1 | 1 | $0.00$ | $0.00$ | $0.00$ | 0.00 | $0.00$ | $0.00$ | 0.0 | 0 | 0
2 | 1 | $0.00$ | $0.00$ | $0.00$ | 0.00 | $0.00$ | $0.00$ | 0.0 | 0 | 0
3 | 4 | $0.00$ | $0.00$ | $0.00$ | 0.00 | $0.00$ | $0.00$ | 0.0 | 0 | 0
4 | 7 | $0.43$ | $0.02$ | $0.95$ | $0.02$ | $0.01$ | $0.03$ | $2.4$ | $1$ | $6$
5 | 13 | $1.42$ | $1.28$ | $1.60$ | $0.28$ | $0.23$ | $0.32$ | $42.5$ | $35$ | $63$
6 | 21 | $6.52$ | $5.56$ | $10.41$ | $1.44$ | $1.28$ | $2.07$ | $1009.9$ | $741$ | $2003$
7 | 32 | $267.05$ | $228.21$ | $342.88$ | $43.11$ | $36.05$ | $53.36$ | $27297.0$ | $21729$ | $39542$
8 | 48 | $4127.32$ | $1892.48$ | $5808.65$ | $571.04$ | $317.82$ | $760.54$ | $112814.0$ | $57872$ | $160581$
9 | 67 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
10 | 91 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
11 | 121 | $0.02$ | $0.02$ | $0.02$ | $0.02$ | $0.02$ | $0.02$ | $0.0$ | $0$ | $0$
12 | 133 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
13 | 169 | $0.06$ | $0.05$ | $0.06$ | $0.04$ | $0.04$ | $0.04$ | $0.0$ | $0$ | $0$
14 | $\geq 172$ |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
Table 18: Proving infeasibility for $k+1$, IP with cube and star cliques for
$(n,3)$

####  6.1.9 Warmstarts with Base Model

$n$ | $|Q_{max}|$ | avg. time |  avg. min |  avg. max | avg. work |  avg. min |  avg. max | avg. nodes |  avg. min |  avg. max
---|---|---|---|---|---|---|---|---|---|---
4 | 7 | $1.08$ | $0.72$ | $1.45$ | $0.05$ | $0.03$ | $0.06$ | $7.0$ | $4$ | $11$
5 | 13 | $4.30$ | $2.95$ | $6.07$ | $0.56$ | $0.41$ | $0.78$ | $759.0$ | $673$ | $871$
6 | 21 | $143.08$ | $127.75$ | $151.12$ | $22.72$ | $19.97$ | $24.22$ | $44150.3$ | $38559$ | $46817$
7 | 32 | $3839.39$ | $3092.87$ | $4389.22$ | $683.22$ | $571.67$ | $7782.13$ | $666381.1$ | $518615$ | $765314$
8 | 48 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
9 | 67 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
10 | 91 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
11 | 121 | $1.10$ | $1.03$ | $1.16$ | $1.64$ | $1.55$ | $1.73$ | $1.0$ | $1$ | $1$
12 | 133 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
13 | 169 | $2.74$ | $2.55$ | $2.90$ | $3.96$ | $3.65$ | $4.22$ | $1.0$ | $1$ | $1$
14 | $\geq 172$ |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
Table 19: Base IP with warmstarts for $(n,3)$

####  6.1.10 Warmstarts with Cube and Star Cliques

$n$ | $|Q_{max}|$ | avg. time |  avg. min |  avg. max | avg. work |  avg. min |  avg. max | avg. nodes |  avg. min |  avg. max
---|---|---|---|---|---|---|---|---|---|---
4 | 7 | $0.81$ | $0.75$ | $0.87$ | $0.03$ | $0.03$ | $0.03$ | $8.4$ | $7$ | $14$
5 | 13 | $1.77$ | $1.49$ | $2.19$ | $0.37$ | $0.30$ | $0.49$ | $32.4$ | $23$ | $37$
6 | 21 | $18.14$ | $15.52$ | $20.63$ | $3.48$ | $3.04$ | $3.89$ | $1177.9$ | $765$ | $1700$
7 | 32 | $498.39$ | $401.58$ | $603.80$ | $107.35$ | $79.57$ | $144.34$ | $36634.9$ | $26126$ | $45966$
8 | 48 | $7324.733$ | $4433.61$ | $9261.85$ | $1465.36$ | $931.14$ | $1844.42$ | $280155.8$ | $170989$ | $382164$
9 | 67 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
10 | 91 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
11 | 121 | $6.79$ | $6.38$ | $7.79$ | $10.23$ | $9.58$ | $11.658$ | $1.0$ | $1$ | $1$
12 | 133 |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
13 | 169 | $30.66$ | $27.43$ | $34.63$ | $28.13$ | $26.45$ | $29.93$ | $1.0$ | $1$ | $1$
14 | $\geq 172$ |  0000.00- | $>36000.00$ |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00- |  0000.00-
Table 20: IP with cube and star cliques with warmstarts for $(n,3)$

####  6.1.11 Comparison of IP Formulations

$n$ | $|Q_{max}|$ | Base | LMR | Cube | Star | C+S | Inf | Inf C+S | ws | ws C+S | Cube∗ | Inf C∗
---|---|---|---|---|---|---|---|---|---|---|---|---
1 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $-$ | $-$ | $0.00$ | $0.00$
2 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $-$ | $-$ | $0.00$ | $0.00$
3 | 4 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $-$ | $-$ | $0.01$ | $0.00$
4 | 7 | $1.03$ | $1.20$ | $0.81$ | $0.76$ | $0.81$ | $0.03$ | $0.42$ | $1.08$ | $0.81$ | $0.77$ | $0.01$
5 | 13 | $3.66$ | $3.25$ | $1.61$ | $3.48$ | $1.58$ | $2.48$ | $1.42$ | $4.30$ | $1.77$ | $1.56$ | $0.26$
6 | 21 | $135.71$ | $101.12$ | $15.44$ | $163.24$ | $16.43$ | $349.06$ | 6.52 | $143.08$ | $18.14$ | $10.76$ | $9.79$
7 | 32 | $3351.14$ | $6225.06$ | $574.01$ | $3714.34$ | $531.74$ | $-$ | 267.05 | $3839.39$ | $498.39$ | $659.68$ | $175.23$
8 | 48 | $-$ | $-$ | $11343.43$ | $-$ | $11745.36$ | $-$ | 4127.32 | $-$ | $7324.73$ | $8464.06$ | $2604.80$
9 | 67 | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $45481.27$ | $31525.97$
10 | 91 | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $36453.71$ | $87914.31$
11 | 121 | $894.79$ | $2029.97$ | $1164.61$ | $1246.48$ | $2001.73$ | 0.00 | $0.02$ | $1.10$ | $6.70$ | $315.78$ | $0.01$
12 | 133 | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
13 | 169 | $-$ | $-$ | $-$ | $-$ | $-$ | 0.01 | $0.06$ | $2.74$ | $30.66$ | $-$ | $0.05$
14 | $\geq 172$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
Table 21: Runtime comparison for $(n,3)$

The fastest variant is marked bold for instances where the base model exceeds
$10s$ runtime and excludes the singular runs* on Intel Xeon Gold 6338. We note
that warmstarts with suitable certificates produce no significant speedup, as
the computationally expensive part of the solving process remains to close the
dual. This, however, can be significantly improved by introducing the
discussed clique inequalities and by proving infeasibility for solutions of
greater size than the known certificates instead.
For $n=11,13$, the infeasibility of a larger solution $|Q_{max}|+1$ is
trivially solved as it already violates the LP relaxation. Further, the
existence and construction of a solution of size $n\^{A}{{}^{2}}$ is known due
to theorem 5 theorem 10. Computational results are still provided for
completeness. However, they will be ignored when comparing the variants due to
the trivial result.

###  6.2 The Partial $(n,4)$-Queens Problem

####  6.2.1 Base Model

$n$ | $|Q_{max}|$ | avg. time |  avg. min |  avg. max | avg. work |  avg. min |  avg. max | avg. nodes |  avg. min |  avg. max
---|---|---|---|---|---|---|---|---|---|---
1 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.0$ | $0$ | $0$
2 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.0$ | $0$ | $0$
3 | 6 | $0.02$ | $0.02$ | $0.02$ | $0.02$ | $0.02$ | $0.02$ | $1.0$ | $1$ | $1$
4 | 16 | $0.80$ | $0.56$ | $0.99$ | $0.41$ | $0.33$ | $0.45$ | $1.0$ | $1$ | $1$
5 | 38 | $-$ | $>36000.00$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
6 | 80 | $569.57$ | $137.25$ | $1437.64$ | $169.51$ | $98.72$ | $289.15$ | $430.5$ | $31$ | $2020$
7 | 145 | $-$ | $>36000.00$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
Table 22: Base IP for $(n,4)$

####  6.2.2 LMR

$n$ | $|Q_{max}|$ | avg. time |  avg. min |  avg. max | avg. work |  avg. min |  avg. max | avg. nodes |  avg. min |  avg. max
---|---|---|---|---|---|---|---|---|---|---
1 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.0$ | $0$ | $0$
2 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.0$ | $0$ | $0$
3 | 6 | $0.01$ | $0.01$ | $0.01$ | $0.01$ | $0.01$ | $0.01$ | $1.0$ | $1$ | $1$
4 | 16 | $0.09$ | $0.07$ | $0.15$ | $0.08$ | $0.08$ | $0.10$ | $1.0$ | $1$ | $1$
5 | 38 | $-$ | $>36000.00$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
6 | 80 | $760.08$ | $291.53$ | $2246.26$ | $202.53$ | $118.34$ | $483.90$ | $460.9$ | $55$ | $2570$
7 | 145 | $-$ | $>36000.00$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
Table 23: [LRMR22b] for $(n,4)$

####  6.2.3 All additional Inequalities

$n$ | $|Q_{max}|$ | avg. time |  avg. min |  avg. max | avg. work |  avg. min |  avg. max | avg. nodes |  avg. min |  avg. max
---|---|---|---|---|---|---|---|---|---|---
1 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.0$ | $0$ | $0$
2 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.0$ | $0$ | $0$
3 | 6 | $0.02$ | $0.02$ | $0.02$ | $0.03$ | $0.03$ | $0.03$ | $1.0$ | $1$ | $1$
4 | 16 | $0.21$ | $0.13$ | $0.31$ | $0.19$ | $0.16$ | $0.23$ | $1.0$ | $1$ | $1$
5 | 38 | $-$ | $>36000.00$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
6 | 80 | $725.91$ | $438.90$ | $1637.14$ | $276.35$ | $220.12$ | $435.53$ | $67.9$ | $15$ | $196$
7 | 145 | $-$ | $>36000.00$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
Table 24: IP with cube- and star cliques, layer- and subsolution inequalities
for $(n,4)$

####  6.2.4 Infeasibility for $|Q_{max}|+1$

$n$ | $|Q_{max}|$ | avg. time |  avg. min |  avg. max | avg. work |  avg. min |  avg. max | avg. nodes |  avg. min |  avg. max
---|---|---|---|---|---|---|---|---|---|---
1 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.0$ | $0$ | $0$
2 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.0$ | $0$ | $0$
3 | 6 | $0.02$ | $0.02$ | $0.02$ | $0.02$ | $0.02$ | $0.03$ | $1.0$ | $1$ | $1$
4 | 16 | $0.67$ | $0.55$ | $0.80$ | $0.28$ | $0.23$ | $0.34$ | $1.0$ | $1$ | $1$
5 | 38 | $-$ | $>36000.00$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
6 | 80 | $879.43$ | $638.87$ | $2072.33$ | $173.93$ | $152.10$ | $303.54$ | $4545.6$ | $3077$ | $6347$
7 | 145 | $-$ | $>36000.00$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
Table 25: Proving infeasibility for $|Q_{max}|+1$, Base IP for $(n,4)$

####  6.2.5 Infeasibility for $|Q_{max}|+1$, all additional Inequalities

$n$ | $|Q_{max}|$ | avg. time |  avg. min |  avg. max | avg. work |  avg. min |  avg. max | avg. nodes |  avg. min |  avg. max
---|---|---|---|---|---|---|---|---|---|---
1 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.0$ | $0$ | $0$
2 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.0$ | $0$ | $0$
3 | 6 | $0.02$ | $0.02$ | $0.02$ | $0.02$ | $0.02$ | $0.02$ | $1.0$ | $1$ | $1$
4 | 16 | $0.01$ | $0.01$ | $0.01$ | $0.01$ | $0.01$ | $0.01$ | $0.0$ | $0$ | $0$
5 | 38 | $-$ | $>36000.00$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
6 | 80 | $10.68$ | $8.58$ | $17.49$ | $9.21$ | $7.75$ | $15.30$ | $1.0$ | $1$ | $1$
7 | 145 | $-$ | $>36000.00$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
Table 26: Proving infeasibility for $|Q_{max}|+1$, IP with cube- and star
cliques, layer- and subsolution inequalities for $(n,4)$

####  6.2.6 Warmstarts with Base Model

$n$ | $|Q_{max}|$ | avg. time |  avg. min |  avg. max | avg. work |  avg. min |  avg. max | avg. nodes |  avg. min |  avg. max
---|---|---|---|---|---|---|---|---|---|---
1 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.0$ | $0$ | $0$
2 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.0$ | $0$ | $0$
3 | 6 | $0.02$ | $0.02$ | $0.02$ | $0.02$ | $0.02$ | $0.02$ | $1.0$ | $1$ | $1$
4 | 16 | $0.57$ | $0.48$ | $0.63$ | $0.31$ | $0.30$ | $0.32$ | $1.0$ | $1$ | $1$
5 | 38 | $-$ | $>36000.00$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
6 | 80 | $64.98$ | $62.51$ | $67.19$ | $41.27$ | $39.96$ | $42.66$ | $1.0$ | $1$ | $1$
7 | 145 | $-$ | $>36000.00$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
Table 27: Warmstarts on base IP for $(n,4)$

####  6.2.7 Warmstarts with all additional Inequalities

$n$ | $|Q_{max}|$ | avg. time |  avg. min |  avg. max | avg. work |  avg. min |  avg. max | avg. nodes |  avg. min |  avg. max
---|---|---|---|---|---|---|---|---|---|---
1 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.0$ | $0$ | $0$
2 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.0$ | $0$ | $0$
3 | 6 | $0.02$ | $0.02$ | $0.02$ | $0.03$ | $0.03$ | $0.03$ | $1.0$ | $1$ | $1$
4 | 16 | $0.12$ | $0.10$ | $0.12$ | $0.14$ | $0.13$ | $0.15$ | $1.0$ | $1$ | $1$
5 | 38 | $-$ | $>36000.00$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
6 | 80 | $19.77$ | $16.91$ | $26.88$ | $23.99$ | $20.76$ | $32.18$ | $1.0$ | $1$ | $1$
7 | 145 | $-$ | $>36000.00$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
Table 28: Warmstarts on IP with cube- and star cliques, layer- and subsolution
inequalities for $(n,4)$

####  6.2.8 Comparison of IP Formulations

$n$ | $|Q_{max}|$ | Base | LMR | Inq. | Inf | Inf Inq. | ws | ws Inq.
---|---|---|---|---|---|---|---|---
1 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$
2 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$
3 | 6 | $0.02$ | $0.01$ | $0.02$ | $0.02$ | $0.02$ | $0.02$ | $0.02$
4 | 16 | $0.80$ | $0.09$ | $0.21$ | $0.67$ | $0.01$ | $0.57$ | $0.12$
5 | 38 | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
6 | 80 | $569.57$ | $760.08$ | $725.91$ | $879.43$ | 10.68 | $64.98$ | $19.77$
7 | 145 |  yyyyyyy$-$ |  yyyyyyy$-$ |  yyyyyyy$-$ |  yyyyyyy$-$ |  yyyyyyy$-$ |  yyyyyyy$-$ |  yyyyyyy$-$
Table 29: Runtime comparison for $(n,4)$

The fastest variant is marked bold for instances where the base model exceeds
$10s$ runtime. For $d=4$, the smaller instances up to $n=4$ solve too fast and
in the root node, leaving little room for comparing the proposed variants. In
contrast to $d=3$, warmstarts with suitable certificates already produce a
speedup by roughly one order of magnitude compared to the respective variant
without a warmstart for $n=6$. The additional clique inequalities, layer- and
subsolution inequalities do not provide a significant speedup for $n=6$ by
themselves; however, they reduce the number of nodes by one order of
magnitude. We expect the inequalities to result in a larger speedup for
instances $n>6$, as a similar effect can be observed for $d=3$ (for smaller
instances, the additional inequalities may slow down the solving process,
which outweighs the speedup through the reduction of nodes).

As is the case with $d=3$, the difficulty of the instances lies in the dual,
and the mentioned additional inequalities can greatly improve the performance
of closing the dual. Proving a solution of size $|Q_{max}|+1$ is infeasible
(provided we know a certificate that we believe to be maximal) is the fastest
method for $d=4,n=6$.

###  6.3 The Partial $(n,5)$-Queens Problem

####  6.3.1 Base Model

$n$ | $|Q_{max}|$ | avg. time |  avg. min |  avg. max | avg. work |  avg. min |  avg. max | avg. nodes |  avg. min |  avg. max
---|---|---|---|---|---|---|---|---|---|---
1 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.0$ | $0$ | $0$
2 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.0$ | $0$ | $0$
3 | 11 | $0.78$ | $0.58$ | $1.07$ | $0.42$ | $0.34$ | $0.50$ | $1.0$ | $1$ | $1$
4 | 32 | $21.14$ | $18.14$ | $23.82$ | $14.14$ | $13.02$ | $15.86$ | $1.0$ | $1$ | $1$
5 | $\geq 90$ | $-$ | $>36000.00$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
Table 30:  Base IP for $(n,5)$

####  6.3.2 LMR

$n$ | $|Q_{max}|$ | avg. time |  avg. min |  avg. max | avg. work |  avg. min |  avg. max | avg. nodes |  avg. min |  avg. max
---|---|---|---|---|---|---|---|---|---|---
1 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.0$ | $0$ | $0$
2 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.0$ | $0$ | $0$
3 | 11 | $0.20$ | $0.15$ | $0.29$ | $0.12$ | $0.11$ | $0.15$ | $1.0$ | $1$ | $1$
4 | 32 | $3.38$ | $2.66$ | $5.30$ | $1.83$ | $1.57$ | $2.61$ | $1.0$ | $1$ | $1$
5 | $\geq 90$ | $-$ | $>36000.00$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
Table 31:  [LRMR22b] for $(n,5)$

####  6.3.3 All additional Inequalities

$n$ | $|Q_{max}|$ | avg. time |  avg. min |  avg. max | avg. work |  avg. min |  avg. max | avg. nodes |  avg. min |  avg. max
---|---|---|---|---|---|---|---|---|---|---
1 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.0$ | $0$ | $0$
2 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.0$ | $0$ | $0$
3 | 11 | $0.53$ | $0.40$ | $0.66$ | $0.27$ | $0.23$ | $0.31$ | $1.0$ | $1$ | $1$
4 | 32 | $2.40$ | $1.75$ | $4.63$ | $14.14$ | $1.93$ | $3.76$ | $1.0$ | $1$ | $1$
5 | $\geq 90$ | $-$ | $>36000.00$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
Table 32:  IP with cube- and star cliques, layer- and subsolution inequalities
for $(n,5)$

####  6.3.4 Infeasibility for $|Q_{max}|+1$

$n$ | $|Q_{max}|$ | avg. time |  avg. min |  avg. max | avg. work |  avg. min |  avg. max | avg. nodes |  avg. min |  avg. max
---|---|---|---|---|---|---|---|---|---|---
1 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.0$ | $0$ | $0$
2 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.0$ | $0$ | $0$
3 | 11 | $2.11$ | $0.87$ | $4.36$ | $0.74$ | $0.39$ | $1.17$ | $102.7$ | $1$ | $873$
4 | 32 | $44.47$ | $44.47$ | $167.89$ | $18.21$ | $9.99$ | $38.14$ | $604.0$ | $1$ | $5939$
5 | $\geq 90$ | $-$ | $>36000.00$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
Table 33: Proving infeasibility for $|Q_{max}|+1$, base IP for $(n,5)$

####  6.3.5 Infeasibility for $|Q_{max}|+1$, all additional Inequalities

$n$ | $|Q_{max}|$ | avg. time |  avg. min |  avg. max | avg. work |  avg. min |  avg. max | avg. nodes |  avg. min |  avg. max
---|---|---|---|---|---|---|---|---|---|---
1 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.0$ | $0$ | $0$
2 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.0$ | $0$ | $0$
3 | 11 | $0.40$ | $0.31$ | $0.61$ | $0.26$ | $0.23$ | $0.31$ | $1.0$ | $1$ | $1$
4 | 32 | $0.07$ | $0.07$ | $0.07$ | $0.07$ | $0.07$ | $0.07$ | $0.0$ | $0$ | $0$
5 | $\geq 90$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $-$
Table 34: Proving infeasibility for $|Q_{max}|+1$, IP with cube- and star
cliques, layer- and subsolution inequalities for $(n,5)$

####  6.3.6 Comparison of IP Formulations

$n$ | $|Q_{max}|$ | Base | LMR | Inq. | Inf | Inf Inq.
---|---|---|---|---|---|---
1 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$
2 | 1 | $0.00$ | $0.00$ | $0.00$ | $0.00$ | $0.00$
3 | 11 | $0.78$ | $0.20$ | $0.53$ | $2.11$ | $0.31$
4 | 32 | $21.14$ | $3.38$ | $2.40$ | $44.47$ | 0.07
5 | $\geq 90$ |  yyyyyyy$-$ |  yyyyyyy$-$ |  yyyyyyy$-$ |  yyyyyyy$-$ |  yyyyyyy$-$
Table 35: Runtime comparison for $(n,5)$

Again, the fastest variant is marked bold for $n=4$ where the base model
exceeds $10s$ runtime. For $d=5$, this is the case for only $n=4$, as $n=5$
remains unsolved and $n=1,2,3$ solves under 1 second.

###  6.4 Density of Solutions

Results for $n=1,2$ are excluded, as they follow trivially from proposition
10. The plots show the density for each 2d-layer (in order and row-wise), the
color scale is chosen to visualize the empirical density reminiscent of a
higher dimensional equivalent to the density described by [Sim21].

####  6.4.1 $d=3$

Figure 21: Density for the $(3,3)$-queens problem

Figure 22: Density for the $(4,3)$-queens problem

Figure 23: Density for the $(5,3)$-queens problem

Figure 24: Density for the $(6,3)$-queens problem

Figure 25: Density for the $(7,3)$-queens problem

Due to all solutions for $n=11$ and $n=13$ being regular, the density for
those $n$ is simply the uniform distribution. However we may describe their
structure further for a single class by fixing a queen on $(1,1,1)$.

Figure 26: Density of the $(0,0,0)$-class of the maximal partial solutions for
the $(11,3)$-queens problem

####  6.4.2 $d=4$

Figure 27: Density for the $(3,4)$-queens problem

Figure 28: Density for the $(4,4)$-queens problem (limited to the first two
layers due to symmetry)

##  7 Conclusions and Future Work

We provided a first overview of the $(n,2)$-queens problem, connecting and
improving existing results of related problems and methods for both
theoretical results and the solving of large instances of the $(n,d)$-queens
problem. We compare several different IP formulations and achieve a speedup of
$15.5\times-71.2\times$ less computational time compared to [LRMR22a], who
recently succeeded in breaking new, never-before-solved instances. Our results
suggest that breaking additional, previously unsolved instances with the
proposed methods or improvements is likely possible.

The problem of solving instances of the $(n,d)$-queens problem for $d\geq 3$
can be summarized as follows:

  * •

Construction of Solutions
On the primal side, we discussed several heuristic approaches to constructing
solutions that are either maximal partial solutions or very close to the
optimum. Additionally, even if we discard this knowledge, the computational
results showed that finding a solution of the (yet to be proven) optimal value
takes an insignificant part of the total computational time.

  * •

Proving Maximality of Solutions
The time-intensive part of the solving process remains to close the dual. We
greatly improved the computational time by adding additional valid
inequalities, resulting in a significantly lower optimum to the LP relaxation
of the problem. The corresponding theoretical results are described in section
4.3. These and the computational results suggest that the potential speedup
scales with $d$.

We emphasize that this problem structure differs from the classic
$(n,2)$-queens problem in complexity and, more importantly, as the former
comes down to a feasibility problem and does not inherit the difficulty of
closing the dual. Here, we showed that certain clique inequalities, in
particular, the (hyper-)cube inequalities as discussed by [FS19] for the
$(n,2)$-queens problem improve on the dual and thereby computational time.

Following this conclusion, a recipe for solving further instances seems to be
a combination of (a) improved theoretical results, also for subsets of the
instances, (b) further study of clique inequalities and clique separation, and
(c) making use of the unique structure of the problem during the solving
process, for example by its corresponding symmetry group. One may also compare
the IP with constraint programming and SAT solvers, specifically for those
instances where we suspect already knowing the maximal partial solution.

Additionally, the generalization to the $(n,d)$-queens problem opens up the
entire branch of variations to the classical $(n,2)$-queens problem to their
higher dimensional equivalents. Through discussing the $(n,d)$-queens problem,
we have also gained insight into $(n,d)$-queens completion and shown some
preliminary results. Similarly, one may be interested in the many possible
variations and related problems as discussed in the introductory section:
minimum dominating sets, different board structures (or underlying graphs),
and varying pieces (or ’vision’). These topics may be discussed in future
work.

Finally, we have listed a number of open questions regarding the
$(n,d)$-queens problem. We believe that a density function of the
$(n,d)$-queens problem for $d\geq 3$ exists. If one imagines a hypersphere
intersecting with a hypercube in the corresponding dimension $d$, then the
density is the highest in the $(n,d)$-cube around the boundary of the sphere
and lower in the middle and at all corners of the cube. We can observe this
for $d=2$, see Fig. 9 and empirically from the densities shown in section 6.4.
We may follow the approach [Sim21] to show that such a density exists;
however, it is not clear if the distinction between $n$ for which regular
solutions exist and those for which they do not allow for this approach. As we
have noted, proving that such a density exists would imply the existence of a
non-regular solution of full size $n^{d-1}$.

In the following two tables, we summarize the results regarding the current
state of solved instances for the $(n,d)$-queens problem (c.f. [LRMR22a]).

d \n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13
---|---|---|---|---|---|---|---|---|---|---|---|---|---
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1
2 | 1 | 1 | 2 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13
3 | 1 | 1 | 4 | 7 | 13 | 21 | 32 | 48 | 67 | 91 | 121 |  | 169
4 | 1 | 1 | 6 | 16 | 38 | 80 | 145 |  |  |  |  |  |
5 | 1 | 1 | 11 | 32 |  |  |  |  |  |  |  |  |
6 | 1 | 1 | 19 | 64 |  |  |  |  |  |  |  |  |
7 | 1 | 1 | 32 | 128 |  |  |  |  |  |  |  |  |
8 | 1 | 1 | 52 |  |  |  |  |  |  |  |  |  |

Table 36: Known maximal partial solutions to the $(n,d)$-queens problem

##  8 Bibliography

## References

  * [AR21] Hannah Alpert and Érika Roldán.  Art gallery problem with rook and queen vision.  Graphs and Combinatorics, 37:621–642, 2021.  https://doi.org/10.48550/arXiv.1810.10961.
  * [AY86] Bruce Abramson and Mordechai M Yung.  Construction through decomposition: A divide-and-conquer algorithm for the N-queens problem.  In Proceedings of 1986 ACM Fall joint computer conference, pages 620–628, 1986.  https://dl.acm.org/doi/10.5555/324493.324620.
  * [Ber91] B Bernhardsson.  Explicit solutions to the N-queens problem for all N.  ACM SIGART Bulletin, 2(2), 1991.  https://doi.org/10.1145/122319.122322.
  * [BS08] Jordan R Bell and Brett Stevens.  Results for the n-queens problem on the Möbius board.  Australas. J Comb., 42:21–34, 2008.
  * [Chv] V. Chvátal.  Colouring the queen graphs.  http://users.encs.concordia.ca/~chvatal/queengraphs.html, Accessed: 15.09.2023.
  * [EH69] RC Moore EJ Hoffman, JC Loessi.  Constructions for the Solution of the m Queens Problem.  Mathematics Magazin, 32(2), 1969.  https://doi.org/10.1080/0025570X.1969.11975924.
  * [FJ84] LR Foulds and DG Johnston.  An application of graph theory and integer programming: chessboard non-attacking puzzles.  Mathematics Magazine, 57(2):95–104, 1984.  https://doi.org/10.1080/0025570X.1984.11977086.
  * [FS19] Matteo Fischetti and Domenico Salvagnin.  Finding First and Most-Beautiful Queens by Integer Programming.  2019\.  https://arxiv.org/abs/1907.08246.
  * [GJN17] Ian P Gent, Christopher Jefferson, and Peter Nightingale.  Complexity of n-queens completion.  Journal of Artificial Intelligence Research, 59:815–848, 2017.  https://doi.org/10.1613/jair.5512.
  * [GMCS22] Stefan Glock, David Munhá Correia, and Benny Sudakov.  The n-queens completion problem.  Research in the Mathematical Sciences, 9(3):41, 2022.  https://doi.org/10.48550/arXiv.2111.11402.
  * [HG81] Agnes M Herzberg and Cyril WL Garner.  Latin queen squares.  Utilitas Math, 20:143–154, 1981.  https://doi.org/10.1016/0097-3165(83)90048-1.
  * [HHS04] 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.  https://doi.org/10.1016/S0012-365X(03)00176-6.
  * [IM66] MR Iyer and VV Menon.  On Coloring the n$\times$ n Chessboard.  The American Mathematical Monthly, 73(7):721–725, 1966.  https://doi.org/10.1080/00029890.1966.11970823.
  * [JB09] B Stevens J Bell.  A survey of known results and research areas for n-queens.  Discrete Mathematics, 309(1), 2009.  https://doi.org/10.1016/j.disc.2007.12.043.
  * [KB20] Thorsten Koch and Timo Berthold.  Notes on Mathematical Modelling.  CO@Work, 2020.  https://co-at-work.zib.de/berlin2020/.
  * [Kee18] Peter Keevash.  The existence of designs ii.  2018\.  https://doi.org/10.48550/arXiv.1802.05900.
  * [Kla79] David A Klarner.  Queen squares.  J. Recreational Math, 12(3):177–178, 1979.
  * [LRMR22a] Alexis Langlois-Rémillard, Christoph Müßig, and Érika Róldan.  Complexity of Chess Domination Problems.  arXiv preprint arXiv:2211.05651, 2022.
  * [LRMR22b] Alexis Langlois-Rémillard, Christoph Müßig, and Érika Róldan.  Queen problems on the d-dimensional hypercube., 2022.  gist.github.com/PhoenixSmaug/5dddbf431d8d07b069f1a4e0c8d7024b.
  * [Lur17] Zur Luria.  New bounds on the number of n-queens configurations.  arXiv preprint arXiv:1705.05225, 2017.
  * [McC78] Carl P McCarty.  Queen squares.  The American Mathematical Monthly, 85(7):578–580, 1978.
  * [MS21] Stephen Montgomery-Smith.  personal communication, 2021.
  * [MW05] Brendan D McKay and Ian M Wanless.  On the number of Latin squares.  Annals of combinatorics, 9(3):335–344, 2005.  https://doi.org/10.48550/arXiv.0909.2101.
  * [NAB23] Parth Nobel, Akshay Agrawal, and Stephen Boyd.  Computing tighter bounds on the n-queens constant via newton’s method.  Optimization Letters, 17(5):1229–1240, 2023.  https://doi.org/10.1007/s11590-022-01933-2.
  * [Nud95] SP Nudelman.  The modular n-queens problem in higher dimensions.  Discrete Mathematics, 146(1-3):159–167, 1995.  https://doi.org/10.1016/0012-365X(94)00161-5.
  * [OEIa] OEIS.  A000170 - Number of ways of placing n nonattacking queens on an n x n board.  https://oeis.org/A000170, accessed: 01.10.2023.
  * [OEIb] OEIS.  A359441 - The n-Queens Constant.  https://oeis.org/A359441, accessed: 01.10.2023.
  * [OEIc] OEIS.  Number of Latin squares of order n.  https://oeis.org/A002860, accessed: 10.08.2023.