DIR Return Create A Forum - Home
---------------------------------------------------------
knight tours
HTML https://knighttours.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: magic tours
*****************************************************
#Post#: 5--------------------------------------------------
8x10 magic knight's tours
By: gsgs Date: March 4, 2023, 9:16 am
---------------------------------------------------------
The smallest rectangular board with magic knight tours is the
8x8, which has been
searched completely already. So the next is 8x10.
An exhaustive search is probably out of reach, so we collect
single tours ,
as they had been doing for 183 years now ifor the 8x8.
I found one in Jan.2020 by linking a 4x8 and a 6x8 with 2 links.
Then in Feb.2020 Awani Kumar sent a list of 24 (10 different
magic)
by linking two 4x10s with 4 links.
Then I found 12 in 2020 ? by linking a 4x8 and a 6x8 with 4
links.
(counting only geometrically different tours)
The more links, the more magic tours , the more computation time
, the more complicated ?!
[img]
HTML http://magictour.free.fr/8x10.PNG[/img]
22+1+10 tours are different, 20 open and 13 closed
file :
HTML http://magictour.free.fr/8x10.txt
I use numbers T(0,..,m*n-1) for the board-cells visited at move
i.
always starting at zero.
It's compatible to my programs and modulo-math.
But I may change it to A(1..m,1..n) to show the movenumbers
in the cells starting at 1 9as usual ?!).
However, one line per tour is better IMO for multiple tours in
one file
than rectangles. Easier to check,sort by computer.
-----------------------
I found 4 more magic 8x10s now
[edit:12 , searching 4 of 12 start-end combinations]
( the last 4 open ones in the updated picture above)
by partitioning the board into these
two knight-friendly symmetric parts and touring them separately.
That gave 1216424180 knight's tours for each part alone.
For an estimated 1.2e9^2/40=4e16 tours by combining them,
0,001% of the estimated total of 10^22 open 8x10 tours.
Then I picked a matching start and end cell at random and
stored the 18 sums for each of the 20866920 and 25972378
solutions.
I calculated the 18 sums for each, normal for the first part
and magic constant - sum for the second, 1 byte per sum.
Then I sorted that 800MB file and searched for matching sums.
This gave the 4 solutions. The whole process took 3 hours
and luckily it worked without much debugging.
If someone wants to repeat it for others of the 24
start-end-combinations or the other knight-friendly partition,
I can send the programs but it still needs programming skills,
all the steps are not fully automised.
I estimate > 100 magic 8x10 tours with this method.
This same procedure gives 21 of the 108 magic 8x8 tours = 20%.
There are 7900012 solutions per part , so combinations give
8e6*8e6/30/2e16 = 0.015% of all tours but 20% of the magic ones.
-----------------edit 2023-02-21----------------------
the calculated chance to get the 14 sums matching with this
method
is very low. There are an estimated 50 sums that may occur
in each line, so 1/50^14 (the last 2 sums are forced)
or < 1e-16 with 20 million sums checked.
That I still succeeded with 4,1,3,4 matches for the 4 checked
start-end combinations is presumably because some "inverse"
sub-paths are symmetric.
So I do not expect this method to be useful for other,
non-symmetric,
knight-friendly partitions.
With 4 out of 12 start-end combinations checked my estimate for
the total number of tours with this method is down to 36.
I started a complete search for 180^ symmetric magic 8x10s on
one Intel Atom Z3735 - core.(<2W),
expecting ~10 solutions. It may take 1 month....I assume Yann
could do it in <1h
1600 8x10 double symmetric magic 2-kts (two-knight-tours) and
their
generating paths
HTML http://magictour.free.fr/8xtgb.GIF
#Post#: 32--------------------------------------------------
Re: 8x10 magic knight's tours
By: gsgs Date: January 6, 2024, 6:10 am
---------------------------------------------------------
--------------2024-01-06--------------
I'm rerunning the search for symmetric magic 8x10s now on a
Z3735 processor, 1 core ...
hamp4m.d1 8 10
this run was interrupted after 53 days in Feb.2023 without
storing results
The estimated runtime was 30d
in Linux I see, that the empty output-file was accessed after 14
days ?!?
That should have been a solution
Or a power-failure and restart, I don't remember
hamp4m.d1 8 8 takes 17h on the tecra
#Post#: 34--------------------------------------------------
Re: 8x10 magic knight's tours
By: gsgs Date: February 20, 2024, 12:53 pm
---------------------------------------------------------
a simple brute-force program (hamp4r.c12 8 12 x) to search for
(180"-rotation)symmetric magic 8x10 knight's tours
found no solution after about 1 day on 20 cores.(x=1..20)
The program found the 16 symmetric 8x8 tours
in 20 min on 1 core
and the first symmetric magic 8x12 (see below)
after 1 day on 20 cores. (estimated time
for the total search = 10000 days on one core)
From the nodecounts I had expected some 8x10
solutions, so I assume there is some mathematical
argument that symmetric magic knight's tours
are only possible when both sides of the rectangles
are divisible by 4.
40,77,02,61,38,75,58,19,94,33,56,17
03,62,39,76,01,60,95,34,57,18,93,32
78,41,70,05,74,37,20,59,24,91,16,55
63,04,73,42,71,00,35,84,21,54,31,92
44,79,06,69,36,83,48,23,90,25,52,15
07,64,43,72,11,68,85,26,53,22,89,30
80,45,66,09,82,47,12,49,28,87,14,51
65,08,81,46,67,10,27,86,13,50,29,88
40,--,02,--,38,--,--,19,--,33,--,17
03,--,39,--,01,--,--,34,--,18,--,32
--,41,--,05,--,37,20,--,24,--,16,--
--,04,--,42,--,00,35,--,21,--,31,--
44,--,06,--,36,--,--,23,--,25,--,15
07,--,43,--,11,--,--,26,--,22,--,30
--,45,--,09,--,47,12,--,28,--,14,--
--,08,--,46,--,10,27,--,13,--,29,--
HTML http://magictour.free.fr/8x12-sy.bmp
that gives the idea to search
such patterns only ...
... but no other such solution was found with complete search,
1d,12 cores
a 2nd solution was found after 50 core*days (from 10000
estimated)
and it also looks special. 88 of its 96 edges have their
horizontal reflection included.
HTML http://magictour.free.fr/8x12-sy.GIF
--------update 2024-02-29--------------------
These were just the first 2 found (randomly) out of an estimated
500.
I'm now searching for all such tours with 3 visited cells per
row
after 24 moves.
This should finish in some weeks or days.
---------------
from the first 40 such solutions 19 were of that 2nd type above,
i.e, had only 8 edges whose horizontal reflection was not
part of the tour.
Another 8 had only 12 such edges
----------2024-03-02-----------------
solutions are getting rarer, I expect 80 (istead of 500)
and these include tours and inverse tours, so 40 different ones
-----------------2024-03-04----------------
55066 2-symmetric magic 12x12 tours of that "semi-4-symmetric
A,B,-Sy(A),-Sy(B),Sxy(A),Sxy(B),-Sx(A),-Sx(B)" type
were found in 2 hours on my laptop (27319 different ones)
HTML http://magictour.free.fr/cxc.mtn
also :
30 * 16x12s in 5min
661 * 16x8s in 4sec
4 * 16x16s in 10min
2532 * 20x16s in 30min
0 * 20x20s in 10h
estimated 2e12 * 16x16s in 1e13sec
-------------------------------------
this reminds me to early 2023 when I examined
4-symmetric 2kts . Now I see, that you can make 1kts
with "modified" 4-symmetry
A,B,-Sy(A),-Sy(B),Sxy(A),Sxy(B),-Sx(A),-Sx(B)
instead of
A,B,Sxy(A),Sxy(B),-Sx(B),-Sx(A),-Sy(B),-Sy(A)
---------2024-03-12----------------------
in order to create symmetric 4m*4n knight's tours ...
it's probably easier and more suitable to create
these special A,B,-Sy(A),-Sy(B) tours .
And again it's probably easier to require
in addition that the cells in A and B are from the
left half and have no two cells in the same aligned 2x2 box.
These tours can then be drawn as double king-tours
e,g. this 12x12 tour :
[code]
(4,6)-(6,5)
o-o-o o-o-o
| | | |
o o o o o-o
| |\ | |
o o o o o o
| | | | | |
o o o o o o
| \ | |
o o o o o o
|/| | |/| |
o o-o o o-o
03-02-01 24-23-22
| | | |
04 15 00 25 20-21
| |\ | |
05 14 16 26 19 35
| | | | | |
06 13 17 27 18 34
| \ | |
07 09 12 28 30 33
|/ | | |/ | |
08 10-11 29 31-32
[/code]
you can attach columns on the left to make it
12x16,12x20,...
-----------------
on the 8x8 we have 272 symmetric magic knight tours
from 16 symmetry classes and 32 of type AB-a-b from
2 symmetry classes none of them of the special type
as in the 12x12 shown above.
So the cases 8*4n are not included yet
-------------------------
number of such specian symmetric magic knight tours :
12x12:4
12x16:249
12x20:19617
12x24:1279902
16x12:27
16x16:17272
16x20:>4e6
20x12:104
20x16:1411614
20x20:>5e5
20x24:?
24x12:1703
24x16:?1960
28x12:>6700
*****************************************************