Three Dimensional Queens Problems.L.Allison, C.N.Yee, & M.McGaughey,


Abstract: The twodimensional Nqueens problem is generalised to three dimensions and to N^{2}queens. There are nontoroidal and toroidal variants. A computer search has been carried out for (nontoroidal) solutions up to N=14. We conjecture that toroidal solutions exist iff the smallest factor of N is greater than 7. keywords: Nqueens problem, Latin square, pandiagonal Latin square. Introduction.The Nqueens 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 twodimensional Nqueens problem (2DNQP) in this paper. One variation is to make the board toroidal, so that moves wraparound. This is usually called the Nsuperqueens problem but for uniformity it is called the twodimensional toroidal Nqueens 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 NESW and NWSE 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 nonlinear solution for N=13 [1]. We introduce threedimensional variants of both of the above problems. The threedimensional 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 threedimensional queen can move in one of twenty six directions from a position <i,j,k> where N1>=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 threedimensional toroidal N^{2}queens problem (3DTN^{2}QP) the moves wraparound 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 knightqueen can move as a queen or as a knight. A kqueen can move as a queen or in multiples of a knights move; it has extra halfdiagonal moves. There are square and toroidal versions of both variants. Interestingly there are twodimensional toroidal kqueens solutions iff the smallest factor of N is greater than 7. The 3D 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 KnutVik design [2]. A Latin square is in general a solution to the threedimensional 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 twodimensional board, the N positions where any given m in {0..N1} 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 threedimensional 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..N1}. 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 threedimensions threatens along 2×13 lines of action. Given a linear solution to 3DTN^{2}QP generated by <a,b> step ab . . . 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 a1 b b+1 b1 a+b a+b+1 a+b1 ab ab+1 ab1 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 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 threedimensional 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 nonlinear 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 nonlinear 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..N1}. 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.


↑ © L. Allison, www.allisons.org/ll/ (or as otherwise indicated). Created with "vi (Linux)", charset=iso88591, fetched Tuesday, 28May2024 05:20:29 UTC. Free: Linux, Ubuntu operatingsys, OpenOffice officesuite, The GIMP ~photoshop, Firefox webbrowser, FlashBlock flash on/off. 