Attack of the Queens

The Eight Queens Puzzle is an old brainteaser that asks: How can you place eight queens on a chessboard so that no two queens are attacking each other?

It turns out there are many solutions, but here’s a particularly symmetrical one:

In Martin Gardner’s book “The Last Recreations”, I learned about a nice generalization of this problem that asks instead: How many queens can you place on a chessboard so that each queen is attacking exactly one other queen? Or attacking exactly two others? Or exactly three others? Etc. [These are “generalizations” in the sense that the original eight queens problem requires that each queen is attacking exactly zero other queens.]

For example, here are some optimal solutions to these questions:

This post describes how to find solutions like these, why they are optimal, and explores some other generalizations.

History & Known Results

While the Eight Queens problem has been around since the nineteenth century, and has been extensively researched, these other variants are more recent and have received less attention. Nonetheless, various results are known, which are summarized below.

First, let’s define

\[ \begin{aligned} & \text{Maximum number of queens that can be}\\ Q_k(n) \hspace{0.1in} = \hspace{0.2in} & \text{placed on an } n \times n \text{ chessboard so that each } \\ & \text{queen is attacking exactly } k \text{ other queens}. \end{aligned}\]

So, the examples in Figure 1 show that

\[ \begin{aligned} Q_1(8) &\geq 10 \\ Q_2(8) &\geq 14 \\ Q_3(8) &\geq 18 \\ Q_4(8) &\geq 21 \end{aligned}\]

Martin Gardner attributes the first questions about $Q_k(n)$ to Scott Kim in 1980-1981 (in the Journal of Recreational Mathematics). A survey by Bell & Stevens says that Gik (in the Soviet Union) also raised similar questions around the same time, and it appears that substantial progress was made by Peter Hayes in 1992 (also in the Journal of Recreational Mathematics). I haven’t been able to track down these original articles, so what follows is pieced together based on results reported by Gardner and Bell & Stevens, together with my own investigations.

Firstly, $Q_k(n)$ really only makes sense for $k \leq 4$ because it’s impossible to place queens (on a board of any size) so that every queen is attacking 5 or more other queens. (To see this, consider the right-most column that has a queen in it; if there are multiple queens in that column, choose the top-most one. That queen has no queens anywhere to its right, nor any directly above it, so of the 8 directions that queen can attack, at least 4 of them have no queens (SE, E, NE are all to the right and N is directly above); therefore, it can be attacking at most 4 queens.)

Evidently, the Hayes article completely settles the question of $Q_2(n)$ and $Q_4(n)$ , giving an explicit formula for each of them, namely $Q_2(n) = 2n - 2$ (for $n \geq 3$ ) and $Q_4(n) = 3n - 3$ (for $n \geq 6$ ). This fact is documented in the OEIS here and here.

So the interesting cases are $Q_1(n)$ and $Q_3(n)$ , and for both of these, some interesting upper-bounds are known.

Bounds when k = 1

According to Bell & Stevens, Hayes showed that $Q_1(n) \leq \lfloor 4n/3 \rfloor$ ; a slightly sharper bound of $Q_1(n) \leq 2\lfloor 2n/3 \rfloor$ is given, without proof, by Jud McCrainie here. However, the two bounds are actually equivalent once you realize that $Q_1(n)$ is always even; indeed, if every queen is attacking exactly one other queen, then the queens must all occur in pairs that are threatening each other.

And taking this argument one step further actually leads to a direct proof of the sharper bound:

Observation: $Q_1(n) \leq 2\lfloor 2n/3 \rfloor$ .

Proof: Consider a pair of queens that are attacking each other. They must be in two different columns or two different rows (or both, if they are attacking each other diagonally). In either case, they occupy at least 3 rows/columns and there can be no other queens in those rows/columns. Since there are a total of 2n rows and columns, and each pair of queens stakes a claim to at least 3 of them, there can be at most $\lfloor 2n/3 \rfloor$ pairs of queens, i.e., at most $2\lfloor 2n/3 \rfloor$ queens total. QED

Incidentally, when $n = 8$ , this gives a bound of $Q_1(8) \leq 10$ , showing that the configuration in Figure 1 is indeed optimal. Here are some other optimal configurations for small values of $n$ :

More terms of the series (along with more examples) are given in A051754 of the OEIS, and later we’ll see how to actually find these solutions (and much larger ones!) using powerful “SAT Solver” algorithms.

Note that apart from $n = 3$ and $n = 5$ all these examples achieve the bound $2 \lfloor 2n/3 \rfloor$ , leading to the following sensible conjecture (which has been verified for $n \leq 65$ ).

Conjecture: $Q_1(n) = 2\lfloor 2n/3 \rfloor$ for all $n \geq 6$ .

