Springertouren

By Guenter Stertenbrink Date 2021-07-16 05:34 Edited 2021-07-16 05:42 Upvotes 1

Computerschach mal anders

ich versuch (wieder) mal eine SSD mit allen geschlossenen 8x8 Springertouren zu erzeugen.
Um sie dann nach gewissen Eigenschaften und Statistiken zu durchforsten.
3 Methoden :
1.) klassisches backtracking um eine Springerweg zu verlaengern.
Dabei immer aufpassen, dass kein Feld mit nur einem Nachbarn
existiert. Das beschleunigt die Sache. Ca. 30000 Touren pro sec. pro Kern
In dieser Reihenfolge erzeugt lassen sie sich effektiv mit 7zip komprimieren :
weniger als 2 Bytes pro Tour, ca.3TB fuer alle. Das Dekomprimieren ist aber noch
nicht schnell genug.
2.) alle 50Milliarden 5*8- Weg-Strukturen erzeugen siehe McKay,1999
   Eine Wegstruktur kann im Durchschnitt mit 700 Teil-Touren (im 5x8) erreicht werden
und mit ca. 100 Teiltouren (im 3x8) fortgesetzt werden.
Da die Erreichbarkeit und Fortsetzbarkeit fuer partielle Touren mit gleicher
Wegstruktur identisch ist, gibt das auf einen Schlag 70000 Touren pro Wegstruktur
und nur 50e9*(700+100) muessen abgespeichert werden.
3.) Unterketten-Umdrehung. Aus einer Tour erhaelt man meist mehrere neue indem
man eine Reihe aufeinanderfolgender Springerzuege in umgekehrter Richtung
durchlaeuft. Das geht auch mit normalen Hamilton-Cyklen in Graphen,
ich weiss nicht wie das da heisst, ob das untersucht wurde.
Durch iteration erhaelt man >100000 Touren pro Kern pro Sekunde, aber man muss sicherstellen
dass keine (oder zumindest nur wenige) doppelt vorkommen und dass man auch viele erreicht -
der Rest kann wieder einfach aufgelistet werden. Erzeugt man systematisch alle erreichbaren
Touren, so ist das ca. 10 mal langsamer als wenn man nur die Parameter der
naechsten Umkehrung abspeichert. Das geht mit 1 Byte pro Tour.

1.) hatte ich halb fertig, dann kam SARS2
2.) dauert ca 60Tage auf meinem Laptop, Parallellisierung mit mehreren kernen
   ist nicht so einfach.
3.) ist evtl. auch theoretisch interessant. Permutationen aus S_64 die von
   Unterketten-Umkehrung erzeugt werden z.B. 1,2,3,7,6,5,4,8,9,...,64
wobei aber die Schnittpunkte durch Springerzuege erreichbar sein muessen
Wieviele Unterketten-Umkehrungen sind noetig um von einer Springertour
zur anderen zu kommen und geht das ueberhaupt bei allen Touren ?
(nein, Paritaet der 4 Zug-Richtungs-Anzahlen)
Zaehle die >< - Wechsel in der Permutation. Jede Umkehrung
erhoeht dieselbe um max.2
Eine Umkehrung tauscht 2 gegenueberliegende Kanten in einem der Springer-Parallellogramme.
Davon gibt es 148 mit den 3 Typen Quadrat (b1,a3,c4,d3) ,Karo(b1,a3,b5,c3) ,Lanzenspitze (a1,b3,d4,c2)

