# Beyond The 2nd Dimension

## 3D Solutions So Far

The first table on this page lists the number of three-dimensional solutions to the n² Queens in an n³ "chess-cube" puzzle that we have found in each size of cube using our algorithm. As we have been feeding that algorithm the full set of two-dimensional solutions (or "boards") for each cube our progress is increasingly hampered by available computer memory and processing power. However, although we have only found (complete sets of) solutions in two cubes so far, I've already started to find patterns in the results:

Number of 3D solutions found in each cube from size 7 to 16
Cube SizeSolutionsDate First Verified
707th February 2009
807th February 2009
907th February 2009
1007th February 2009
112647th February 2009
1207th February 2009
136247th February 2009
1408th February 2009
15012th December 2010
16None so far...

One obvious feature of these results is the lack of solutions for the 12³ cube and 14³ cube, even though the 11³ cube and 13³ cube both produced solutions. As they (along with the 10³ cube and 8³ cube) are even-numbered cubes, their sets of 2D solutions lack the 1, 3, 5, 7... boards that form the basis of the 11³ cube and 13³ cube solutions, as I found whilst analysing our earliest generated solutions in November 2008. I suspect that this isn't a coincidence and look forward to seeing the results of the 16³ cube that we're currently processing.

Another cube with no solutions is the 15³ cube, which is of course an odd-numbered cube. However, my analysis in November 2008 revealed that it too lacks the 1, 3, 5, 7... boards as this arrangement would result in two Queens trying to share the same diagonal line. The same is true of any chessboard size that's divisible by three, which may also explain the lack of solutions for the 9³ cube as it would otherwise probably be large enough to produce solutions.

### Taking a shortcut

By far the most interesting pattern I've seen in these results has provided us with a 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 by 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 chessboard diagrams:

 Q Q Q Q Q Q Q Q Q Q Q
 Q Q Q Q Q Q Q Q Q Q Q
 Q Q Q Q Q Q Q Q Q Q Q
 Q Q Q Q Q Q Q Q Q Q Q

In the first diagram 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 bottom to top. Similarly, in the second diagram each Queen is three columns away from its neighbours; in the third diagram, four columns; and in the fourth diagram, five columns. The most prominent parallel lines in the fourth diagram are those running from bottom-right to top-left – this is simply because this fourth pattern of Queens is a 90° rotation of the first pattern. It should therefore come as no surprise that the third pattern is a 90° rotation of the mirror of the second pattern.

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, and if we then feed them all into our algorithm for finding 3D solutions we will find we can generate all 264 possible 11³ cube solutions.

Turning to the 13³ cube solutions we find five patterns or gradients:

 Q Q Q Q Q Q Q Q Q Q Q Q Q
 Q Q Q Q Q Q Q Q Q Q Q Q Q
 Q Q Q Q Q Q Q Q Q Q Q Q Q
 Q Q Q Q Q Q Q Q Q Q Q Q Q
 Q Q Q Q Q Q Q Q Q Q Q Q Q

Like the patterns of Queens on the 11 by 11 boards, those on the 13 by 13 boards are also related. The first and fifth patterns are again 90° rotations of each other, as are the second and third patterns. That leaves the fourth pattern all by itself, but here's the clever part: the fourth pattern 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 by 11 the subset of 88 boards represents 3.28% of the full set of 2,680 possible 2D solutions, and that for 13 by 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 is just 25 by 25, and its full set of 2D solutions totals 2,207,893,435,808,352 – that's 2.2 quadrillion.

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, for any other non-prime cubes only some gradient patterns are valid, 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 continues 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.

The following table lists the numbers of solutions generated so far by our adapted "subset-based" program. 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. Also, while it found no solutions in the 25³ cube (the only one we've searched so far that is neither prime nor divisible by three), without further results I'm reserving judgement on whether this program might find solutions only in prime numbered cubes. And finally, note that we're still counting the solutions in the 35³ cube and 37³ cube. But so you can keep an eye on our progress, the number of solutions we find will be automatically updated daily.

Number of 3D solutions found by our subset-based program in each odd-numbered cube from size 17 to 39
Cube SizeSolutionsDate First Verified
172,04024th October 2010
193,19224th October 2010
21019th November 2008
236,62424th October 2010
25025th October 2010
27019th November 2008
2935,4962nd November 2010
3119,34420th January 2011
33019th November 2008
35At least 0
37At least 1,319
39019th November 2008

### So why are there no solutions for the 7³ cube? And what about the smaller cubes?

Technically, of course, the sole solution for the 1³ cube is a single Queen. But that aside, the 7³ cube and its smaller cousins are simply too small to bear any solutions, just like the 2 by 2 and 3 by 3 chessboards in the original (two-dimensional) puzzle. Specifically, there isn't enough variety within their respective sets of 2D boards to allow a 3D cube solution to be built.