Damenproblem für Embedded Systems

[StudentZHW]

Hallo zusammen

Das Damenproblem kennen wohl die meisten von euch und Lösungsansätze gibt es ja genügend. Ich habe eine Variante mittels backtracking programmiert und gebe die Lösungen jeweils auf der Console aus.

1) d8 g7 c6 h5 b4 e3 a2 f1
2) ...

Nun möchte ich aber, dass zuerst die Anzahl Lösungen ausgegeben wird:
bsp:
Brettgrösse: 8x8
Für diese Brettgrösse gibt es 92 Lösungen

...
...


und erst dann sollen die Lösungsvarianten angezeigt werden.

Das Problem besteht nun darin, dass ich das Program für ein Embedded System schreibe und dass ich dort auf den Speicher und CPU achten muss. Kann mir jemand sagen, wie ich die gewünschte Ausgabe erzeugen kann?

Eine weitere Frage: Hat jemand eine gute Variante um die eindeutigen Lösungen zu bestimmen?

Vielen Dank für eure Hilfe!

Daniel

 

[deepthroat]

Hallo zusammen

Das Damenproblem kennen wohl die meisten von euch und Lösungsansätze gibt es ja genügend. Ich habe eine Variante mittels backtracking programmiert und gebe die Lösungen jeweils auf der Console aus.

1) d8 g7 c6 h5 b4 e3 a2 f1
2) ...

Nun möchte ich aber, dass zuerst die Anzahl Lösungen ausgegeben wird:
bsp:
Brettgrösse: 8x8
Für diese Brettgrösse gibt es 92 Lösungen

...
...


und erst dann sollen die Lösungsvarianten angezeigt werden.

Das Problem besteht nun darin, dass ich das Program für ein Embedded System schreibe und dass ich dort auf den Speicher und CPU achten muss. Kann mir jemand sagen, wie ich die gewünschte Ausgabe erzeugen kann?

Möglichkeiten:

• alle Lösungen berechnen und zählen, die Lösungen ausgegben und dann nochmal berechnen.
• alle Lösungen berechnen und geschickt speichern, dann wie gewünscht ausgeben
• Liste der Lösungszahlen von http://de.wikipedia.org/wiki/Damenp...ungen_bis_zur_Brettgr.C3.B6.C3.9Fe_25.C3.9725 im Code vorhalten und je nach Brettgröße ausgeben, dann Lösungen berechnen und ausgeben.

Welche Restriktionen gibt es denn? Bis zu welcher Spielfeldgröße soll das berechnet werden?

Eine weitere Frage: Hat jemand eine gute Variante um die eindeutigen Lösungen zu bestimmen?

nicht eindeutige Lösungen entstehen durch Spiegeln an verschiedenen Achsen des Schachbrettes. Ad hoc weiß ich allerdings nicht wie man nur die eindeutigen Lösungen berechnen sollte.

Gruß

 

[Mizi Mace]

Einen wunderschönen guten Morgen,

hier hast du mal einen Link:

Jeff Somers's N Queens Solution

Der erste Link führt dich zur Lösung von Jeff Somers. Diese ist die mir bis jetzt schnellste bekannte Lösung. Er geht auch auf die Permutation von gefundenen Lösungen ein. Inwieweit er dies im Programm umgesetzt hat, weiß ich nicht. Ich habe mir den Code nie angeschaut. Allerdings ist dieser nun schon fast 7 Jahre alt. Vielleicht gibt es schon etwas schnelleres.

Und noch einen kleinen Tipp zur Mathematik: Schau dir mal Permutationen an. Die uneindeutigen Lösungen sind nur solche. Wenn du dir das mal genau für dein Problem anschaust, kannst du eventuell eine Regel ableiten.

Zur Abspeicherung der Lösungen: Zur Veranschaulichung evolutionärer Algorithmen habe ich als einführendes Beispiel das N-Damen-Porblem gewählt. Dort habe ich die Lösungen als eindimensionales Array mit N Feldern abgespeichert. Die Felder stellen somit die Spalten dar. In die Felder selbst wird dann die Nummer der Zeile geschrieben.

Gruss
Mizi

 

[deepthroat]

Der erste Link führt dich zur Lösung von Jeff Somers. Diese ist die mir bis jetzt schnellste bekannte Lösung. Er geht auch auf die Permutation von gefundenen Lösungen ein.

Ich kann keine Stelle auf der Seite entdecken wo von Permutationen geredet wird.

Und noch einen kleinen Tipp zur Mathematik: Schau dir mal Permutationen an. Die uneindeutigen Lösungen sind nur solche.

Alle Lösungen können als Permutationen von n Zahlen k für 0 <= k < n dargestellt werden. Das hat mit eindeutigen Lösungen nichts zu tun.

Evtl. sollte man sagen was man unter eindeutigen Lösungen versteht. Im allgemeinen sind eindeutige Lösungen solche, die nicht durch Drehung oder Spiegelung einer anderen Lösung entstehen. D.h. für ein 4x4 Brett gibt es genau 1 eindeutige Lösung (siehe auch Wikipedia) - und nicht wie Jeff Somers erklärt 2.

Gruß

 

[Mizi Mace]

Einen wunderschönen guten Tag,

Ich kann keine Stelle auf der Seite entdecken wo von Permutationen geredet wird.

Stimmt, da hatte ich das wohl falsch in Erinnerung. John Somers hat einen Backtracking Algorithmus entwickelt. Der Algorithmus ist vielleicht trotzdem interessant für das Problem.

Alle Lösungen können als Permutationen von n Zahlen k für 0 <= k < n dargestellt werden. Das hat mit eindeutigen Lösungen nichts zu tun.

Das ist korrekt. Jede gefundene Lösung muss eine Permutation sein. Die Gesamtheit aller Permuationen sind die uneindeutigen Lösungen inklusive der eindeutigen Lösungen und die "Nichtlösungen".

Hat man nun eine Lösung gefunden, kann diese durch Spiegelung und Rotation in weitere Lösungen umgeformt werden. Allerdings habe ich mich hier etwas in der Kombinatorik vertan. Diese Lösungen stellen Kombination (nicht Permutationen) der einen gefundenen Lösung dar. Allerdings sind hier dann die Spiegelung und Rotation die kombinierten Eigenschaften.

Evtl. sollte man sagen was man unter eindeutigen Lösungen versteht. Im allgemeinen sind eindeutige Lösungen solche, die nicht durch Drehung oder Spiegelung einer anderen Lösung entstehen. D.h. für ein 4x4 Brett gibt es genau 1 eindeutige Lösung (siehe auch Wikipedia) - und nicht wie Jeff Somers erklärt 2.

Jeff Somers schreibt nicht, dass es zwei eindeutige Lösungen gibt. Er bezieht sich hierbei wohl auf die Gesamtheit der uneindeutigen Lösungen. Wie du oben festgestellt hast, geht er weder auf den Unterschied noch selbst auf eindeutige und uneindeutige Lösungen ein.

Gruss
Mizi