# Beyond The 2nd Dimension

## Searching For 3D Solutions

The aim is simple - to fit **n²** Queens into a cube of
**n³** cells. So how best to go about it? The first step is to look at the
cube so we can better understand how these Queens might fit.

Essentially, the cube is comprised of **n layers**, each of which contains
**n² cells**. Therefore, it makes sense to divide the Queens equally between
these layers, fitting **n Queens** on each. But hang on - we've been here before!
The original two-dimensional puzzle gave us plenty of solutions for each individual layer, so to
create a three-dimensional solution we need only find **n 2D solutions** that will
stack on top of each other such that the Queens on one layer can't capture the Queens on any
other layer.

So how exactly can a Queen on one layer capture a Queen on another layer? We already know from
our two-dimensional puzzle that Queens on the same layer can capture each other if they're in
the same row, column or diagonal, and the same is basically true between layers, except there
are a few more directions to consider. For example, as well as East-West (rows) and North-South
(columns) on the same layer, there's now also directly Up and Down. With the diagonals, a Queen
can now move up or down between layers **in addition to** all of the directions
available on the same layer, such as **North and Up**, **West and
Down**, and even **South-East and Up**. So where a Queen had only eight
directions in which to move on a 2D chessboard, it now has **26**.

Due to the complexities of producing three-dimensional diagrams, each of the diagrams on this
page shows a **plan view** of the cube; in other words, the view as if you were
looking down on the cube from above. The Queens in each Layer are represented by that Layer's
number (counting from the bottom of the cube upwards) so, for example, all the Queens in Layer 1
(the bottom layer) are indicated by a number **1** in the appropriate square. The
higher the number, the higher up the cube the Queen sits. All will hopefully become clearer as
we work through the example.

### Step 1: Placing the First Board

1 | ||||||||||

1 | ||||||||||

1 | ||||||||||

1 | ||||||||||

1 | ||||||||||

1 | ||||||||||

1 | ||||||||||

1 | ||||||||||

1 | ||||||||||

1 | ||||||||||

1 |

We begin with an empty **11³** cube which comprises 1,331 cells into which we might place a Queen. However, as we're going to add Queens eleven
at a time by filling each Layer with an existing two-dimensional solution (or **board**), we really only have eleven Layers to fill.

The diagram shows our cube containing just the **first possible 2D solution** in its bottom Layer. By trying the boards in the same order that they
were discovered using our 2D algorithm - assuming we didn't stop after finding the first solution but let it run right
through to the end, therefore generating the full set of 2D solutions (or boards) - we are guaranteed to find the **first possible 3D solution** as
well.

In our hunt for 3D solutions we are not interested in counting the number of boards tried, so we can move straight on to finding another board to fit in Layer 2.

### Step 2: Filling Layer 2

1 | 2 | |||||||||

1 | 2 | |||||||||

1 | 2 | |||||||||

1 | 2 | |||||||||

1 | 2 | |||||||||

2 | 1 | |||||||||

1 | 2 | |||||||||

1 | 2 | |||||||||

1 | 2 | |||||||||

1 | 2 | |||||||||

1 | 2 |

For a board to fit in Layer 2, the most important consideration is that none of its Queens is directly above those already in Layer 1. Unfortunately, the first 96 boards in the set all have their first Queen in Row 1, Column 1 (the bottom-left square), so they are immediately eliminated from the search. However, we have a total of 2,680 possible boards so there are plenty still available.

The first board without a Queen in its bottom-left square seems like a promising candidate, so we must continue to compare its Queens with those already in Layer 1. Sadly, we find that its Queen on Row 4 is in Column 7, just like the Queen on Row 4 in Layer 1, so it is also no good. The next candidate board, No.98 in the set, doesn't have this clash of Queens, and is shown in the diagram.

Although these two boards have no Queens in the same Row and Column, they do have Queens in **diagonally adjacent** squares which means they can still
capture each other. We therefore need to find a new board for Layer 2.

### Step 3: Changing the Board in Layer 2

2 | 3 | 1 | ||||||||

2 | 3 | 1 | ||||||||

3 | 1 | 2 | ||||||||

3 | 1 | 2 | ||||||||

1 | 2 | 3 | ||||||||

2 | 3 | 1 | ||||||||

2 | 3 | 1 | ||||||||

3 | 1 | 2 | ||||||||

3 | 1 | 2 | ||||||||

1 | 2 | 3 | ||||||||

