Berechnen von magischen Springertouren


August 5 2003: Projekt beendet. Alle 136 Bereiche sind geprüft worden.
Es gibt 140 magische Springertouren auf dem Schachbrett und keine von diesen
ist diagonal magisch.



Dieses Projekt sollte alle magischen Springertouren finden
( " MKTs") auf dem 8*8 Schachbrett.
Eine Springertour (Englisch: knight's tour) ist eine n*n Matrix A(n,n) die
alle Zahlen von 1 bis n*n genau einmal enthaelt und aufeinanderfolgende Zahlen sind einen
Springerzug weit entfernt:
A(u,v)=1+A(x,y) <==> (u-x)*(u-x)+(v-y)*(v-y) = 5.
Die Tour ist magisch genau dann, wenn alle Reihen und Spalten die Summe (n*n+1)*n/2 ergeben
, welches die "magische Konstante" der Springertour ist.
Die Tour ist diagonal magisch, falls auch noch
die zwei Summen der Hauptdiagonalen die magische Konstante ergeben.
Dieses Projekt hat gezeigt, daß keine diagonal magische Springertour auf dem 8*8 Brett existiert
Die Tour A heisst pandiagonal, genau dann, wenn die Summe aller gebrochen Diagonalen ebenfalls die magische Konstante ergeben.
Also: SUMME {j=1..n} von a(j,(i+j) mod n) = n*n+1)*n/2 für i=0..n-1
Und : SUMME {j=1..n} von a(j,(i-j) mod n) = n*n+1)*n/2 für i=0..n-1

Manchmal werfen MKTs auch "semimagic" und diagonal magische Touren
magische genannt. Aber wir folgen Jelliss' Namengebung,
in der Ansicht, dass die zwei Hauptdiagonalen nicht so wichtig sind.
Im folgenden sei n = 8.

Vor diesem Projekt waren 2128 MKTs bekannt, aus 133
Symmetrie-Klassen (Definition siehe unten). 112 neue MKTs wurde während des Projektes gefunden
aus 7 Symmetrie-Klassen.

Für eine vollständige Liste Siehe:
http://www.ktn.freeuk.com/mc.htm

und hier ist eine vollständige Liste aller 2240 MKTs, der 140
Symmetrie-Klassen und der 108 Geometrie-Klassen in computerlesbarer Form: (674KB)
mkts

Beispiel für eine MKT:

8- 01 30 47 52 05 28 43 54
7- 48 51 02 29 44 53 06 27
6- 31 46 49 04 25 08 55 42
5- 50 03 32 45 56 41 26 07
4- 33 62 15 20 09 24 39 58
3- 16 19 34 61 40 57 10 23
2- 63 14 17 36 21 12 59 38
1- 18 35 64 13 60 37 22 11
a b c d e f g h
Beverley, 1848 a8-c1

Dies ist die erste gefundene MKT.

Das Start-Quadrat ist das Quadrat, das "1" enthält und das End-quadrat ist das Quadrat, das "64" enthält. Dies sind a8 und c1 im obigen Beispiel.

Zur Geschichte der Suche nach MKTs siehe: (in Englisch) http://www.ktn.freeuk.com/1d.htm

Jede MKT ergibt 15 anderen MKTs in der gleichen Symmetrie-Klasse durch Drehung, Reflexion und Gegenlaeufige Numerierung.
Eine Tour ist geschlossen, wenn Startfeld und Endfeld eines Springerzug weit entfernt sind
ansonsten ist sie offen.

Eine geschlossene MKT ergibt manchmal neue MKTs in der gleichen Geometrie-Klasse, durch Addieren einer Konstanten c zu jeder Zugnummer:
B(x,y) = ((A(x,y)-1+c) modulo 64) +1

Es gibt 2240 MKTs aus 140 Symmetrie-Klassen und
108 Geometrie-Klassen,

1232 offene MKTs aus 77 Symmetrie-Klassen und 77 Geometrie-Klassen, und

1008 geschlossene MKTs aus 63 Symmetrie-Klassen und 31 Geometrie-Klassen.

Wir hatten geschätzt, daß ein 2GHz Computer alle MKTs
in weniger als 6 Monaten finden sollten.
Tatsächlich , nachdem JC Meyrignac sein Programm nochmals optimiert hatte
wurden nur 2 Monate gebraucht!

Das Programm kann hier runtergeladen werden:
MagicTour Programm

Das Programm hat unterste Priorität unter Windows. Es kann gestoppt werden,

aber dann ist die aktuelle Berechnung des jeweiligen Suchbereichs verloren.

Das Programm ist kompliziert, der Quellcode lang und schwer optimiert
Hier ist ein C-PROGRAMM von Fei Lu mit Erklärungen:
knight.c