Bounds when k = 3

According to Bell & Stevens, Hayes also showed that $Q_3(n) \leq 2\lfloor (6n-2)/5 \rfloor$ . I’m not sure what the original proof was, but here is a way to see this:

Observation: $Q_3(n) \leq 2\lfloor (6n-2)/5 \rfloor$ .

Proof: Consider how the 8 “attack lines” from a queen can terminate at the edge of the board, as highlighted in red here:

If we consider all possible placements of queens on the board, then the set of all possible terminations looks like this:

From this figure, it’s easy to see that there are, in general, $4$ red segments in the corners of the board and $n + 2(n-1) = 3n - 2$ red segments on each side of the board, for a total of $4 + 4(3n - 2) = 12n - 4$ red segments.

Now consider a configuration where each queen is attacking three others and pick a queen (i.e., the rightmost queen in the example below). Three of the queen’s eight attack lines are obstructed by the three queens she is attacking, but the five remaining attack lines must extend to the edge of the board, staking a claim to five of the red segments.

This is true for any queen in the configuration, and the red segments cannot be “shared” by more than one queen, so there must be at most $\lfloor (12n - 4) / 5 \rfloor$ queens in total, i.e., $Q_3(n) \leq \lfloor (12n - 4) / 5 \rfloor$ .

Finally, note that $Q_3(n)$ must be even. To see this, we can count the number of “lines of attack” between queens on the board: with $n$ queens, each attacking $3$ other queens, we have $3n$ lines of attack, but this actually counts each line of attack twice – once in each direction – so $3n$ must be even, which means $n$ must be even.

So we have $Q_3(n) \leq 2\lfloor (6n - 2) / 5 \rfloor$ (which is always the largest even number $\leq \lfloor (12n - 4) / 5 \rfloor$ ). QED

Finding Solutions

Most of the results above focus on upper-bounds on $Q_k(n)$ , but how can we actually find examples like those in Figure 1 and Figure 2? One effective way is to use a “SAT solver” (as we also did here). “SAT” is a shorthand for the “Boolean Satisfiability Problem“, which is essentially the problem of finding solutions to formulas where the variables are binary (i.e., the only valid values are TRUE=1 and FALSE=0). SAT is a foundational topic in computer science and has been studied extensively. While there are a variety of reasons to believe that SAT is a hard problem to solve, there are also impressive “SAT solvers” that do quite well on practical instances, which is what interests us here. To read (much) more about this fascinating topic, check out Chapter 7 of Donald Knuth’s The Art of Computer Programming.

To transform our problem into a SAT problem, we start by defining $n^2$ Boolean variables $x_{i,j}$ , which will encode whether or not there is a queen in cell $(i, j)$ :

And if we’re looking for a solution with at least $m$ queens, then we’ll add the constraint:

\[ \sum_i \sum_j x_{i, j} \geq m \]

to our SAT formula. (There are a variety of techniques for converting such “cardinality constraints” into SAT formulas. See Knuth, for example.)

Next we need to add constraints that say: “Each queen is attacking exactly $k$ other queens”. We’ll build these up incrementally as follows.

Suppose there is a queen in cell $(4, 3)$ , and consider one of the $8$ possible direction of attack from that cell (shown in red here):

We can define a Boolean variable $z$ that is true if and only if there is a queen in that direction of attack from cell $(4, 3)$, for example, using the clauses:

\[ (\neg x_{3,4} \vee z) \wedge (\neg x_{2, 5} \vee z) \wedge (\neg x_{1, 6} \vee z) \wedge (\neg z \vee x_{3, 4} \vee x_{2, 5} \vee x_{1, 6}). \]

In words: the first three clauses ensure that if there is a queen in $x_{3, 4}, x_{2, 5} \text{ or } x_{1, 6}$ , then $z$ is true; the last clause ensures that if $z$ is true then there is a queen in one of those three cells.

Now, if we’ve created variables $z_1, \ldots, z_8$ like this for each of the $8$ directions of attack, we can add a constraint that says:

\[ \text{If } x_{4, 3} \text{ then } \sum_d z_d = k.\]

[In practice, this can be done by creating the CNF for $\sum_d z_d = k$ and then inserting $\neg x_{4, 3}$ into each clause.]

Proceeding in this way for each of the $n^2$ cells, we obtain a collection of SAT clauses that encode the problem of finding valid configurations of queens, and which we can feed to a SAT solving algorithm.

So, how well does this work in practice? Quite well, it turns out . . .

Some Results

In the case of $Q_1(n)$ , this approach handily found examples for all $n \leq 65$ that match the upper bound of $2\lfloor 2n/3 \rfloor$ . In some cases, this search could be sped-up by searching for symmetrical solutions. For example, in all cases except $n = 9$ and $n = 11$ , I was able to find solutions that had $180^\circ$ symmetry, like:

