Taking a Shortcut

By far the most interesting pattern I've seen in the two sets of 3D solutions that we've found (in the 11³ cube and the 13³ cube respectively) has provided us with a handy shortcut to finding at least some of the solutions in any odd-numbered cube whose size is not divisible by three. This shortcut takes advantage of the fact that on all of the 2D boards that make up the 11³ cube and 13³ cube solutions, the Queens are evenly spaced in parallel lines across the board.

For example, amongst the 11×11 boards there are four variations of these parallel lines – or to put it another way, the lines have four different gradients dictated by the number of columns between two Queens in adjacent rows, as illustrated by these four chessboard diagrams.

In the first diagram (labelled A) each Queen is two columns away from its neighbours in the adjacent rows. The pattern continues when the line of Queens reaches an edge of the board by "wrapping around", both from right to left and from top to bottom. Similarly, in the second diagram (labelled B) each Queen is three columns away from its neighbours; in the third diagram (labelled C), four columns; and in the fourth diagram (labelled D), five columns. You might see that the most prominent parallel lines in diagram D are those running from bottom-right to top-left – this is because the pattern of Queens in diagram D is a 90° rotation of the pattern in diagram A. It may therefore come as no surprise that the pattern in diagram C is a 90° rotation of the mirror of the pattern in diagram B.

If we take each of these four diagrams and shift them up by one row, bringing the Queen that's forced off the top row down onto the bottom row, we can create eleven different 2D solutions or boards using each pattern. Mirroring each of these 44 boards gives us a total of 88 different boards (we don't need to rotate them as the four patterns are already 90° rotations of each other, and the 180° rotations are taken care of by the row-shifting process); and if we then feed these 88 boards into our algorithm for finding 3D solutions, we will find we can generate all 264 possible 11³ cube solutions.

Turning now to the 13³ cube solutions, here we find five patterns or gradients; and, like the patterns of Queens on the 11×11 boards, those on the 13×13 boards are also related. The first and fifth patterns (labelled E and J) are again 90° rotations of each other, as are the second and third patterns (labelled F and G). That leaves the fourth pattern (labelled H) all by itself, but here's the clever part: the pattern in diagram H is a 90° rotation of itself.

If we use the same row-shifting technique as before to create the thirteen different 2D solutions using each pattern, and then mirror them, this gives us 130 different boards which we can once again feed into our 3D solution-finding algorithm to generate all 624 possible 13³ cube solutions.

Being able to generate all the possible 3D solutions from just these "subsets" of 2D boards is in these two cases to be expected because we extracted the initial patterns from the full sets of 3D solutions in the first place. But when we consider that for 11×11 the subset of 88 boards represents 3.28% of the full set of 2,680 possible 2D solutions, and that for 13×13 the subset of 130 boards represents just 0.18% of the full set of 73,712 possible 2D solutions, it becomes very clear that if we start with just the subset we can potentially find all the possible 3D solutions far more quickly and easily than if we started with the full set of 2D boards. This is even more interesting when we consider that the largest odd-numbered chessboard for which all 2D solutions has even been counted (at the time of writing) is just 27×27, and its full set of 2D solutions totals 234,907,967,154,122,528 – that's almost 235 quadrillion.

A mathematical prediction

Following my detailed analysis of the 11³ cube and 13³ cube, in March 2009 I worked out a mathematical formula to predict the number of solutions that each odd-numbered cube's subset should produce. (I am indebted to my friend Clare Willis and her father John Willis for helping me to present my analysis in mathematical terminology.) In order to verify the results of that formula, in May 2009 I set about writing a PHP script to generate the required subsets of 2D solutions. This turned out to be as easy as trying as many different gradients of lines of Queens as possible – just like in the diagrams above – and then row-shifting and mirroring those patterns that result in valid 2D solutions to create the complete subset. Perhaps unsurprisingly, for any cube whose size is divisible by three I found that there are NO valid gradient patterns at all. But what did surprise me was that while all the possible gradient patterns are valid for prime numbered cubes, only some gradient patterns are valid for non-prime cubes, giving a reduced subset of boards. My mathematical formula was therefore only of use for prime numbered cubes.

In October 2010 Dad and I produced an adapted version of his own much faster program that would accept my subsets of 2D boards. Initially the prime numbered cubes' results matched my formula's earlier predictions; but then the 29³ cube bucked the trend by generating more than double the predicted number of solutions! It was finally time to lay my formula to rest, but our adapted program continued to generate 3D solutions, albeit perhaps only a subset of the total number possible as there may still be other 3D solutions that do not contain these parallel lines of Queens.

Subset-based solutions so far

The following table lists the number of three-dimensional solutions to the n² Queens in an n³ "chess-cube" problem that we have found in each size of cube using our adapted "subset-based" program. The enormous difference in magnitude between the full set of two-dimensional solutions (or "boards") for each cube – given in second column of the table, and taken from sequence A000170 in the On-Line Encyclopedia of Integer Sequences (OEIS) – and the subset of boards comprising only parallel lines of Queens – given in the third column – is clearly evident.

The complete lack of subset-based boards in cubes whose size is divisible by three is obvious. Also apparent is the reduced subset of boards for other non-prime cubes – see the third column for the 25³, 35³, 49³ and 55³ cubes, and compare the size of their subsets to those of adjacent cubes. While our subset-based program found no solutions in the 25³ cube (the only one we've fully searched so far that is neither prime nor divisible by three), without further results I reserve judgement on whether it might find solutions only in prime numbered cubes, or whether square numbered cubes (i.e. 25³ and 49³, because 25 = 5² and 49 = 7²) might behave differently than other non-prime cubes.

Finally, please remember that this program may not identify all the possible solutions for each cube size – although we know that it does for both the 11³ cube and 13³ cube – and that it is only designed for odd-numbered cubes.

Until the end of 2014 we had been continuing this research by searching for subset-based solutions in the 35³ cube and the 37³ cube. After more than four years we had found no solutions in the 35³ cube, and after more than three years 1,319 solutions in the 37³ cube, but it was clear that we were still only a very short way through both cubes and that completing either of them would take a very long time indeed. The search for solutions in these two cubes – and indeed in any larger cubes – is therefore on hiatus.

Return to Top