Wir interessieren uns auch für allgemeine Hamilton-Pfad-Programme, und werden die Suche evtl. auf andere aehnliche Probleme ausdehnen.

27. April 2003: Erste Version der Web-Site.
25. Mai 2003 : Zweite Version der Web-Site
( Verbesserung-Vorschläge sind willkommen)
19. Juni 2003
: Dritte Version der Web-Seite
16. Juni 2003: Berechnung der Suchbereiche hat begonnen
18. Juni 2003: erster Erfolg: nach 2 Tagen Laufzeit, hat Hugues Mackay
die erste neue magische Springertour gefunden !

6 weitere wurde neue MKTs wurden im Rahmen des Projektes gefunden.
Hier sind der 7 neuen MKTs:


8- 59 30 35 24 57 22 15 18
7- 36 25 58 29 16 19 56 21
6- 31 60 27 34 23 54 17 14
5- 26 37 32 49 28 13 20 55
4- 39 04 61 12 33 48 53 10
3- 62 01 38 07 50 11 44 47
2- 05 40 03 64 45 42 09 52
1- 02 63 06 41 08 51 46 43
a b c d e f g h
Mackay/Meyrignac/Stertenbrink
2003/06/18 b3-d2

8- 11 46 51 40 09 38 31 34
7- 52 41 10 45 32 35 08 37
6- 47 12 43 50 39 06 33 30
5- 42 53 48 01 44 29 36 07
4- 55 20 13 28 49 64 05 26
3- 14 17 54 23 02 27 60 63
2- 21 56 19 16 61 58 25 04
1- 18 15 22 57 24 03 62 59
a b c d e f g h
Jelliss
2003/06/19 d5-f4

8- 34 51 32 13 62 37 20 11
7- 15 30 35 50 19 12 61 38
6- 52 33 14 31 36 63 10 21
5- 29 16 49 44 05 18 39 60
4- 48 53 04 17 64 43 22 09
3- 01 28 45 56 25 06 59 40
2- 54 47 26 03 42 57 08 23
1- 27 02 55 46 07 24 41 58
a b c d e f g h
Mackay/Meyrignac/Stertenbrink
2003/06/21 a3-e4

8- 18 39 64 09 58 41 24 07
7- 63 10 17 40 23 08 57 42
6- 38 19 36 61 16 59 06 25
5- 11 62 13 20 33 22 43 56
4- 50 37 32 35 60 15 26 05
3- 31 12 49 14 21 34 55 44
2- 48 51 02 29 46 53 04 27
1- 01 30 47 52 03 28 45 54
a b c d e f g h
Mackay/Meyrignac/Stertenbrink
2003/06/24 a1-c8

8- 54 13 50 23 10 19 44 47
7- 51 24 53 12 45 48 09 18
6- 14 55 22 49 20 11 46 43
5- 25 52 15 64 37 42 17 08
4- 56 01 26 21 16 63 36 41
3- 27 30 59 04 33 38 07 62
2- 02 57 32 29 60 05 40 35
1- 31 28 03 58 39 34 61 06
a b c d e f g h
Mackay/Meyrignac/Stertenbrink
2003/07/01 b4-d5

8- 54 45 18 23 42 51 12 15
7- 19 24 53 44 13 16 41 50
6- 46 55 22 17 52 43 14 11
5- 25 20 47 64 05 10 49 40
4- 56 01 26 21 48 63 36 09
3- 27 30 59 04 33 06 39 62
2- 02 57 32 29 60 37 08 35
1- 31 28 03 58 07 34 61 38
a b c d e f g h
Mackay/Meyrignac/Stertenbrink
2003/07/01 b4-d5

8- 34 23 42 47 18 31 38 27
7- 43 48 33 24 37 28 17 30
6- 22 35 46 41 32 19 26 39
5- 49 44 21 36 25 40 29 16
4- 06 53 04 45 20 61 12 59
3- 01 50 07 56 09 58 15 64
2- 54 05 52 03 62 13 60 11
1- 51 02 55 08 57 10 63 14
a b c d e f g h
Mackay/Meyrignac/Stertenbrink
2003/08/01 a3-h3

Hier sind die 136 Suchbereiche, die durchforstet wurden:

