graeco latin leaper tours on the torus |
here we enumerate graeco-latin tours of a torus-leaper on the n*n board.
A torus-(r,s)-leaper's tour is an n*n matrix a(0..n-1,0..n-1) containing
the numbers 0 to n*n-1 exactly once and consecutive numbers are a
(r,s)-leaper's move apart in the matrix, but the edges of the board wrap around to the other side :
so a(u,v)=1+a(x,y) implies {abs(u-x),abs(v-y)} is element of {{r,s},{n-r,s},{n-r,n-s},{r,n-s}}
Torus-leapers are somehow nicer and more mathematical than usual chess-pieces,
since they can move to 8 squares (or 4, if r=s) , no matter where they are.
We have n*n-fold translational symmetry and each square can be made
the upper left "corner" by isomorphism.
However it seems that they are not very common and I'd like to
see a reference, if you know where they have been examined.
A leaper's tour a(,) is called magic, iff all rows sum to n*(n*n-1)/2 and
all columns sum also to n*(n*n-1)/2 , the magic constant of the tour.
A (r,s)-leaper is a piece, which moves r squares into one of the 4 directions
and then with the same move s squares into an ortogonal direction.
So, e.g. a knight is a (1,2)-leaper
Each such matrix a(,) with entries from {0,..,n*n-1} gives two other new
n*n matrices a1(,) and a2(,) which contain the 1st and 2nd digit
respectively, when the entries of a(,) are writen in base n ,
a(i,j)=n*a1(i,j)+a2(i,j) .
A leaper tour a(,) is called "graeco latin tour" , iff
a1(,) and a2(,) are both latin squares and then they are ortogonal by construction.
A latin square contains each number in each row and column exactly once.
A graeco-latin tour is also a magic tour, of course.
Example of a 8*8 graeco-latin-torus-knight tour ( numbers are in base 8 ):
8- | 00 | 57 | 14 | 75 | 32 | 61 | 26 | 43 |
7- | 27 | 74 | 01 | 60 | 15 | 42 | 33 | 56 |
6- | 44 | 21 | 50 | 03 | 76 | 17 | 62 | 35 |
5- | 63 | 02 | 45 | 16 | 51 | 34 | 77 | 20 |
4- | 36 | 65 | 22 | 47 | 04 | 53 | 10 | 71 |
3- | 11 | 46 | 37 | 52 | 23 | 70 | 05 | 64 |
2- | 72 | 13 | 66 | 31 | 40 | 25 | 54 | 07 |
1- | 55 | 30 | 73 | 24 | 67 | 06 | 41 | 12 |
a | b | c | d | e | f | g | h | |
you can download the program latleap.exe : (C-source is attached to the executable)
latleap version 0.8
and run it with command-line-parameters n,r,s :
"latleap n t p r s"
fill in the desired values for n,r,s e.g. :
latleap 12 t p l 1 2
computes and prints all (graeco-) latin torus-knight-tours on 12*12,
output copied to file SOLUTION.TXT
Type latleap without parameters to get a short usage- instruction
if you run new ranges , please send the solution.txt file to
mailto:magictour@free.fr
graeco latin tours of a (r,s)-leaper on a n*n-board
board-type (c=cylinder,t=torus),n,r,s,tours,closed tours/8,nodes
there are no graeco-latin leaper tours on a cyclinder for n<16
and thus no such tours on a normal board either
t,4,1,2,0,0,93
t,5,1,2,96,12,11057
t,6,1,2,0,0,377
t,6,1,3,0,0,141
t,6,2,3,0,0,37
t,7,1,2,32,4,429505
t,7,1,3,32,4,429505
t,7,2,3,32,4,429505
t,8,1,2,2112,224,32994985
t,8,1,3,0,0,63433
t,8,1,4,0,0,53
t,8,2,3,2112,224,32994985
t,8,2,4,0,0,21
t,8,3,4,0,0,53
t,9,1,2,0,0,9892081
t,9,1,3,168,21,328857257
t,9,1,4,0,0,9892081
t,9,2,3,168,21,328857257
t,9,2,4,0,0,9892081
t,9,3,4,168,21,328857257
t,10,1,2,0,0,8049
t,10,1,3,0,0,3440009
t,10,1,4,0,0,11961
t,10,1,5,0,0,437
t,10,2,3,0,0,11961
t,10,2,4,0,0,209
t,10,2,5,0,0,69
t,10,3,4,0,0,8049
t,10,3,5,0,0,437
t,10,4,5,0,0,69
t,11,1,2,32,4,65402049
t,11,1,3,216,25,2809061745
t,11,1,4,216,25,2809061745
t,11,1,5,32,4,65402049
t,11,2,3,216,25,2809061745
t,11,2,4,32,4,65402049
t,11,2,5,216,25,2809061745
t,11,3,4,32,4,65402049
t,11,3,5,32,4,65402049
t,11,4,5,216,25,2809061745
t,12,1,2,656,72,5420305073
t,12,1,3,0,0,15166609
t,12,1,4,96,12,56910394513
t,12,1,5,0,0,143489977
t,12,1,6,0,0,85
t,12,2,3,2048,0,202161786553
t,12,2,4,0,0,377
t,12,2,5,656,72,5420305073
t,12,2,6,0,0,45
t,12,3,4,0,0,3956772113
t,12,3,5,0,0,15166609
t,12,3,6,0,0,21
t,12,4,5,96,12,56910394513
t,12,4,6,0,0,37
t,12,5,6,0,0,85
t,13,1,2,128,12,1372980921
t,13,1,3,152,19,70938409017
t,13,1,4,152,19,70938409017
t,13,1,5
t,13,1,6,128,12,1372980921
t,13,2,3
t,13,2,4,128,12,1372980921
t,13,2,5,152,19,70938409017
t,13,2,6,152,19,70938409017
t,13,3,4,152,19,70938409017
t,13,3,5,128,12,1372980921
t,13,3,6,128,12,1372980921
t,13,4,5,128,12,1372980921
t,13,4,6
t,13,5,6,152,19,70938409017
t,14,1,2,0,0,125105
t,14,1,3,0,0,266943625
t,14,1,4,0,0,279753
t,14,1,5,0,0,266943625
t,14,1,6,0,0,251001
t,14,1,7,0,0,885
t,14,2,3,0,0,279753
t,14,2,4,0,0,905
t,14,2,5,0,0,251001
t,14,2,6,0,0,905
t,14,2,7,0,0,101
t,14,3,4,0,0,251001
t,14,3,5,0,0,266943625
t,14,3,6,0,0,125105
t,14,3,7,0,0,885
t,14,4,5,0,0,125105
t,14,4,6,0,0,905
t,14,4,7,0,0,101
t,14,5,6,0,0,279753
t,14,5,7,0,0,885
t,14,6,7,0,0,101
t,15,3,5,0,0,481329
t,15,3,6,0,0,209
t,15,5,6,0,0,481329
thanks to Werner Schauer for computing many of these ranges .
A list of the graeco-latin-torus-leaper tours for n<14
can be found here:
gllt
Here is an Executable to display the tours , BASIC-source-code
is attached to the executable , put the file gllt into the same directory
grgllt.exe
gllt contains one tour from each symmetry-class , one from each isomorphism-class
of leaper-graphs. The 13t(1,5) (isomorphic to 13t(2,3),13t(4,6) ) is incomplete
it took too long to compute all tours from this range.
We have the following isomorphism classes of torus-leaper-graphs for n<16 :
(one row = one class with its members)
4t(1,2)
5t(1,2)
6t(1,2)
6t(1,3)
6t(2,3)
7t(1,2),7t(1,3),7t(2,3)
8t(1,2),8t(2,3)
8t(1,3)
8t(1,4),8t(3,4)
8t(2,4)
9t(1,2),9t(1,3),9t(1,4),9t(2,3),9t(2,4),9t(3,4)
10t(1,2),10t(3,4)
10t(1,3)
10t(1,4),10t(2,3)
10t(1,5),10t(3,5)
10t(2,4)
10t(2,5),10t(4,5)
11t(1,2),11t(1,3),11t(1,4),11t(1,5),11t(2,3),11t(2,4),11t(2,5),11t(3,4),11t(3,5),11t(4,5)
12t(1,2),12t(1,4),12t(2,5),12t(4,5)
12t(1,3),12t(3,5)
12t(1,5)
12t(1,6),12t(5,6)
12t(2,3),12t(3,4)
12t(2,4)
12t(2,6)
12t(3,6)
12t(4,6)
13t(1,2),13t(1,3),13t(1,4),13t(1,6),13t(2,4),13t(2,5),13t(2,6),13t(3,4),13t(3,5),13t(3,6),13t(4,5),13t(5,6)
13t(1,5),13t(2,3),13t(4,6)
14t(1,2),14t(1,4),14t(2,3),14t(3,6),14t(4,5),14t(5,6)
14t(1,3),14t(1,5),14t(3,5)
14t(1,6),14t(2,5),14t(3,4)
14t(1,7),14t(3,7),14t(5,7)
14t(2,4),14t(2,6),14t(4,6)
14t(2,7),14t(4,7),14t(6,7)
15t(1,2),15t(1,3),15t(1,7),15t(2,4),15t(2,6),15t(3,4),15t(4,7),15t(6,7)
15t(1,4),15t(2,7),15t(3,5),15t(5,6)
15t(1,5),15t(1,6),15t(2,3),15t(2,5),15t(3,7),15t(4,5),15t(4,6),15t(5,7)
15t(3,6)
However , when we consider magic tours, then we must also take into account
the rows and columns where the vertices reside.
So, I add 2*n new vertices representing the n rows and n columns
and connect them with the squares which are on that
row or column. Then we get the following isomorphism classes,
in accordance with the nodecounts from the latleap-program :
4t(1,2)
5t(1,2)
6t(1,2)
6t(1,3)
6t(2,3)
7t(1,2),7t(1,3),7t(2,3)
8t(1,2),8t(2,3)
8t(1,3)
8t(1,4),8t(3,4)
8t(2,4)
9t(1,2),9t(1,4),9t(2,4)
9t(1,3),9t(2,3),9t(3,4)
10t(1,2),10t(3,4)
10t(1,3)
10t(1,4),10t(2,3)
10t(1,5),10t(3,5)
10t(2,4)
10t(2,5),10t(4,5)
11t(1,2),11t(1,5),11t(2,4),11t(3,4),11t(3,5)
11t(1,3),11t(1,4),11t(2,3),11t(2,5),11t(4,5)
12t(1,2),12t(2,5)
12t(1,3),12t(3,5)
12t(1,4),12t(4,5)
12t(1,5)
12t(1,6),12t(5,6)
12t(2,3)
12t(2,4)
12t(2,6)
12t(3,4)
12t(3,6)
12t(4,6)
13t(1,2),13t(1,6),13t(2,4),13t(3,5),13t(3,6),13t(4,5)
13t(1,3),13t(1,4),13t(2,5),13t(2,6),13t(3,4),13t(5,6)
13t(1,5),13t(2,3),13t(4,6)
14t(1,2),14t(3,6),14t(4,5)
14t(1,3),14t(1,5),14t(3,5)
14t(1,4),14t(2,3),14t(5,6)
14t(1,6),14t(2,5),14t(3,4)
14t(1,7),14t(3,7),14t(5,7)
14t(2,4),14t(2,6),14t(4,6)
14t(2,7),14t(4,7),14t(6,7)
15t(1,2),15t(1,7),15t(2,4),15t(4,7)
15t(1,3),15t(2,6),15t(3,4),15t(6,7)
15t(1,4),15t(2,7)
15t(1,5),15t(2,5),15t(4,5),15t(5,7)
15t(1,6),15t(2,3),15t(3,7),15t(4,6)
15t(3,5),15t(5,6)
15t(3,6)
two ranges n,l1,l2 and n,L1,L2 are isomorphic, iff
there is an integer k such that
( |k*l1| = |k*L1| (mod n) and |k*l2| = |k*L2| (mod n) )
or ( |k*l1| = |k*L2| (mod n) and |k*l2| = |k*L1| (mod n) )
Pegg, which leaper tours are possible ?
last updated: August/16/2003 |
© 2003 Guenter Stertenbrink mailto:magictour@free.fr |