n-queens in 3D
It's possible to place n queens on an n * n chess board so that no queen is attacking any other queen, provided n > 3. A queen is able to move any number of squares in any horizontal, vertical, or diagonal direction. Another way to put it is that the queen can move in any of 8 = 3^2 - 1 directions, in the direction of any cell in a 3 * 3 grid centered on the queen.
What if we extend chess to three dimensions? Now we have an n * n * n cube. Now a queen is able to move in 26 = 3^3 - 1 directions, in the direction of any cell in a 3 * 3 * 3 cube centered on the queen.
Klarner [1] proved that it is possible to placen^2 queens in an n * n * n cube so that no queen is attacking any other, provided gcd(n, 210) = 1, i.e. provided the largest prime factor ofn is larger than 7. The condition gcd(n, 210) = 1 is sufficient, and it is conjectured to be necessary as well [2].
Klarner constructed a solution as follows: Place the queens on
(i,j, (3i +5j) mod n)
fori andj running from 1 ton.
One way to visualize the queens in 3D is to draw a 2D grid where each cell contains the vertical coordinate of the corresponding queen. This grid will be a Latin square, and so the 3D queen placement problem is also known as the Latin queen problem.
Here's a visualization of Klarner's example.
Note that if you only pay attention to a particular number, you have a solution to the 11 queens problem in a square. That's because every slice of a 3D solution is a solution to the 2D problem.
I played around with plotting the points in three dimensions. Here's one view.
A slight rotation of the cube gives a substantially different perspective. This would be better as an animation, available here.
Mathematica code
Here's the code that made the images above.
Flat grid:
Grid[ Table[ Mod[3 i + 5 j, 11], {i, 0, 10}, {j, 0, 10} ], Frame -> All ]Static 3D view:
ListPointPlot3D[ Table[ {i, j, Mod[3 i + 5 j, 11]}, {i, 0, 10}, {j, 0, 10} ], BoxRatios -> {1, 1, 1}, PlotStyle -> {PointSize[0.02]} ]Animation:
Animate[ ListPointPlot3D[ Table[ {i, j, Mod[3 i + 5 j, 11]}, {i, 0, 10}, {j, 0, 10} ], BoxRatios -> {1, 1, 1}, PlotStyle -> {PointSize[0.02]}, ViewPoint -> {2 Cos[t], 2 Sin[t], 1} ], {t, 0, Pi, 0.05}, AnimationRunning -> True, AnimationRate -> 4 ] Export["klerner_animation.gif", %]Related posts[1] D.A. Klarner, Queen squares, J. Recreational Math. 12 (3) (1979/1980) 177-178.
[2] Jordan Bell and Brett Stevens. A survey of known results and research areas for n-queens. Discrete Mathematics 309 (2009) 1-31
The post n-queens in 3D first appeared on John D. Cook.