Von-zu MKTs bekannt vor dem Juni 2003 Symmetrie-Klassen Neue MKTs Neue Symmetrie-Klassen Berechnet von
a1-a2 0 0 0 0 Mackay
a1-a4 0 0 0 0 Mackay
a1-a6 0 0 0 0 Mackay
a1-a8 0 0 0 0 Mackay
a1-b3 0 0 0 0 Mackay
a1-b5 0 0 0 0 Mackay
a1-b7 0 0 0 0 Mackay
a1-c4 0 0 0 0 Mackay
a1-c6 0 0 0 0 Mackay
a1-c8 8 8 1 1 Mackay
a1-d5 0 0 0 0 Mackay
a1-d7 0 0 0 0 Mackay
a1-e6 0 0 0 0 Mackay
a1-e8 0 0 0 0 Mackay
a1-f7 0 0 0 0 Mackay
a1-g8 0 0 0 0 Mackay
a2-a3 0 0 0 0 Thomasson, Mackay
a2-a5 0 0 0 0 Thomasson, Mackay
a2-a7 0 0 0 0 Thomasson
a2-b2 0 0 0 0 Thomasson
a2-b4 0 0 0 0 Thomasson
a2-b6 0 0 0 0 NovaTec
a2-b8 0 0 0 0 NovaTec
a2-c1 0 0 0 0 NovaTec
a2-c3 0 0 0 0 Tyman
a2-c5 0 0 0 0 Tyman
a2-c7 0 0 0 0 Tyman, NovaTec
a2-d2 0 0 0 0 Schauer
a2-d4 0 0 0 0 Schauer
a2-d6 0 0 0 0 NovaTec
a2-d8 0 0 0 0 NovaTec
a2-e1 0 0 0 0 NovaTec
a2-e3 0 0 0 0 NovaTec
a2-e5 0 0 0 0 NovaTec
a2-e7 0 0 0 0 Marlow
a2-f2 0 0 0 0 Marlow
a2-f4 0 0 0 0 NovaTec
a2-f6 0 0 0 0 NovaTec,
a2-f8 0 0 0 0 NovaTec,
a2-g3 0 0 0 0 Euler
a2-g5 0 0 0 0 Rottmann
a2-g7 0 0 0 0 GrafZahl
a2-h2 0 0 0 0 Rottmann
a2-h4 7 7 0 0 Mackay
a2-h6 0 0 0 0 Euler, Schauer
a3-a4 1 1 0 0 Mackay
a3-a6 0 0 0 0 Mackay
a3-b3 0 0 0 0 Mackay
a3-b5 8 8 0 0 Mackay
a3-b7 0 0 0 0 Mackay
a3-c2 1 1 0 0 Mackay
a3-c4 0 0 0 0 Mackay
a3-c6 3 3 0 0 Mackay
a3-c8 1 1 0 0 Mackay
a3-d1 0 0 0 0 Mackay
a3-d3 0 0 0 0 Mackay
a3-d5 4 4 0 0 Mackay
a3-d7 0 0 0 0 Mackay
a3-e2 0 0 0 0 Mackay
a3-e4 1 1 1 1 Mackay
a3-e6 0 0 0 0 GrafZahl, Mackay
a3-e8 0 0 0 0 Mackay, GrafZahl
a3-f3 0 0 0 0 Mackay, GrafZahl
a3-f5 0 0 0 0 Mackay
a3-f7 0 0 0 0 Euler
a3-g2 1 1 0 0 Mackay
a3-g4 0 0 0 0 Euler
a3-g6 0 0 0 0 Schauer
a3-h3 0 0 2 1 Mackay
a3-h5 4 4 0 0 Mackay
a4-a5 6 3 0 0 Mackay
a4-b2 0 0 0 0 Schauer, Mackay
a4-b4 0 0 0 0 Stertenbrink
a4-b6 19 19 0 0 Mackay
a4-c3 0 0 0 0 Schauer, Mackay
a4-c5 3 3 0 0 Mackay
a4-c7 0 0 0 0 Mackay
a4-d2 2 2 0 0 Mackay
a4-d4 3 3 0 0 Mackay
a4-d6 4 4 0 0 Mackay
a4-d8 1 1 0 0 Mackay
a4-e3 1 1 0 0 Mackay
a4-e5 3 3 0 0 Mackay
a4-e7 5 5 0 0 Mackay
a4-f2 0 0 0 0 Mackay
a4-f4 0 0 0 0 Mackay
a4-f6 1 1 0 0 Mackay
a4-g3 0 0 0 0 Mackay
a4-g5 0 0 0 0 Mackay
a4-g7 0 0 0 0 Mackay
a4-h4 0 0 0 0 Mackay
b2-b3 0 0 0 0 Mackay
b2-b5 0 0 0 0 Mackay
b2-b7 2 1 0 0 Mackay
b2-c4 2 2 0 0 Mackay
b2-c6 0 0 0 0 Mackay
b2-d5 0 0 0 0 Mackay
b2-d7 0 0 0 0 Mackay
b2-e6 1 1 0 0 Mackay
b2-f7 0 0 0 0 Mackay
b3-b4 2 2 0 0 Mackay
b3-b6 6 3 0 0 Mackay
b3-c3 1 1 0 0 Mackay
b3-c5 6 6 0 0 Mackay
b3-c7 0 0 0 0 Mackay
b3-d2 4 4 1 1 Mackay
b3-d4 8 8 0 0 Mackay
b3-d6 3 3 0 0 Mackay
b3-e3 0 0 0 0 Mackay
b3-e5 0 0 0 0 Mackay
b3-e7 0 0 0 0 Mackay
b3-f4 0 0 0 0 Mackay
b3-f6 0 0 0 0 Mackay
b3-g3 0 0 0 0 Mackay
b3-g5 0 0 0 0 Mackay
b4-b5 0 0 0 0 Mackay
b4-c4 0 0 0 0 Mackay
b4-c6 0 0 0 0 Mackay
b4-d3 0 0 0 0 Mackay
b4-d5 0 0 2 2 Mackay
b4-d7 0 0 0 0 Mackay
b4-e4 1 1 0 0 Mackay
b4-e6 0 0 0 0 Mackay
b4-f3 0 0 0 0 Mackay
b4-f5 0 0 0 0 Mackay
b4-g4 12 6 0 0 Mackay
c3-c4 2 2 0 0 Mackay
c3-c6 0 0 0 0 Mackay
c3-d5 6 6 0 0 Mackay
c3-e6 1 1 0 0 Mackay
c4-c5 0 0 0 0 Mackay
c4-d4 0 0 0 0 Mackay
c4-d6 2 2 0 0 Mackay
c4-e5 0 0 1 1 Mackay
c4-f4 0 0 0 0 Mackay
d4-d5 0 0 0 0 Mackay
Summe: 146 133 8 7