Das blosse Abzaehlen der Touren mit 2.) geht in ca. 12 Stunden auf meinem Laptop von 2014 mit SSD
(schnelles Sortieren grosser Dateien zum Finden und Aufaddieren der Teiltouren mit gleicher Wegstruktur)
indem man nur all die Wegstrukturen erzeugt
(8M fuer's 4x8, 161M fuer's 5x8) ,
und die zugehoerigen Teil-touren zuordnet und aufaddiert.
Man nimmt successiv jeweils ein Feld dazu und erweitert die Wegstrukturen.
Da gibt es dann 3 Moeglichkeiten, indem man das neue Feld mit 0,1,2 freien
Enden verbindet.
Diese Methode 2.) laesst sich auch fortsetzen auf 8X9,8x10... Bretter.
Aber nicht 9X9 etc., da explodieren die Zahlen.
Nun, auch das wurde in 2015 erfolgreich versucht, siehe unten.
Wenn jemand noch Rechenpower und grosse schnelle SSDs uebrig hat
kann er's mal versuchen

1997,pathstructures :
https://oeis.org/A001230
https://oeis.org/A001230/a001230.pdf

2011, [2.)] ttps://oeis.org/A193055
ptourn.c   Linux,Windows
http://magictour.free.fr

andere Beschreibung hier :
https://oeis.org/search?q=1067638&sort=&language=&go=Search
Er fuegt volle Spalten hinzu statt einzelne Felder wie in 2.)

====================================
in 2015 hier fuer 9x10 aus China :
https://oeis.org/search?q=1067638&sort=&language=&go=Search
19381952998732022416892 = 2e18 (2015)

After testing, network transmission is too slow, is the bottleneck of the whole calculation,
so the dual-machine operation is not single-machine fast. Recently optimized the program,
read-only write terabytes of oversized files, on a stand-alone machine to calculate the total
number of closed-circuit chessboards, the effect of the group, run for a month to get the
results the landlord wants:

And the total number of closed roads is too much, we only know the result of this digital model.
It is worth mentioning that the first run is the use of mobile hard disk, the result only ran for
more than a month, read-only written the amount of data on my mobile hard drive wrote bad,
Helplessly had to use the desktop comes with the hard disk, clean out of the space to run again.

Upon enquiry, the total number of closed roads could not be found on google,
This may be due to a miscalculation, or it is possible that this data is the first of its kind
in this round. If the latter can be verified, the results can be submitted to OEIS.
##### Before that, write the above results into plain text so that search engines can search for:

===================================
das erstaunlichste an Springertouren ist dieser Algorithmus, diese Methode, um das Brett
Feld um Feld mit Weg-structuren zu fuellen anstatt Springerzugketten zu verlaengern.
========================================

Jelliss hat eine umfangreiche Webseite ueber Springertouren, kurioses,
geschichtliches , auch zum download in .pdfs (in Englisch)
aber im wesentlichen ohne die Computer/Programmierung/Algorithmus-Aspekte
https://www.mayhematics.com/t/t.htm
https://www.mayhematics.com/t/8a.htm
====================================

By Thomas Zipproth Date 2021-07-16 13:22 Edited 2021-07-16 13:25 Upvotes 1

Finde ich interessant, aber ohne tiefere Beschäftigung mit der Materie schwer vollständig zu verstehen.
Deshalb ein paar Fragen:

1.)
Eine geschlossene 8x8 Springertour beginnt auf einem beliebigen Feld, betritt alle Felder einmal und endet wieder auf dem Ausgangsfeld?

2.)
Alle geschlossenen Springertouren:
Damit ist gemeint, alle verschiedenen geschlossenen Springertouren beginnend auf jedem der 64 Felder zusammengefaßt?

3.)
Eigentlich muss man aus Symetriegründen ja nur 10 Startfelder betrachten (ein Dreieck eines 4x4 Viertels),
da das aber nicht erwähnt wurde nehme ich an das diese Betrachtung aus irgendwelchen Gründen keine Rolle spielt?

4.)
Es werden 50 Milliarden 5*8- Weg-Strukturen erwähnt.
Damit sind vermutlich alle geschlossenen Springertouren auf einem 5x8 Brett gemeint.
Ist das ein getrenntes Problem oder hilft einem die Erzeugung dieser Touren irgendwie bei dem 8x8 Problem?

