Algorithmus

Damen

Hier verwenden wir ein rekursives Back Tracking Verfahren:
Das Schachbrett hat n Zeilen und n Spalten.
Wir setzen die n Damen nacheinander nach folgender Weise:

Und beginnen mit Spalte 0 und lassen die Dame auf die niederste Spalte 'absinken'.
Ist sie bedroht, 'steigt' sie in Ihrer Spalte auf.
Kann sie gesetzt werden, kommt die nächste Dame in der nächsten Spalte dran.
Auch sie startet 'ganz unten' und 'steigt' auf bis sie nicht mehr bedroht wird.
Gelingt dies nicht, wird die vorherige Dame weiter 'aufsteigen'.

Dies wiederholt sich, bis die erste Dame nicht mehr weiter 'aufsteigen' kann.

Optimierung:

Spalte 0 Hälfte
Ist diese Lösung für das n-Damen Problem gefunden mit der Notation [1,3,0,2],
so kann die gespiegelte Lösung mit der Notation [2,0,3,1] einfach errechnet werden:

Für alle y Werte in den Spalten gilt: y'=n-y-1.
Daraus folgt, dass wir die erste Spalte nur bis zur Hälfte füllen und die andere Hälfte berechnen.
Dies beschleunigt die Suche um etwa den Faktor 2.
unique
Sollen nur eindeutige Lösungen generiert werden, so unterbleibt die Berechnung der Spiegel Lösung.
weitere abgeleitete Lösungen
Ist eine Lösung gefunden, können daraus max. 7 weitere Lösungen durch Drehungen und Spiegelungen entstehen. Allerdings zeigt sich, dass dies zu keiner Optimierung führt, da man keine Veringerung der Startpositionen machen kann.

Springer

Hier werden folgende Strukturen zur Verwaltung der Züge verwendet:

n
Die Position auf dem Brett
no
die ZugNummer
LinkCnt[n]
Die Anzahl der Links, ausgehend von der Position n
next[n]
Die nächsten (max 8) Positionen.
Werden Positionen besetzt ändert sich die hier Reihenfolge, damit die freien stets von vorne beginnen.
LinkCntNow[n]
Der aktuelle Stand der Links während der Zugfolge

Optimierung:

Der Springer wechselt mit jedem Zug die Farbe des Schachbretts. Dies hat Auswirkungen für den Fall:

Comeback
Sollen nur geschlossende Zugfolgen (der letzte Springerzug könnte den ersten wieder erreichen) gefunden werden dann gilt:
Es braucht gleich viele schwarze wie weiße Felder.
Dies ist nur bei geradzahligen n gegeben.
Bsp.:n=4: und n=3: .

Damit gibt es keine Lösung für ungerade n mit der -comeback Option.
ohne Comeback mit n=ungerade
Ein Start ist nur auf ungeraden Feldern möglich! Also den Feldern welche von der Färbung häufiger vorkommen.
Hier am Bsp mit n=5 die möglichen Start Positionen:

Weitere hilfreiche Masnahmen:

Spiegelung & Rotation
Streng genommen müssen nur wenige Startpositionen betrachtet werden:
Alle anderen Startpositionen und Felder können dann berechnet werden!
ComeBack Spiegelung
Mit dieser Option starten wir in einer Ecke (Position 0) und haben nur 2 Möglichkeiten. Es reicht nun, die eine zu verfolgen, da die andere als Spiegelung an der Diagonale generiert werden kann. Allerdings stellt sich heraus, dass dies schon passiert.
Sackgasse erkennen
Wird eine Position besetzt, so ändert sich die Anzahl der freien Links.
Gibt es nur noch 1 Link im Umfeld der neu zu bestzenden Position so ist dies eine Sackgasse!

Bsp:

1	 .	 .	 .	3	 .	
 .	 .	2	 .	 .	 .	
 .	 .	 .	 .	 .	4	
 .	 .	8	 .	 .	 .	
7	 .	 .	 .	5	 .	
 .	 .	6	 .	 .	 .	

Setze
no =  9
n  = 31
next[n] 18 20 27

LinkCntNow [31] 2   .. aber next[n]== 20 tausch mit 27
LinkCntNow [18] 3
LinkCntNow [20] 5
LinkCntNow [27] 5

Magisches Quadrat

Die Quersumme bei einem magischen Quadrat hängt von der Kantenlänge n des Quadrates ab. Dabei gibt es diese Relationen:

Kantenlänge	Quersumme
3	15
4	34
5	65
6	111
7	175
n	(1+n²)/ 2 * n

Kennt man ein magisches Quadrat mit der Kantenlänge n, so kann diese erweitert werden auf n' = n+2.

Dabei entstehen 4(n'-1) neue Felder.
Die eine Hälfte im unteren Zahlenbereich von 1 bis 2(n+1).
Die obere Hälfte von n'² - 2(n'-1)-1 bis n'².
Das innere magische Quadrat erfährt eine Anhebung der Felder mit dem Faktor Shift = 2(n+1).

Nachfolgend eine Tabelle mit Werten:

Kantenlänge	Kantenlänge erweitert	untere Randfelder	inneres Quadrat	obere Randfelder
1	3	1..4	5..5	6..9
2	4	1..6	7..10	11..16
3	5	1..8	9..17	18..25
4	6	1..10	11..26	27..36
5	7	1..12	13..37	38..49
6	8	1..14	15..50	51..64
7	9	1..16	17..65	66..81
n	n+2	1 .. 2(n+1)	1+2(n+1) .. n²+2(n+1)	n²+2(n+1)+1 .. n²

Wichtig:Die gegenüberliegende Randfelder erhalten stets die gleiche Summe.

23       7       6       4      25
21      10      15      14       5			Untere Randfelder:  '1' ...  '8'
18      17      13       9       8			Inneres Quadrat:    '9' ... '17'
 2      12      11      16      24			Obere Randfelder:  '18' ... '25'
 1      19      20      22       3

Rolf LANG - Remsstr. 39 - 71384 Weinstadt | 02:27:04 up 16:11, 0 user, load average: 0.19, 0.10, 0.04