8 x 8 Queens

The famous Eight Queens problem has always fascinated me, perhaps because I’m so bad at it. The problem is to place eight queens on the chessboard in such a way that none of them attack one another (diagram shamelessly copied from Wikipedia).

I actually think that the reason it’s so fascinating to me is because I can’t see any pattern for the placement of the queens. I mean, a lot of the queens are a knight’s move apart, which only makes sense, since it’s the closest way to pack them without them attacking one another. But obviously this also gets broken quite a bit, and there turns out to be no simple heuristic as to where to start over once you’ve run your string of knight-related queens to the edge of the board (as happens on the left-hand side of the diagram).

This would also be why I’m so bad at it – because I can’t see any overall pattern. So ideally, to “subdue” this problem, I’d want to find a way to see patterns in it – by which I mean human-recognizable ones, not paper algorithms that can generate a solution but can’t be perceived over the board.

Another thing I’ve wondered about off and on is how many eight-queen solutions can be placed on a single board, where one is not allowed to put more than one queen on a square. In other words, can I put one set of eight yellow queens on the board such that none of them attack one another, then put a set of blue queens on vacant squares such that none of them attack one another, and so on for eight sets of eight queens?

Packing: the Rotational Approach
Now, these patterns are much too random-looking for me to just try mixing and matching them. One needs a heuristic. The first one involved packing a whole 8-queen pattern into one quarter of the board via rotation.

For instance, if I give the board three quarter-turns, and on each turn I “trap” whatever queen is in the lower-right, then I’ve packed all eight queens into one quarter of the board. If I can do this without any of them landing on top of one another, I’ll have proved that the initial position can be rotated four times to give us four solutions that fit on the same board. The diagram below shows how our initial position fails this test:

Here I’ve colored the home square of each queen, and colored the square that it packs to (in the lower right) the same color. Six of the queens rotate without interference, but the two on the magenta squares map onto one another, ruining the situation.

Well, let’s not try to break down an existing pattern – let’s try to generate one of our own. And let’s not bother with the four rotations, let’s immediately test for eight.

Generating our own solutions
This quarter of the board can be split in half down the long diagonal. If I can take each eighth of the board and spin it out into a valid eight-queens pattern, then the way I’ve generated it will prove that (a) it can be spun three times to give us four non-interfering eight-queens patterns, and (b) it can then be flipped across the long diagonal to give us four more – our ideal solution of eight non-interfering patterns.

It’s not quite as simple as that, because the long diagonal squares can’t each be divided in half. But one can split them two and two: for instance in the diagram above, one can take the set of the six yellow squares plus the two deep blue ones on the long diagonal, and then take the set of the six light blue squares plus the two black ones on the long diagonal. If both sets can be spun out into a valid eight-queens pattern, it will show that it is possible to fit eight sets of eight queens on a chess board.

It is fairly easy to show that this is impossible. Let’s start with the central dark blue square and work our way down the column of yellow squares beneath it:

Already, ominously, there is only one rotational slot possible for the second square (possible rotations shown in green). And there is only one for the third square (shown in magenta). By the time we get to the fourth square, there is no space available for it that doesn’t attack an already placed queen.

The reason for this is easy to see: we’re starting out with four squares on the same column, and there are only four rotations available. Therefore, we have to distribute our rotations with optimum efficiency, one queen each on the two central columns and two each on the two central rows. But queen number one is already on both a central column and a central row, taking up two slots. Thus, we can only add two more queens before running out of slots. The exact same problem applies with the corner square.

I believe that there are similar issues with light-blue-centered eighth of the board, but those would be more complicated to demonstrate. In the meantime, it’s clear – there can be no fully 8x8 queen solution generated in this way.

Is this a packing problem or a tiling problem?
Well, this got me thinking about approaching the problem in a related way: these rotational rings of queens don’t attack one another; so if I can find a pair of rings that cover the whole board without attacking one another (a) it’ll be pretty cool and (b) it might open the way to seeing other patterns.

Well, that doesn’t work. In fact, if we make a ring of queens that are on rotations of the square e3:

We find that just two more queens (in the lower left and right corners) completely cover the board. Now we’re starting to get more human-grokkable patterns, but we’re also straying a bit from the task. So I started to wonder: is this a packing problem or a tiling problem?

It’s sort of a mixture of each: if it’s a packing problem, then it’s to find the most efficient packing given a constraint (queens can’t attack each other) that makes the packing very inefficient; or, if it’s a tiling problem then it’s to find the least efficient tiling given a constraint that tends to make the tilings maximally efficient. This is an issue especially with our 8 x 8 queens task, since it's actually a packing of a packing (or a packing of a tiling?).

Okay, so let’s take a look at whether this ring of queens idea can give us patterns that need less than six queens to control (or occupy) the whole board. One does not have far to look for a generalized solution!

For each non-mutually-attacking rotational ring of queens outside the central sixteen squares, the four queens in the ring leave exactly four squares uncovered. These squares are symmetrically distributed on the long diagonals, so that one more queen on any of these four squares covers them all and completely controls the board.