Dank an
Hugues Mackay, Dan Thomasson, Guenter Stertenbrink, Tom Marlow, NovaTec,
Hendrik Tyman, Werner Schauer, Thilo Rottmann, GrafZahl, Euler
die Bereiche berechnet haben und damit halfen, das Projekt zu beenden.
Besonderen Dank an Hugues Mackay, der alleine mehr als 100 Bereiche berechnet hat!
Und natuerlich Dank an, JC Meyrignac fuer's Optimieren des Programms, und fuer die Hilfe bei dieser Webseite

Am 5.August 2003 waren alle 136 Bereiche geprüft nach
5305279.08 Sekunden = 61.40 Tagen Rechenzeit
und 11_945038 CPU-Gigazyklen (entspricht 138.25 Tagen bei 1GHz)
52_280100_180652 Springerzuege waren gemacht worden, das macht 228.5 CPU-Zyklen pro Zug (=Knoten im Suchbaum)
7.0e10 bis 3.1e12 Knoten pro Suchbereich. Durchschnitt 3.8e11, Standardabweichung 5.4e11


Knotenzahlen fuer die 136 Suchbereiche : nodecounts
graphische Darstellung der Komplexitaet der einzelnen Suchbereiche: NODES2.GIF
Computer-lesbare Liste aller MKTs : (674KB) mkts.txt
graphische Darstellung der Touren: MKTS108B.GIF
griechisch lateinische Torus Touren: latin torus-leaper-tours
Unser Projekt zum Berechnen aller geschlossenen 8*8 Touren: computing knight tours

Hier ist der Mathworld Artikel ueber das Projekt: mathworld article

und hier ein Artikel mit Diskussion auf Deutsch: Heise Artikel


Andere Seiten ueber Springertouren in Deutsch:
A.Conrad
[ wie man eine Tour findet fuer grosse Bretter ]
Dan Thomasson
[ andere Methode, graphisch untermalt ]
PDF-paper zum Abzaehlen von Springertouren
[ Vergleich von Springertour-Abzaehl-Algorithmen ]

in Englisch: Jelliss, knight tour notes
[ die ultimative Seite ueber Springertouren. Sehr ausfuehrlich ]
Velucchi, knight-links
[ beste Sammlung von Internet-Links zum Thema Springertouren ]
Friedel,F.:"The Knight's Tour."
[ unterhaltsames und kurioses ueber Springertouren ]
mathworld-MagicTour
[ introduction,definitions,examples,links ]
Achtung , E.Weisstein von Mathworld benutzt andere Definitionen als wir und Jelliss:
"magic tour" (Mathworld) = "diagonal magic tour" (Jelliss)
"semimagic tour" (Mathworld) = "magic tour" (Jelliss)
"semimagic tour" (Jelliss) = [nur die Reihen addieren zur magischen Konstante]


Deutsche Version: 13.Januar 2004 © 2003 Guenter Stertenbrink mailto:sterten@aol.com
Visitor numberVisitor since May 1st 2003.
[return to top]