DIR Return Create A Forum - Home
---------------------------------------------------------
knight tours
HTML https://knighttours.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: general Hamiltonian cycles problem
*****************************************************
#Post#: 4--------------------------------------------------
Warnsdorf rule
By: gsgs Date: March 4, 2023, 9:11 am
---------------------------------------------------------
I implemented several variations of Warnsdorf's rule
and tested them on knight's square graphs.
1.) normal, original rule, starting next to the first cormer.
When there are several equal possibilities, choose the first
one.
(rectangle vertices enumerated by rows,columns)
2.) same as 1.) , but choose the last one
3.) proceed from both ends of the partially finished tour.
At each step choose the end with fewest free neighbors
and go to the one which itself has the fewest free neighbors.
Take the first vertex, if there are equal choices.
4.) join paths.
Start with all vertices as paths of length 1.
At each step choose the path and the end with the fewest
free neighbors (=path-ends)
and join it with the one which itself has the fewest free
neighbors
Take the first vertex, if there are equal choices.
seconds needed for the 100x100 and 200x200 rectangles :
1.) 0.8,4.0
2.) 1.0,4.0
3.) 0.7,4.1
4.) 10.9,252
the results for n*n=6x6,...,200x200
(1=yes,0=no)
tour found, n odd :
Code: Select all
1.) 00
0000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000
0
2.) 00
0000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000
0
3.) 76
1111111011110111111111111111110111111001110110100101111101001111
111110010101111101111101111111010
76
4.) 97
1111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111
97
tour found, n even :
Code: Select all
1.) 76
1111111011011111101111111111111111111100111110110101111110101101
1011101101010001111101111001011111
76
2.) 40
1111111111111010111011101111111001000000011010000100000110010001
1000001000000000000000100000000001
40
3.) 52
1111111111111100111101110111000101010101110101010011110101010101
0000010001010000010001001111000000
52
4.) 98
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111
98
closed tour found, n even :
Code: Select all
1.) 00
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000
0
2.) 01
0000000000000000000000000000000000000000000010000000000000000000
0000000000000000000000000000000000
1
3.) 38
1111111101111100111101010101000000000101110101000001010101010001
0000010000010000010001000001000000
38
4.) 87
1111001111111111111111111111101111111111111111111011111101011010
1111111111011101111111111111111110
87
There could still be bugs...
I expect similar results for n/2*n/2 4-symmetry-classes-graphs ,
where
a tour makes a magic 2-kt if y-balanced.
Make a program that for any m,n creates a Warnsdorf-random magic
4-symmetric 2m*4n 2-kt.
Optional with rolling-pin start/end .
---------------------not so easy, it won't work with the normal
Warnsdorf rule
on larger boards (y-balanced !) , I give up on this
------------------edit 2023-03-04 ----------------------
as a final step we could do subpath reversals a la Euler to
convert open tours
into closed ones or to change the ends, when there are dead ends
Top
-------------------------
on the 8x8 with Warnsforf I get 600000 tours per second ,
7894584 in total,
and 100000 with normal backtrcking
but on larger boards normal backtracking (trying to find all
solutions)
is often trapped in useless branches of the searchtree without
producing any solutions for long time.
Not so with the Warnsdorf-rule.
--------------
392666316 Warnsdorf tours on the 8x10 , found in 15min and
2.3e9 nodes=knight-placements
and take-backs.
------------------------------
I converted knight-tour problems to tsp-instances (traveling
salesman problem)
and let concorde.exe solve it.
It finds a closed tour for all problems that I tried (<=50x50)
but it needs 2 minutes for the 50x50.
It finds this tour for the 8x8 :
HTML http://magictour.free.fr/tsp8x8.GIF
It looks Warnsdorf-like. - But on the 50x50 it sometimes crosses
the almost empty board, unlike Warnsdorf
It did not finish the 100x100 overnight, so I stopped it.
There is another heuristic solver , LKH, reportedly faster but
randomized,may fail,
I have not tried it yet , needs another computer.
-------------------------
> Installing LKH on a Unix-like system (e.g. Linux or Mac) can
be as simple as running these commands:
> curl -LO
HTML http://www.akira.ruc.dk/~keld/research/
...
2.0.10.tgz
> tar zxf LKH-2.0.10.tgz
> cd LKH-2.0.10
> make
> cp ./LKH /usr/local/bin/
>--------------
> Concorde is a bit more fiddly to install, but once you have it
working it’s simple to run:
> concorde knig8x.tsp
> Be warned that it creates a LOT of temporary files in the
working directory, so you may want
> to do something a bit more elaborate and run it from a
different directory,
============================================
on 2023-03-04 I tried linkern.exe , downloaded from here :
HTML https://www.math.uwaterloo.ca/tsp/conco
... nloads.htm
linkern finds Hamilton cycles (= closed knight tours) in n*n
knight-graphs
for n<=50 .
It takes 88s for the 50x50 , 367s for the 100x100
============================================
Top
I think the problem is, that there may be left free areas,
holes, in some places of the board
which can't be toured. So it's useful to keep a big convex-like
free area.
This is achieved by chosing the first vertex, if possible =
staying close to the startvertex.
Proceed froom top to bo bottom, leave no holes.
"Divide and conquer-algorithm".
One other proposed strategy was to choose the vertex farthest
away from the center,
if there are equal choices.
But, when you want a closed tour you must go back to the
startvertex.
In that case, maybe go to the other side first along the border
and
then stay close to that distant side, as good as possible.
------------
In these 1kt-counting algorithms they fill the board cell by
cell from top to bottom
with "pathstructures" = collections of extandable paths, which
are ultimatively
joined to give a full 1kt. They only need to consider the last
two lines,
that reduces the number of different pathstructures and gives
the
efficiency in counting 1kts.
-------------
however, this is specific to knight tours. But it is desirable
to find an algorithm that
works well for any graph, or even tsp , as 4.) above.
Post by gsgs » 3 March 2023, 3:05 pm
Douglas Squirrel in 1996 gives a refined Warnsdorf algorithm
which looks to me almost as fast as the original rule but more
complicated with 43 tiebreaking rules depending on
some specified squares reached and n mod 8.
He claims to have proved that it produces a (open ?) tour for
all n>112 . 3 other rules cover the cases <112
HTML https://raw.githubusercontent.com/dougl
... rrel96.pdf
he orders the 8 possible knight moves and gives several
changing preferences to the orders in case of a Warnsdorf-tie.
The smallest/largest angle preference is just one of them.
It seems to be a successful idea, although there is no universal
such ordering.
*****************************************************