In other words, now that we’ve shown that e3 needs six queens to cover the whole board, the five remaining yellow squares from our original eighth-board formation all have five-queen solutions to the problem of covering the whole board. Here are those formations:

e2 (I’ve just colored the appropriate squares rather than drawing actual queens)


f2


e1


f1


g1


A few points here:

1) I think this exhausts the solutions possible with five queens. I don’t have a proof, but these five patterns strongly exploit both the rotational symmetry of the board and that of the queen herself. As soon as I mess up the symmetry, the solutions start requiring more queens.

2) I will hold out the possibility that there may be a solution with four queens, randomly and brilliantly placed (sort of like the famous problem of how to connect nine dots with only four straight lines). But I think the probability of this is low.

3) Among these five solutions, each uses a different long diagonal square except that two use the corner. However, you can see that I have cunningly notated one corner in the lower left and one in the upper left (all other long diagonal squares are in their lower left rotation). This means that (a) we can place each of these five solutions on the chessboard at the same time without any queens landing on top of one another, and (b) we can then flip this composite solution horizontally to give us a total of ten solutions packed onto the same chessboard.

I like this.

Update: after writing all this, I did some online research and found out that there already exists a proof that five queens is the minimum number to completely cover an 8x8 chessboard, and that moreover there are 638 “basic” solutions that can be rotated and reflected to produce a total of 4860 distinct positions satisfying the condition. But intriguingly, the position given as an example follows the same form as my five solutions: a ring of four queens plus one “cleaning up” on the long diagonal. I wonder how many of the solutions follow this form.

Back to the original problem
Can this shed any light on our original problem of the eight queens, and how many of them can be packed onto a chessboard? It does. Let’s take a look at Wikipedia’s solution #1 again:

Although the presence of queens at d8 and h5 mean that this solution can’t be rotated a quarter-turn in either direction, it can be rotated 180 degrees. That gives us the following pair of solutions, notated here with red squares for the original queens, and blue squares for the rotation:

Now I call that an amazingly regular pattern – one that is very human-understandable! First of all, this is a pair of solutions packed onto the same board. But one can also easily see by looking at the pattern that it can be flipped either horizontally or vertically without any of the queens landing on top of one another. But then it can’t be flipped again, because either of these flips gives us the same composite pattern of four solutions packed onto the same board. (This is actually a result of the operations we’ve done, since flipping horizontally followed by flipping vertically is the same as rotating 180 degrees)

Looking at the existing “basic” eight queens solutions (there are only twelve), there aren’t any whose composite patterns of four magically compliment one another, giving us the ideal eight solutions. However, there is at least one pair of eight-queen patterns where the solution and one reflection can fit into the space left by the full composite of another.

Each of the twelve basic solutions must also be a distinct eight-queen pattern in either of its reflections, since for a reflection to have a queen land on top of another means that those queens must have started out on the same row or column – an impossibility giving the starting restrictions. Each of the twelve basic solutions also possesses exactly one non-interfering rotational version. All twelve patterns contain at least one pair of queens that interfere with one another rotationally, but those that contain two pairs interfere with each other at the same number of rotations.

So each basic eight-queen pattern can be packed onto the board with exactly three other versions of itself. And once this is accomplished, there is at least one pair of basic patterns where two permutations of the second pattern can be packed onto the board with the full four permutations of the first.

Let’s take a look. Here is Wikipedia’s pattern #2:


In passing: I like the way this pattern contains two permutations of my e3 tiling covering the chessboard with six queens:

Okay, here is Wikipedia’s #2 pattern rotated 180 degrees and then flipped horizontally (or vertically):

So far, so good.
All right, here is Wikipedia’s pattern #12:

You can see that it fits in the blank spaces left in the diagram just above it. Let’s flip this one horizontally:


This one fits, too, so let’s put them all together:

This gives us six eight-queen patterns packed onto a single chessboard.


Okay, summing up:

1) I think that this is a maximum packing for eight queens. Just looking at the twelve basic solutions, they all interfere with themselves or one another if you try to do more than six on a board. This is still a very concrete result, though, achieved by spot-checking the twelve basic solutions for rotational interference. I have no idea how to give the result (generalized or specific) in theoretical terms – for starters because I have no idea if there exists any way to represent the basic solutions themselves in theoretical terms.

2) I find it interesting that the five-queen solution can be packed onto a chessboard ten times, and the eight-queen solution six times – as close to being inverses of one another as the number of queens being used allows. One occupies 50 total squares on the chessboard and the other 48. I wonder how this number will behave for other numbers of queens on other sizes of chessboard. I imagine that as the board gets larger, it will become possible to fill a larger and larger proportion of the available squares with queens – by an analogy with knot theory, where as you increase the number of dimensions, it becomes easier and easier to slip out of a knot, and also because as the board increases in size the queen becomes proportionally less powerful.