DIR Return Create A Forum - Home
---------------------------------------------------------
knight tours
HTML https://knighttours.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: magic tours
*****************************************************
#Post#: 31--------------------------------------------------
y-balanced 4-symmetry avoiding paths make magic 2-knight tours
By: gsgs Date: January 4, 2024, 9:24 am
---------------------------------------------------------
Post by gsgs » 22 February 2023, 10:12 am
instead of searching for magic knight tours in the m*n rectangle
you can often better search for y-balanced 4-reflection-symmetry
avoiding knight paths
of length m*n/4. These are then extended by their reflections to
make
magic 2-knight tours or 4-knight tours.
The reflections build just the negatives of the original path,
so the row and
column sums will be constant.
"y-balanced" means, that there are the same number of cells
visited in each column.
This is needed for the Sxy reflection which is only the neagtive
modulo m*n/2
sind the negative modulo m*n is already used by the Sy-step.
The 4 reflection symmetries are Sxy,Sy,Sx , of which Sx and Sy
induce one rook-move
into the tour, so they are no full knight's tours.
I apply first Sxy then Sy to the path and get a magic 2-knight
tour (2kt) if start and end is suitably
chosen, else it's a magic 4-knight tour .
I'm getting many 4-fold symmetric (==>magic) extendable 2-kts
quickly now upto 20x20 with my new program
e.g. all 1606 linkable (=start and end in the top 2 rows) 8x10s
in 1 second, ~100 million (complete)
12x12s in 3 days with the latest version.
Why was this method missed all the years,decades,centuries ?
Make balanced symmetry-avoiding paths rather than full magic
tours !
Only m*n/4 steps and no need to calculate sums,
useful especially in the pre-computer times.
Well, it gives "only" 2-kts - albeit symmetric ones.
And these can be extended to 1-kts with 4xn (or 6xn?) or 8xn
magic 3-kt "Linkers".
I found 4x8,4x12,4x16 Linkers, but no suitable 4x10 Linkers.
{###correction : I do have suitable 4x10 and 4x14 Linkers
also###}
Magic 1kts also work as Linkers, if start and end cells match.
But unfortunately none of the magic 4xn and 6xn on your page
have start and end cells in the top 2 rows (2xn).
There might be a process, an algorithm, how to construct
suitable 4xn - Linkers (magic 3kts).
for example tour this 20-cell y-balanced
4-symmetry avoiding region in the 8x10 :
xx,--,xx,--,xx,--,--,--,--,--
xx,--,xx,--,xx,--,--,--,--,--
--,xx,--,xx,--,--,--,--,--,--
--,xx,--,xx,--,--,--,--,--,--
--,--,--,--,--,xx,--,xx,--,xx
--,--,--,--,--,xx,--,xx,--,xx
--,--,--,--,--,--,xx,--,xx,--
--,--,--,--,--,--,xx,--,xx,--
one solution :
path:
02,--,08,--,04,--,--,--,--,--
07,--,03,--,09,--,--,--,--,--
--,01,--,05,--,--,--,--,--,--
--,06,--,10,--,--,--,--,--,--
--,--,--,--,--,11,--,17,--,13
--,--,--,--,--,16,--,12,--,18
--,--,--,--,--,--,20,--,14,--
--,--,--,--,--,--,15,--,19,--
after Sxy :
02,39,08,35,04,--,--,--,--,--
07,34,03,40,09,--,--,--,--,--
38,01,32,05,36,--,--,--,--,--
33,06,37,10,31,--,--,--,--,--
--,--,--,--,--,11,30,17,26,13
--,--,--,--,--,16,25,12,21,18
--,--,--,--,--,29,20,23,14,27
--,--,--,--,--,24,15,28,19,22
and the magic 2-kt after Sxy and Sy:
02,39,08,35,04,77,46,73,42,79
07,34,03,40,09,72,41,78,47,74
38,01,32,05,36,45,76,49,80,43
33,06,37,10,31,50,71,44,75,48
68,55,64,51,70,11,30,17,26,13
63,60,69,56,65,16,25,12,21,18
54,67,58,61,52,29,20,23,14,27
59,62,53,66,57,24,15,28,19,22
move 40->41 is the rook move. This can't be avoided.
The pattern can be extended in the obvious way
to make 8x12,8x14,... magic 2-kts.
See here for a 32x32 :
HTML http://magictour.free.fr/32x32.GIF
It uses a slightly different symmetry-avoiding knight friendly
balanced area,
with better start and end cells.
These give
2,4,12,60,330,1260,5074,22816,99180,417008,1778036,7666920
solutions for 8x10,8x12,...8x32
Top
gsgs
Posts: 22
Joined: 6 February 2023, 8:07 am
Location: Germany
Contact: Contact gsgs
Re: y-balanced 4-symmetry avoiding paths make magic
2-knight-tours
Post by gsgs » 23 February 2023, 4:25 am
why did I not just take this pattern :
Code: Select all
x,-,x,-,x,-,x,-,x,-
x,-,x,-,x,-,x,-,x,-
-,x,-,x,-,x,-,x,-,x
-,x,-,x,-,x,-,x,-,x
-,-,-,-,-,-,-,-,-,-
-,-,-,-,-,-,-,-,-,-
-,-,-,-,-,-,-,-,-,-
-,-,-,-,-,-,-,-,-,-
it's y-balanced, 4-symmetry-avoiding,
and better tourable.
The reason is the choice of possible start and endcells
so to get a "linkable" 2-kt.
With linkable I mean, the start and endcells as well as
the cells of the rook-move of the tour must be in the
top (or bottom) 2 rows , so we can apply a Linker to make 1-kts.
The endcell of the length=m*n/4 path is not the endcell of the
resulting extended tour but rather the Sxy-reflection of it.
If these two are in the upper 2 rows, then the other 2 linkable
cells
are also in the upper 2 rows, since they are just the
Sy-reflections.
So, make sure the endcell of the path is a knight-move away from
the
Sxy-reflection of the startcell of the path, so to get a 2-kt
and not a 4-kt.
Top
gsgs
Posts: 22
Joined: 6 February 2023, 8:07 am
Location: Germany
Contact: Contact gsgs
Re: Magic Two-Knight Tours
Post by gsgs » 24 February 2023, 9:29 am
There are methods how to construct magic 1-kts
from these m*n/4 paths instead of 2-kts, but they can
no longer be fully symmetric.
E.g. here is a path which gives magic,
almost 4-symmetric 1-kts for 10x(12+4n) :
Code: Select all
--,--,--,03,--,--,--,--,--,--
--,04,--,--,--,02,--,--,--,--
--,--,--,01,--,--,--,--,--,--
05,10,07,--,13,--,--,--,--,--
08,--,12,--,--,--,14,--,--,--
11,06,09,--,15,--,--,--,--,--
--,--,--,--,--,--,16,--,--,--
--,--,--,--,17,--,--,--,19,--
--,--,--,--,--,--,18,--,--,--
--,--,--,--,--,28,--,22,25,20
--,--,--,29,--,--,--,27,--,23
--,--,--,--,--,30,--,24,21,26
applying Sxy and Sy gives
this 4-symmetric magic 2-kt :
Code: Select all
56,51,54,03,60,61,B8,67,70,65
53,04,57,62,B9,02,59,64,B7,68
50,55,52,01,58,63,C0,69,66,71
05,10,07,48,13,A8,73,B4,B1,B6
08,49,12,A7,74,47,14,A9,72,B3
11,06,09,46,15,A6,75,B2,B5,B0
80,85,82,A5,76,45,16,39,36,41
83,A2,79,44,17,A4,77,42,19,38
86,81,84,A3,78,43,18,37,40,35
A1,96,99,90,93,28,31,22,25,20
98,87,94,29,32,89,92,27,34,23
95,A0,97,88,91,30,33,24,21,26
now just swap 01 with 03 and 61 with 63
to get a magic 1-kt , no Linker needed.
Code: Select all
56,51,54,01,60,63,B8,67,70,65
53,04,57,62,B9,02,59,64,B7,68
50,55,52,03,58,61,C0,69,66,71
05,10,07,48,13,A8,73,B4,B1,B6
08,49,12,A7,74,47,14,A9,72,B3
11,06,09,46,15,A6,75,B2,B5,B0
80,85,82,A5,76,45,16,39,36,41
83,A2,79,44,17,A4,77,42,19,38
86,81,84,A3,78,43,18,37,40,35
A1,96,99,90,93,28,31,22,25,20
98,87,94,29,32,89,92,27,34,23
95,A0,97,88,91,30,33,24,21,26
extend this by putting a "normal"
4nx10 inbetween like this :
Code: Select all
--,--,--,03,--,--,--,--,--,--
--,04,--,--,--,02,--,--,--,--
--,--,--,01,--,--,--,--,--,--
05,10,07,--,13,--,--,--,--,--
08,--,12,--,--,--,14,--,--,--
11,06,09,--,15,--,--,--,--,--
--,--,16,--,--,--,22,--,--,--
17,--,--,--,21,--,--,--,23,--
--,--,--,19,--,--,--,25,--,--
--,18,--,--,--,20,--,--,--,24
--,--,--,--,--,--,16,--,--,-- {
*****************************************************