And in some cases, there were optimal solutions with $90^\circ$ symmetry (i.e., all $90^\circ$ rotations are the same), like this placement of $24$ queens on an $18 \times 18$ board:

For $Q_3(n)$ , this approach was also able to extend OEIS sequence A051756 up to $n = 17$ , all of which match the upper bound of $2\lfloor 2n/3 \rfloor$ . This included some particularly symmetrical solutions, like the following configuration of $36$ queens on a $16 \times 16$ board:

However, once we get to $n \geq 18$ , the SAT solver starts to really struggle to find solutions . It’s hard to say whether this is because there is no solution that meets the upper bound, or whether the SAT solver simply gets lost in the exponentially large search space. Despite this apparent difficulty, it effortlessly finds solutions that are just below the bound, such as this configuration of 40 queens on an $18 \times 18$ board:

Is this optimal, or is there a configuration with $42 = 2\lfloor (6\cdot 18 - 2)/5 \rfloor$ queens?

Update [11-Feb-2024]: There is indeed a configuration of $42$ queens on an $18 \times 18$ board, showing that $Q_3(18) = 42$ (and not 40)!

An 18×18 chessboard with 42 queens where each queen is attacking exactly 3 others, showing that $Q_3(18) = 42$ .

The key to getting the SAT solver to find such a solution was to provide some “hint” clauses constructed using the following logic.

In the proof of the upper bound on $Q_3(n)$ above, we established that there are $12n-4$ “terminations” and that each queen must cover exactly 5 of them. That means that when $n=18$ , there are $12 \cdot 18 - 4 = 212$ terminations and a configuration with $42$ queens would cover $42 \cdot 5 = 210$ of them, leaving exactly two terminations unused. It’s not hard to see that these two unused terminations must be “pointing toward each other” and this means that the line joining these terminations has no queens in it. In particular, there must be some row/column/diagonal with no queens in it, and all other rows/columns/diagonals must contain at least one queen. This statement can easily be expressed as a SAT formula (e.g., by defining a new variable for each row/column/diagonal and defining that variable as “there is no queen along this line”, and then adding clauses saying that exactly one of these variables is true).

Remarkably, adding these “hints” to the formula passed to the SAT solver, allows it to find a solution is seconds (rather than spinning its wheels for days, as it did before being given these hints)!

And this trick doesn’t just help for $n = 18$ . Essentially the same idea has helped find optimal configurations for $n$ up to at least 117. In general, there may be 0, 2, 4, 6, or 8 unused terminations, in which case there are (respectively) exactly 0, 1, 2, 3, or 4 rows/columns/diagonals with no queens in them, but any of these conditions is easily expressed as SAT clauses.

So why are these hints so helpful? Well, SAT solving is mysterious enough that it’s hard to say exactly “why” some formulas are easier than others, but it’s often the case that SAT solvers struggle with the kind of Pigeonhole Principle reasoning that we used in developing the “hints”. (Indeed, Knuth shows how some SAT algorithms require exponential time to prove that $n + 1$ pigeons can’t fit in $n$ pigeonholes.) By using our brains to do some of the pigeonhole thinking, and then feeding the insights to the SAT solver, it can presumably search much more intelligently.

Now that we’ve been able to calculate $Q_3(n)$ for many more values, it’s reasonable to make the following conjecture:

Conjecture: $Q_3(n) = 2\lfloor (6n-2)/5 \rfloor$ for all $n \geq 1$ .

Other Generalizations

Above, we focused on the function $Q_k(n)$ in part because this was the generalization of the n-Queens Problem that previous authors looked at. Arguably, however, it would be just as natural to study the function $q_k(n)$ defined by:

\[ \begin{aligned} & \text{Maximum number of queens that can be}\\ q_k(n) \hspace{0.1in} = \hspace{0.2in} & \text{placed on an } n \times n \text{ chessboard so that each } \\ & \text{queen is attacking at most } k \text{ other queens}. \end{aligned}\]

This is also a natural generalization in the sense that $q_0(n) = Q_0(n)$ is the classic n-Queens Problem.

Since $q_k(n)$ is less restrictive than $Q_k(n)$ (by not requiring that every queen be attacking $k$ others), it follows that $q_k(n) \geq Q_k(n)$ .

And when it comes to upper bounds, we’ve already done most of the work. Indeed, the proof above that $Q_3(n) \leq 2 \lfloor (6n-2)/5 \rfloor$ , readily generalizes to a proof of the following:

Observation: $q_k(n) \leq \lfloor (12n-4) / (8-k) \rfloor.$