5.)
"Dabei immer aufpassen, dass kein Feld mit nur einem Nachbarn existiert."
Ein Feld hat immer je nach Definition mindestens 2 oder 3 Nachbarn.
Deshalb muss hier eine andere Definition der Nachbarschaft gemeint sein?

6.)
Am intressantesten scheint ja erst einmal das bloße Zählen der Touren zu sein.
Unter
https://www.mayhematics.com/t/8a.htm
wird aber erwähnt, das es gar nicht so offensichtlich zu sein scheint was man eigentlich zählt.

Ich finde hier 4 verschiedene Zahlen, mit ist aber nicht ganz klar, welche dieser Zahlen nun tatsächlich die Zahl "aller geschlossenen 8x8 Springertouren" ist:

1,658,420,855,433
1,658,420,247,200
13,267,364,410,532
106,138,915,284,256

By Guenter Stertenbrink Date 2021-07-16 14:35 Upvotes 1

Wikipedia hat auch einen ganz guten Artikel zur Einfuehrung
https://de.wikipedia.org/wiki/Springerproblem
Wolfram mathworld (in Englisch) :
https://mathworld.wolfram.com/KnightGraph.html

----------------------------------------
1.) ja
2.). Wobei der Startpunkt und die Richtung IMO irrelevant sind.
Ich wuerde es definieren als 64-er Untermenge der 168 Kanten
die einen grossen 64-er Zyklus bilden.
3.) der Einfachheit halber nicht erwaehnt. Als Symmetrie gibt es nur die 180-Drehung,
die symmetrischen Touren sind schnell gefunden. Die anderen haben 8 Symmetrien
mit meiner Definition. 16 bei einigen anderen Autoren.
4.) Nein, "Wegstrukturen" sind die "Pathstructure" im 1997-paper von McKay.

Eine (untere 5x8) partielle Tour sei eine Untermenge von Springerwegen (hier im 5x8) die auf Feldern
starten und enden welche mit dem Rest (hier 3x8) verbunden sind.
Alle anderen Felder (hier 24) werden von einem der Wege beruehrt.
Man macht sich leicht klar, dass dies genau das ist was eine Erweiterung zu einer vollen 8x8-Tour
zumindest theoretisch erlaubt.
Eine Wegstruktur ist quasi nur die Menge der Endpunkte der partiellen Touren
bzgl.Erweiterbarkeit kommt es ja nicht darauf an, wie die unteren beruehrt werden.
Im Computer ist das bei mir ein 16-Tupel von Zahlen aus {0,1,..,9},
wobei 0 : wird von 2 Kanten berueht, 1=wird von keiner Kante beruehr, 2-9 : wird von einer Kante beruehrt,
das andere Ende des Springerweges endet auf dem Feld mit der gleichen Zahl.
Also Zahlen 2,... kommen 0 oder 2 mal vor.
Ahh, vielleicht waere eine streng formale Definition besser, vielleicht spaeter.

5.) die Felder die bereits von dem bisher erzeugten Springerweg belegt sind werden rausgenommen.
Also z.B. nicht ...d4-c2-a4... ziehen, da a1 dann nur noch einen Nachbarn (b3) hat und nicht mehr
in die Tour reinpasst.

6.) mit meiner Definition sind es 13,267,364,410,532
Die SSD haette nur 1,658,420,855,433, komprimiert, die anderen koennte man leicht daraus erzeugen, wenn man will.

By Guenter Stertenbrink Date 2021-07-16 14:52 Edited 2021-07-16 15:11 Upvotes 1

ich hab noch eine Beschreibung aus 2005 in Englisch von meiner alten HD :
Es wird etwas Mathematik vorrausgesetzt, z.B. die Definition eines Graphen.
(paths,vertices,edges,edge-graph,Hamilton cycles)
Springertouren sind ja fuer Mathematiker Hamilton-Wege im Springer-Graphen

in narrow graphs , in order to count Hamilton cycles and other similar things ,
it's faster to extend path-structures than paths.

