# 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.

Cube size | Total candidate 2D boards | "Subset" 2D boards | Number of 3D subset solutions |
Date that we first completed the search |
---|---|---|---|---|

11³ | 2,680 | 88 | 264 | 24th October 2010 |

13³ | 73,712 | 130 | 624 | 24th October 2010 |

15³ | 2,279,184 | 0 | 0 | 19th November 2008 |

17³ | 95,815,104 | 238 | 2,040 | 24th October 2010 |

19³ | 4,968,057,848 | 304 | 3,192 | 24th October 2010 |

21³ | 314,666,222,712 | 0 | 0 | 19th November 2008 |

23³ | 24,233,937,684,440 | 460 | 6,624 | 24th October 2010 |

25³ | 2,207,893,435,808,352 | 250 | 0 | 25th October 2010 |

27³ | 234,907,967,154,122,528 | 0 | 0 | 19th November 2008 |

29³ | Not yet counted | 754 | 35,496 | 2nd November 2010 |

31³ | Not yet counted | 868 | 19,344 | 20th January 2011 |

33³ | Not yet counted | 0 | 0 | 19th November 2008 |

35³ | Not yet counted | 280 | Not yet fully searched | |

37³ | Not yet counted | 1,258 | Not yet fully searched | |

39³ | Not yet counted | 0 | 0 | 19th November 2008 |

41³ | Not yet counted | 1,558 | Not yet searched | |

43³ | Not yet counted | 1,720 | Not yet searched | |

45³ | Not yet counted | 0 | 0 | 19th November 2008 |

47³ | Not yet counted | 2,068 | Not yet searched | |

49³ | Not yet counted | 1,372 | Not yet searched | |

51³ | Not yet counted | 0 | 0 | 19th November 2008 |

53³ | Not yet counted | 2,650 | Not yet searched | |

55³ | Not yet counted | 880 | Not yet searched | |

57³ | Not yet counted | 0 | 0 | 19th November 2008 |

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.