This is a bit looser than the known bounds on $Q_k(n)$ , but that’s at least in part because $q_k(n) > Q_k(n)$ in some cases. For example, this configuration of $13$ queens on a $6 \times 6$ board shows that $q_3(6) = 13$ , which is optimal:

A 6×6 chessboard with 13 queens where each queen is attacking at most 3 other queens.

in contrast to $Q_3(6) = 12$ .

Another nice feature of $q_k(n)$ is that it actually makes sense for values of $k$ greater than $4$ (unlike $Q_k(n)$ ). For example, $q_7(8) = 44$ :

An 8×8 chessboard with 44 queens, where each queen is attacking at most 7 others.

I.e., each queen is attacking at most $7$ other queens or, put another way, each queen has at least one unobstructed “line of sight” to the edge of the board. (We know that $44$ is the optimal value because a SAT solver was quickly able to show there were no solutions with at least $45$ queens.)

And it turns out that $q_5$ can be pinned down exactly…

Observation: $q_5(n) = 4n - 4$ for all $n \geq 2$ .

Proof: First, to see that $q_5(n) \geq 4n - 4$ , note that we can simply arrange $4n - 4$ queens around the edge of the board:

and each queen is attacking its two “neighbors” and at most one other queen on each of the other three sides of the board, i.e., at most $5$ other queens.

To see that $q_5(n) \leq 4n - 4$ , take some configuration of $m$ queens where each queen is attacking at most $5$ others, and consider the convex hull of these queens. If the vertices of the convex hull are $v_1, \ldots, v_h$ , then there must be a queen at each such vertex, $v_i$ , and the number of other queens she is attacking, $a_i$ , must satisfy:

\[ 45^\circ (a_i – 1) \leq \theta_i ,\]

where $\theta_i$ is the interior angle of the convex hull at $v_i$ .

Now, a polygon with $h$ vertices has interior angles that sum to $180^\circ \cdot (h - 2)$ , which means:

\[ \begin{aligned} 45^\circ \sum_i (a_i – 1) & \leq 180^\circ \cdot (h – 2) \\ \left(\sum_i a_i \right) – h & \leq 4(h – 2) \\ \sum_i a_i & \leq 5h – 8 \end{aligned} \]

Now, we count “terminations”, as we did in previous proofs. If a queen is attacking $a_i$ other queens, then she must cover $8 - a_i$ of the $12n - 4$ terminations on the boundary of the board. In particular, the $h$ queens at the vertices of the convex hull consume at least

\[ \sum_i (8 – a_i) = 8h – \sum_i a_i \geq 8h – (5h – 8) = 3h + 8 \]

terminations. And the remaining $m - h$ queens each consume at least $3$ terminations (since they are each attacking at most $5$ queens). Therefore, we have

\[ 3h + 8 + 3(m-h) \leq 12n – 4 \]

and solving for $m$ yields $m \leq 4n - 4$ . QED

And similar reasoning can also be used for $q_4(n)$ :

Observation: $q_4(n) = 3n - 2$ for all $n \geq 2$ .

Proof: The following arrangement shows that $q_4(n) \geq 3n - 2$ :

To see that $q_4(n) \leq 3n - 2$ , we will count “terminations”. Suppose we have a configuration where each queen is attacking at most $4$ others. There are $12n - 4$ terminations, and each queen must cover at least $4$ of them, implying that there can be at most $(12n - 4) / 4 = 3n - 1$ queens. However, to achieve this bound of $3n – 1$ queens, each queen must cover exactly $4$ terminations and every termination must be covered by some queen, and we’ll see this is not possible. Indeed, consider a corner of the board and the two terminations circled below:

For these terminations to be covered, there must be a queen in this corner square; however, if there’s a queen in this corner square, that queen covers $5$ terminations (not $4$ ). So it’s not possible for there to be $3n - 1$ queens, and therefore the maximum possible is $3n - 2$ . QED

Conclusions

In this post, we’ve made some progress in understanding $Q_k(n)$ and $q_k(n)$ , and along the way we’ve extended OEIS sequences A051754 and A051756. But in some ways we’ve only scratched the surface of this topic and there are many open questions. The survey by Bell & Stevens describes many other directions of inquiry into the n-Queens Problem and related questions. And perhaps some readers of this blog will be able to prove the conjectures described here, or find even larger examples of optimal configurations!

Aleph Null

Attack of the Queens

History & Known Results

Bounds when k = 1

Bounds when k = 3

Finding Solutions

Some Results

Other Generalizations

Conclusions

Like this:

Leave a ReplyCancel reply

Attack of the Queens

History & Known Results

Bounds when k = 1

Bounds when k = 3

Finding Solutions

Some Results

Other Generalizations

Conclusions

Share this:

Like this:

Leave a ReplyCancel reply

Discover more from Aleph Null