Define the width of a (undirected) graph G=(V,E) , V={1,..,n} as
the minimum over all permutations P=(p1,..,pn) of the vertices
of the maximum of sizes of the border-regions
Bk=N({pk+1,p2,..,pn}) /\ {p1,...,pk} ) for k=1,..,n

For knight's graphs on rectangles a*b with a<=b the width is a+a+1
(picture)

let G=(V,E) be a graph and B a subset of V
A pathstructure on B is a map ps:B-->{0,1,..}
with
PS1) exists k with |ps^-1(i)=2 for 1<i<=k and |ps^-1(i)|=0 for i>k
PS2) i,j>1 --> min(ps^-1(i))<=min(ps^-1(j))
pS3) i not in N(V-B) --> ps(i)=0
interpreting it as a set of paths in V-B see McKay

For any P and B the number of Hamilton cycles using the
edges with both end-vertices in ps^-1(0) and one end-vertex in ps^-1(1)
depends only on the path-structure of B.

So counting/generating Hamilton cycles on V can be done by recursively
counting/generating pathstructures on {1,..,k}

a (B,ps) is called extendable if there is a Hamilton cycle on G
matching ps

for the canonical enumeration of vertices of the 8x8 knight's tour graph
this gives the following counts for
k-ps, k-extendable ps, k-predecessor ps
k-hp-paths

you see from these counts how counting by ps is faster

-------------------------

a Hamilton cycle is uniquely determined by a subset
S of the edges E whose induced subgraph in the edge-graph is 2-regular.
However not each such S gives a hamilton cycle, it may also
give disjoint unions of cycles.

for Hamilton paths instead of cycles ("open tours")
you can just add one new vertex connected to each other vertex.

------------------------------

so the pathstructures on B-(ps^-1(0)/\N(V-B))
are just the subsets of edges hamilton cycles when restricted to B

--------------------------------

there are 7 possible ways to extend a ps B on {1...s-1} to a ps T on {1...s}
for u with B(u)>1 let B_(u) be the unique vertex !=u with B(B_u)=B(u)

u<v in N(s)/\{1...s-1}
1.) T(s)=1
2.) B(u)=1 then T(s)=s:T(u)=s
3.) B(u)>1 then T(s)=B(u):B(u)=0
4.) B(u)=1 and B(v)=1 then T(u)=s:T(v)=s:T(s)=0
5.) B(u)=1 and B(v)>1 then T(u)=B(v):T(v)=0:T(s)=0
6.) B(u)>1 and B(v)=1 then T(v)=B(u):T(u)=0:T(s)=0
7.) B(u)>1 and B(v)>1 then T(u)=0:T(v)=0:T(P(v))=B(u):T(s)=0
for x in N({s+1...n})/\{1,..,s} set T(x)=0 in all 7 cases

{picture to illustrate this}

---------------------------------------------------

similarly there are 8 ways to form possible predecessors :

hier mein erstes BASIC-Programm aus 2005, welches Springertouren mit der Wegstruktur-Methode abzaehlt :
http://magictour.free.fr/NEWM8.BAS
es erzeugt bei jedem Schritt Dateien p und q , die sortiert werden mit DOS-sort
Es ist nicht schnell, 6*6 ergibt die 9862 Touren nach einigen Minuten/Stunden.
Schnelles Linux-C-Programm : http://magictour.free.fr/ptourn
unter Ubuntu ./ptourn 6 6 ergibt 9862 nach 4 Sekunden

By Benno Hartwig Date 2021-07-16 17:59 Upvotes 1

> Eigentlich muss man aus Symetriegründen ja nur 10 Startfelder betrachten (ein Dreieck eines 4x4 Viertels)...

wobei beim Start auf den Diagonalenfeldern nur die Startzüge betrachtetet werden müssen, die den Springer unterhalb der Diagonale landen lassen.
Die Lösungen mit Startzügen zu Feldern oberhalb der Diagonale sind dann symmetrisch dazu.