1 | 2 | 3 |

After trying almost 900 further boards we finally find one that fits with no Queens able to capture any other: No.976. We can now move up to Layer 3, for which we need to start searching the entire set of solutions again from the beginning. Why? Because although none of those 2D boards would fit on Layer 2, they might yet be perfect for Layer 3, or indeed any other Layer of the cube. As it happens, though, the first board to fit on Layer 3 with no clashing Queens is No.2,358 as shown on the diagram.

Interestingly, we are beginning to see a pattern emerging. If you look closely you will see that the Queens on each Layer form parallel lines running from bottom-left to top-right. Also, each column in the diagram contains the numbers 1, 2, 3 running from top to bottom. Is it possible that these patterns could persist throughout the entire 3D solution?

### Step 4: Filling Layers 4 to 6

2 | 5 | 3 | 6 | 1 | 4 | |||||

2 | 5 | 3 | 6 | 1 | 4 | |||||

3 | 6 | 1 | 4 | 2 | 5 | |||||

3 | 6 | 1 | 4 | 2 | 5 | |||||

1 | 4 | 2 | 5 | 3 | 6 | |||||

4 | 2 | 5 | 3 | 6 | 1 | |||||

2 | 5 | 3 | 6 | 1 | 4 | |||||

5 | 3 | 6 | 1 | 4 | 2 | |||||

3 | 6 | 1 | 4 | 2 | 5 | |||||

6 | 1 | 4 | 2 | 5 | 3 | |||||

1 | 4 | 2 | 5 | 3 | 6 |

Having now filled Layers 4 to 6, it would appear that those patterns are indeed continuing. The Queens in each Layer are still forming those diagonal lines, and the second column from the right in the diagram best shows the numbers from 1 to 6 running vertically. We can also see a new pattern emerging in the bottom-right to top-left diagonals with triplets of 1, 3, 5 and 2, 4, 6 - you might be able to guess how those triplets will continue. And finally, there are pairs of numbers running horizontally.

The board on Layer 4 is our old friend No.98 which we first saw trying to fit on Layer 2. It now fits perfectly on Layer 4, and illustrates the need to search the entire set of 2D solutions for each new Layer. The board on Layer 5 is No.1,371 and on Layer 6 is No.2,366.

### Step 5: Completing the First Solution

7 | 10 | 2 | 5 | 8 | 11 | 3 | 6 | 9 | 1 | 4 |

2 | 5 | 8 | 11 | 3 | 6 | 9 | 1 | 4 | 7 | 10 |

8 | 11 | 3 | 6 | 9 | 1 | 4 | 7 | 10 | 2 | 5 |

3 | 6 | 9 | 1 | 4 | 7 | 10 | 2 | 5 | 8 | 11 |

9 | 1 | 4 | 7 | 10 | 2 | 5 | 8 | 11 | 3 | 6 |

4 | 7 | 10 | 2 | 5 | 8 | 11 | 3 | 6 | 9 | 1 |

10 | 2 | 5 | 8 | 11 | 3 | 6 | 9 | 1 | 4 | 7 |

5 | 8 | 11 | 3 | 6 | 9 | 1 | 4 | 7 | 10 | 2 |

11 | 3 | 6 | 9 | 1 | 4 | 7 | 10 | 2 | 5 | 8 |

6 | 9 | 1 | 4 | 7 | 10 | 2 | 5 | 8 | 11 | 3 |

1 | 4 | 7 | 10 | 2 | 5 | 8 | 11 | 3 | 6 | 9 |

The last few Layers are the quickest and easiest to fill as we not only have fewer 2D boards to choose from, but fewer places for Queens to sit comfortably in the cube. You will see that the diagonal patterns we identified earlier have continued as expected, and the second column from the right in the diagram, in which we saw the numbers 1 to 6 incrementing earlier, now has the numbers 7 to 11 filling in the gaps to give us the sequence 1, 7, 2, 8, 3, 9, 4, 10, 5, 11, 6. This sequence is similarly repeated in every column of the diagram.

For reference, the boards we used to fill the five remaining Layers of the cube are No.326, No.1,781, No.2,593, No.579 and No.2,109. But why did we keep track of these numbers? If we allowed the algorithm to continue to find the full set of 3D solutions we would inevitably exhaust the set of 2D solutions on a particular Layer, so we'd need to know from which point to continue searching on the Layer below in case there was another board that fitted. And optionally, the board numbers can also be used for Describing 3D Solutions.