Three Dimensional Queens Problems.
L.Allison, C.N.Yee, & M.McGaughey, Department of Computer Science (Faculty of Info. Tech.), Monash University, Australia 3800.
Technical Report 89/130 [TR.ps],
created: 15 Nov 1988
Abstract: The two-dimensional N-queens problem is generalised to three dimensions and to N2-queens. There are non-toroidal and toroidal variants. A computer search has been carried out for (non-toroidal) solutions up to N=14. We conjecture that toroidal solutions exist iff the smallest factor of N is greater than 7.
keywords: N-queens problem, Latin square, pandiagonal Latin square.
Introduction.
The N-queens problem is well loved in computer science [1,5,6] and in combinatorial mathematics. To solve it is to place N queens on a square N×N chess board so that no two queens threaten each other. To distinguish the problem from other variants it is called the two-dimensional N-queens problem (2DNQP) in this paper.
One variation is to make the board toroidal, so that moves wrap-around. This is usually called the N-super-queens problem but for uniformity it is called the two-dimensional toroidal N-queens problem (2DTNQP) here. Any toroidal solution is also a solution on the square. The torus is more uniform than the square in a number of ways: all columns and rows are equally constrained and there are just N diagonals in both the NE-SW and NW-SE directions. For this reason there has been more success in proving results about 2DTNQP than about 2DNQP. It has been shown, by various means [3,4,7], that there are solutions to 2DTNQP iff the smallest factor of N is greater than 3. There are only linear solution for N<13 but {0, 3, 8, 11, 5, 1, 10, 4, 7, 12, 2, 9, 6} is a non-linear solution for N=13 [1].
We introduce three-dimensional variants of both of the above problems. The three-dimensional N2-queens problem (3DN2QP) is to place N2 (hyper?) queens in an N×N×N cube so that no two queens threaten each other. A three-dimensional queen can move in one of twenty six directions from a position <i,j,k> where N-1>=i,j,k>=0 to <i+nx, j+ny, k+nz> where {x,y,z} is a subset of {-1,0,1}, {x,y,z}!={0} and n>0. In the three-dimensional toroidal N2-queens problem (3DTN2QP) the moves wrap-around modulo N. Note that each plane slice through a 3DN2QP (3DTN2QP) solution is a solution to 2DNQP (2DTNQP). We relate these two problems to Latin squares and present the results of computer searches for solutions. There are no solutions to 3DN2QP for N<11, N=12 or N=14. All solutions to 3DN2QP for N=11 and 13 are solutions to 3DTN2QP and are linear. We conjecture that there are solutions to 3DTN2QP iff the smallest factor of N is greater than 7.
A solution to 3DN2QP places N2 points very uniformly in the cube in the sense that when looking along any row, column or diagonal just one queen is seen. If one imagines a 3DTN2QP solution replicated infinitely many times in three dimensions, it scatters points very uniformly in space at a density of 1/N.
Other variants on the 2DNQP have been studied [3]. A knight-queen can move as a queen or as a knight. A k-queen can move as a queen or in multiples of a knights move; it has extra half-diagonal moves. There are square and toroidal versions of both variants. Interestingly there are two-dimensional toroidal k-queens solutions iff the smallest factor of N is greater than 7.
The 3-D N2-Queens problem.
The 3DN2QP requires placing N2 queens in an N×N×N cube so that no two queens threaten each other. There can only be one queen in any row parallel to any axis, or in any diagonal. If a solution is projected onto one face, S, of the cube, so that Sij contains a height, k, then S is clearly a Latin square. A solution to 3DTN2QP is also a pandiagonal Latin square or Knut-Vik design [2]. A Latin square is in general a solution to the three-dimensional N2 rooks problem, not the queens problem.
Each row and column of a square derived from a solution to 3DN2QP (3DN2QP) is a solution to the 2DNQP (2DTNQP) represented as a vector. Also, considering the square to be a two-dimensional board, the N positions where any given m in {0..N-1} lies form a 2DNQP (2DTNQP) solution. With so many constraints it is surprising that there are any solutions at all but for suitable N there are quite a lot.
0 1 2 3 4 5 6 7 8 9 10
0: 0 2 4 6 8 10 1 3 5 7 9
1: 4 6 8 10 1 3 5 7 9 0 2
2: 8 10 1 3 5 7 9 0 2 4 6
3: 1 3 5 7 9 0 2 4 6 8 10
4: 5 7 9 0 2 4 6 8 10 1 3
5: 9 0 2 4 6 8 10 1 3 5 7
6: 2 4 6 8 10 1 3 5 7 9 0
7: 6 8 10 1 3 5 7 9 0 2 4
8: 10 1 3 5 7 9 0 2 4 6 8
9: 3 5 7 9 0 2 4 6 8 10 1
10: 7 9 0 2 4 6 8 10 1 3 5
The first solution to 3D112QP.
The example is the lexicographically first solution to the 3D112QP. It is also a linear solution in that the rows and columns are arithmetic progressions modulo N; Sij=x+ai+bj mod N for some a, b, x.
Representing a solution to the 3DN2QP as a square involves an arbitrary choice of a face of the N×N×N cube. Any square or face determines the solution and thus the other faces (fig 1).
.................................
..7 .
.2. .
. .3 .
. 4. S .
. .10 .
. 6. .
. .6 .
. 8. .
. .2 .
. 10. ^ step b .
. .9 . .
. 1. . .
. .5 .--->step a .
. S" 3. .
. .1 .
. 5. .
. .8 .
. ^step -b/a 7. .
. . .4 .
. . 9. .
. . .0 2 4 6 8 10 1 3 5 7 9.
. | .................................
. | 0.0 5 10 4 9 3 8 2 7 1 6.
. | . .
. v step 1/a 6.3 .
. . .
. 1.6 S' .
. . .
. 7.9 .
. . .
. 2.1 .
. . .
. 8.4 .
. . .---> step -a/b .
. 3.7 | .
. . | .
. 9.10 v step 1/b .
. . .
. 4.2 .
. . .
. 10.5 .
. . .
.5.8 .
..................................
Figure 1. Faces of the cube.
`steps' refer to linear solutions only
If we name the three visible faces S, S' and S", then either they are all linear Latin squares or none of them are. We call three squares related in this way perpendicular Latin squares (since the use of orthogonal has been preempted).
Computer Search.
A program was written to enumerate solutions to 3DN2QP. There are no solutions for N<11, N=12 or N=14. There are 264=11×24 solutions for N=11 and 624=13×48 solutions for N=13. All of them are also solutions to 3DTN2QP and they are all linear. Note that if the the queens are not allowed to move along diagonals of the cube, which are the genuinely three-dimensional diagonals, there are solutions for N=7.
The search tree for 2DNQP has maximum breadth at a depth of approximately N/2. The 3DN2QP search tree stacks 2DNQP search trees in layers. The second and successive layers are more and more tightly constrained and, for N about 11, the maximum width of the 3DN2QP tree is at the third or fourth layer. Beyond about the fifth layer the branching factor is one and any solution is essentially determined.
Generalised Latin squares on the Torus.
Shapiro [7] generalised the notion of a Latin square to define Latin squares over generators. A generator is a pair <x,y> that defines a line {<r,s> <x+r,y+s> <2x+r,2y+s> ...} of N points for any starting point <r,s>; addition is modulo N. A generator <x,y> partitions the torus into N disjoint lines. S is a Latin square on the torus over a collection of generators if the values of S on each line generated by a generator are a permutation of {0..N-1}. In these terms, traditional Latin squares are Latin squares over {<0,1> <1,0>} and pandiagonal Latin squares are Latin squares over {<0,1> <1,0> <1,1> <1,-1>}.
Shapiro proved the remarkable result that there is a Latin square over a set of generators iff there is a linear Latin square over the generators. We conjecture that a similar result applies if `Latin square' is replaced everywhere with `three perpendicular Latin squares'. Thus there would be solutions to 3DTN2QP iff there are linear solutions.
Linear Solutions to 3DTN2QP.
A queen in three-dimensions threatens along 2×13 lines of action. Given a linear solution to 3DTN2QP generated by <a,b>
step a-b
.
.
.
0 a 2a 3a ...
b b+a 2a+b 3a+b ...
2b 2b+a 2b+2a 3a+2b ...
... .
.
.
step a+b
the action lines are defined by steps of
a a+1 a-1 b b+1 b-1 a+b a+b+1 a+b-1 a-b a-b+1 a-b-1
The steps involving +1 and -1 are for diagonals running out of the page. These account for twelve out of the thirteen lines. The thirteenth is dealt with by there being just one number for each position of the square.
- It is not hard to see that
- (i) There is a linear solution to 3DTN2QP generated by <a,b> iff the twelve steps above are all coprime to N.
- (ii) If the smallest factor of N is greater than 7 there are solutions, for example a=2, b=4.
- (iii) If the smallest factor of N is 2, 3, 5 or 7 there are no linear solutions and thus,
- if the conjecture is valid, no solutions at all. (For example, if the smallest factor of N is 7, then a and b must be 2, 3, 4, or 5 mod 7. If a=2 mod 7 say then b cannot be 3 or 5 mod 7, so b=4 mod 7 but then a+b+1=0 mod 7.)
- (i) There is a linear solution to 3DTN2QP generated by <a,b> iff the twelve steps above are all coprime to N.
It is straightforward to write a computer program to enumerate the pairs <a,b> that can define a linear solution.
Decomposition Solutions.
Abramson and Yung[1] described the decomposition solutions to 2DTNQP (and hence to 2DNQP). The idea is that a solution on the L×L board may be treated like a queen; a copy is placed at each queen's position in a solution on the M×M board. This gives a solution on the LM×LM board.
A similar technique can be used for the three-dimensional toroidal problem, placing a solution to 3DTL2QP within a 3DTM2QP solution to form a solution in the LM3 cube. These are the only known non-linear solution as yet.
Summary.
There are no solutions to 3DN2QP if N<11, N=12 or N=14. For N=11 and N=13 all solutions to 3DN2QP are also solutions to 3DTN2QP and they are all linear. We conjecture that there are solutions to 3DTN2QP iff the smallest factor of N is greater than 7. No solution to 3DN2QP that is not a solution to 3DTN2QP is known. The only known non-linear solutions to 3DN2QP and 3DTN2QP are the decomposition solutions.
The queens problems can obviously be generalised to four or more dimensions. This suggests the idea of a Latin (hyper-)cube. A solution to 2DNQP is a permutation. A permutation is a vector of N integers, all different, chosen from {0..N-1}. A solution to 3DN2QP is a Latin square. A Latin square is a vector of N permutations such that each vertical and horizontal slice is a permutation. A solution to 4DN3QP would be a Latin cube - a vector of Latin squares such that each plane slice through the cube is a Latin square.
References.
- [1] B. Abramson and M. M. Yung.
Construction through decomposition: a divide-and-conquer algorithm
for the N-queens problem.
Fall Joint Computer Conference 620-628 Nov 1986.
- [2] A. O. L. Atkin, L. Hay and R. G. Larson. Enumeration and construction of pandiagonal Latin squares of prime order. Computers and Mathematics with Applications 9(2) 267-292 1983.
- [3] A. K. Chandra. Independent permutations, as related to a problem of Moser and a theorem of Polya. Journal of Combinatorial Theory (A) 16 111-120 1974.
- [4] F. K. Hwang and Ko-Wei Lih. Latin squares and superqueens. Journal of Combinatorial Theory (A) 34 110-14 1983.
- [5] J. S. Rohl. Generating permutations by choosing. Computer Journal 21(4) 302-305 1978 also correspondence 22(2) pp191 1979
- [6] J. S. Rohl. A faster lexicographical N queens algorithm. Information Processing Letters 17 231-233 1983
- [7] H. D. Shapiro. Generalized Latin squares on the torus. Discrete Mathematics 24 63-77 1978.
- [2] A. O. L. Atkin, L. Hay and R. G. Larson. Enumeration and construction of pandiagonal Latin squares of prime order. Computers and Mathematics with Applications 9(2) 267-292 1983.