DIR Return Create A Forum - Home
---------------------------------------------------------
knight tours
HTML https://knighttours.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: 8x8 knight's tours
*****************************************************
#Post#: 11--------------------------------------------------
counting 8x8 knight tours
By: gsgs Date: March 26, 2023, 12:17 pm
---------------------------------------------------------
1996, Loebbing+Wegener :
HTML https://www.combinatorics.org/ojs/index.php/eljc/article/view/v3i1r5
1997, McKay :
HTML https://openresearch-repository.anu.edu.au/bitstream/1885/40759/3/TR-CS-97-03.pdf
1997?, Loebbing+Wegener , correction
2011, Zhao Hui Du
HTML https://oeis.org/A193055
2014, Chernov :
HTML http://alex-black.ru/article.php?content=141
2014 Haanpaa+Ostergard :
HTML https://www.ams.org/mcom/2014-83-286/S0025-5718-2013-02741-X/S0025-5718-2013-02741-X.pdf
HTML http://magictour.free.fr/knig8x8.GIF
#Post#: 12--------------------------------------------------
Re: counting 8x8 knight tours
By: gsgs Date: March 28, 2023, 4:17 am
---------------------------------------------------------
a better method to count all closed knight's tours
--------------------------------------------------
it's more efficient than the usual way of extending an existing
path
in all possible ways by continuously adding one new unvisited
vertex to the end of the path :
use a fixed pre-calculated order of the vertices (=board-squares
= cells)
and cover the first 1,2,...n cells completely by collections of
potentially extendable paths by adding one more vertex at a time
at each step and trying to extend the previous
collections in all possible ways.
The extensions only depend on the endpoints of the paths, not
on how they wind to fill the area.
So the tours can be grouped by the collections of endpoints
(=pathstructures) which results in the high number of tours,
while the computer only walks through the
path-endpoint-collections,
not through all the path-collections.
The efficiency of the method depends on the precalculated
ordering
of the cells so to minimize the number of possible
endpoint-collections.
For this the bordersize at each step should be small,
The border at step k is the set of cells in the already
covered area {v(1),v(2),...,v(k)) that are connected
(a knight's move away) to some cell in the still uncovered
area {v(k+1),...,v(n)}.
Plus vice versa the set of cells in the uncovered area
that are connected to some cell in the covered area -
this should also be small since it reduces the potential
future increase of pathstructures at the following steps.
For the 8x8 knight's graph the minimal sum of the 64*2
border-area-sizes that I found so far is 1616 with this ordering
:
01,11,18,03,09,05,15,13,07,20,22,24,12,02,06,16
14,08,04,31,29,27,10,25,23,21,19,17,32,30,28,26
34,36,38,40,39,37,35,33,48,46,55,44,53,42,51,63
49,57,59,61,41,43,45,47,50,52,54,58,60,62,56,64
resulting in a calculation time of 3.5 hours (1 core at 3 GHz)
to enumerate all closed 8x8 knight's tours.
While the natural left-right;top-bottom ordering
01,02,...,64 gives a sum of bordersizes of 1752
and a calculation time of 15 hours.
The ordering from the Haanpaeae-Ostergard paper gave
a bordersizesum of 1708 and an execution time of 9 hours.
--------edit---------------
it's more complicated, it's not just the sum of border-sizes
*****************************************************