## 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 N^{2}-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 N^{2}-queens problem (3DN^{2}QP) is
to place N^{2} (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 N^{2}-queens problem (3DTN^{2}QP)
the moves wrap-around modulo N.
Note that each
plane slice through a 3DN^{2}QP (3DTN^{2}QP) 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 3DN^{2}QP for N<11, N=12 or N=14.
All solutions
to 3DN^{2}QP for N=11 and 13 are solutions to 3DTN^{2}QP
and are linear.
We conjecture that
there are solutions to 3DTN^{2}QP
iff the smallest factor of
N is greater than 7.

A solution to
3DN^{2}QP places N^{2} 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 3DTN^{2}QP 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 N^{2}-Queens problem.

The
3DN^{2}QP requires placing N^{2} 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 S_{ij} contains a height, k,
then S is clearly a Latin square.
A solution to 3DTN^{2}QP is also a pandiagonal Latin square
or Knut-Vik design [2].
A Latin square is in general a solution to the
three-dimensional N^{2} rooks problem, not the queens problem.

Each row and column of a square
derived from a solution to 3DN^{2}QP (3DN^{2}QP)
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 3D11^{2}QP.

The example is the lexicographically first solution
to the 3D11^{2}QP.
It is also a *linear solution*
in that the rows and columns
are arithmetic progressions modulo N;
S_{ij}=x+ai+bj mod N for some a, b, x.

Representing a solution to the 3DN^{2}QP 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 3DN^{2}QP.
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 3DTN^{2}QP
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 3DN^{2}QP 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 3DN^{2}QP 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 3DTN^{2}QP iff there
are linear solutions.

## Linear Solutions to 3DTN^{2}QP.

A queen in three-dimensions threatens along 2×13 lines of action.
Given a linear solution to 3DTN^{2}QP 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 3DTN
^{2}QP 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.)

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 3DTL^{2}QP within a 3DTM^{2}QP solution to form
a solution in the LM^{3} cube.
These are the only known non-linear solution as yet.

## Summary.

There are no solutions to 3DN^{2}QP if N<11, N=12 or N=14.
For N=11 and N=13 all solutions to 3DN^{2}QP are also solutions
to 3DTN^{2}QP and they are all linear.
We conjecture that
there are solutions to 3DTN^{2}QP iff the smallest factor
of N is greater than 7.
No solution to 3DN^{2}QP that is not a solution to 3DTN^{2}QP is known.
The only known non-linear solutions to 3DN^{2}QP
and 3DTN^{2}QP 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 3DN^{2}QP 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 4DN^{3}QP 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.