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.
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