Skip to: 
LyndenleaSearching for 3D Solutions
The aim is simple – to fit n² non-attacking 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 attack the Queens on any other layer.
So how exactly can a Queen on one layer attack a Queen on another layer? We already know from our two-dimensional puzzle that Queens on the same layer can attack 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, she 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
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
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 attack each other. We therefore need to find a new board for Layer 2.
Step 3: Changing the board in Layer 2
After trying almost 900 further boards we finally
find one that fits with no Queens able to attack 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
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
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.