Ich beschäftige mich gerade mit der Variante auf dem Bild und mir stellt
sich die Frage wieviele unterschiedliche Lösungen es gibt ohne die, die
durch Symmetrie (Spiegelung/Rotation) entstehen.
Ich hab mir ein Programm geschrieben, welches allerdings auf einer
Annahme basiert die ich noch nicht verifizieren kann und dieses spuckt
nach knapp 2 Minuten als Antwort 24 aus. Nimmt man symmetrische dazu
sind es ca. 80 Billiarden.
Kann die 24 jemand (- zu Yalu rüberschiel - ;) ) veri-/falsifizieren?
Markus B. schrieb:> Muss man dein Bild in Zusammenhang mit Solitär verstehen? Oder gehts da> nicht um das Windows Spiel?http://de.wikipedia.org/wiki/Solit%C3%A4r_%28Brettspiel%29Vlad Tepesch schrieb:> Ich kenn das Spiel unter dem Namen Solo-Halma.> rein vom Gefühl her kommt mir 24 aber arg wenig vor.
Dachte ich auch erst, beim französischen Brett sinds aber je nach
Startposition aber auch nur 280. Fürs englische mit obiger
Startkonfiguration habe ich jedoch keinen Wert im Netz gefunden und
deswegen habe ich selbst Hand angelegt.
Hallo,
in der c't Ausgabe 7/1999 gab es den Artikel "Spielverderber - Solitaire
mit dem Computer lösen". Dieser Artikel behandelt die von Dir angegebene
Variante. Kennst Du diesen Artikel?
Mit freundlichen Grüßen
Guido
D. I. schrieb:> Zu gutes Wetter oder zu schwierig?
Ersteres, wenn man "gutes" durch "heißes" ersetzt. Weder Computer noch
Hirn sind für Temperaturen über 30 °C optimiert :)
Ich hätte eigentlich gedacht, das Spiel sei auf Grund seiner Popularität
schon komplett analysiert. So findet man bspw. Informationen über die
Anzahl der Spielstellungen insgesamt oder nach dem n-ten Zug:
http://www.durangobill.com/Peg33.html
Über die Anzahl der möglichen Lösungswege habe ich auf die Schnelle auch
nichts gefunden. Man kann jetzt entweder weiter googeln, ein
Scuhprogramm schreiben oder eines der im Web verfügbaren Programme so
anpassen, dass es die gewünschte Information ausgibt. Der obige Link
enthält am Ende zwei C-Programme (eins mit Tiefe- und eins mit
Breitensuche). Vielleicht stellen diese eine brauchbare Basis dar.
Yalu X. schrieb:> D. I. schrieb:>> Zu gutes Wetter oder zu schwierig?>> Ersteres, wenn man "gutes" durch "heißes" ersetzt. Weder Computer noch> Hirn sind für Temperaturen über 30 °C optimiert :)
In der Tat.
>> Ich hätte eigentlich gedacht, das Spiel sei auf Grund seiner Popularität> schon komplett analysiert. So findet man bspw. Informationen über die> Anzahl der Spielstellungen insgesamt oder nach dem n-ten Zug:>> http://www.durangobill.com/Peg33.html
Die Seite habe ich auch gefunden, mit der konnte ich immerhin einige
Dinge verifizieren.
>> Über die Anzahl der möglichen Lösungswege habe ich auf die Schnelle auch> nichts gefunden. Man kann jetzt entweder weiter googeln, ein
Mit Google bin ich mittlerweile am Ende.
> Scuhprogramm schreiben oder eines der im Web verfügbaren Programme so> anpassen, dass es die gewünschte Information ausgibt. Der obige Link> enthält am Ende zwei C-Programme (eins mit Tiefe- und eins mit> Breitensuche). Vielleicht stellen diese eine brauchbare Basis dar.
Die berechnen eben nur die Gesamtzahl aller Lösungen, was ja auch
mithilfe von DP sehr einfach ist, da wird noch keine Symmetrie
berücksichtigt.
Um genau zu sein interessiert mich nicht nur die Anzahl, sondern auch
die tatsächlichen Wege und das ist ziemlich knifflig. Breitensuche und
Wege merken scheidet aus, explodiert der Speicher. Also bleibt nur
Tiefensuche und sobald man einen Weg gefunden hat kann man ihn direkt
ausgeben. Tiefensuche und Symmetrieerkennung gemeinsam scheint nicht
ohne.
Edit: Wie ich gerade sehe ist der Lauf meines überarbeiteten Programms
von dem ich mir relativ sicher bin, dass es stimmt, fertig nach 10
Minuten Rechenzeit. Es sind scheinbar wirklich 24 Wege.
D. I. schrieb:> als Antwort 24 aus. Nimmt man symmetrische dazu> sind es ca. 80 Billiarden.
Ist die Symmetriegruppe da nicht etwas zu gross? Sollten nicht die
Anzahl der Lösungen sich nur so um den Faktor 8 vergrößern?
dumdi dum schrieb:> D. I. schrieb:>> als Antwort 24 aus. Nimmt man symmetrische dazu>> sind es ca. 80 Billiarden.>> Ist die Symmetriegruppe da nicht etwas zu gross? Sollten nicht die> Anzahl der Lösungen sich nur so um den Faktor 8 vergrößern?
Dachte ich auch erst, aber wie gesagt beim französischen Brett ist es
ähnlich.
Jetzt will ich meine Berechnung noch etwas beschleunigen.
Ich glaube, ich habe – ähnlich wie "dumdi dum" – missverstanden, was du
unter symmetrischen Lösungen verstehst. Wenn man sich alle 31 Züge einer
Lösung aufmalt, kann diese Grafik in vier unterschiedlichen
Orientierungen ausgerichtet und optional gespiegelt werden, so dass die
Gesamtzahl der Lösungen maximal um den Faktor 8 größer als die durch
Symmetrien reduzierte Anzahl ist.
Kannst du mal eine Definition dafür geben, wann genau zwei Lösung als
gleich gelten?
Yalu X. schrieb:> Kannst du mal eine Definition dafür geben, wann genau zwei Lösung als> gleich gelten?
Im Original der Aufgabenstellung steht lediglich man soll alle
unterschiedlichen Wege ausgeben, alle radiär/spiegelsymmetrischen Wege
zählen als ein Weg.
Ich verstehe das folgendermaßen:
Zwei Lösungen sind gleich wenn die Wege die zu den Lösungen führen durch
Spiegelung / Drehung ineinander übergeführt werden können.
Nimmt man z.b. das Feld so:
.. .. 01 02 03 .. ..
.. .. 04 05 06 .. ..
07 08 09 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
.. .. 28 29 30 .. ..
.. .. 31 32 33 .. ..
Dann wären für meine Begriffe diese Zugketten identisch:
5->17, 24->10, 22->24
5->17, 24->10, 26->24
Ich versuche nochmal die Quelle zum französischen Brett mit 280 Lösungen
zu finden, aber die spart sich auch die Definition von unterschiedlich
aus.
Edit: Hab noch nen Bug bei mir gefunden, noch läuft das Programm...
Darüberhinaus kann man ja schonmal folgendes sagen:
Nach dem 1. Zug kann man schonmal 75% killen, weil es egal ist wie man
anfängt.
Nach dem 2. Zug ist nochmal 50% weg. wären dann schonmal 82,5% weg.
Ist da schon Ende?
Ich glaube ich muss mal ne Clarification des Aufgabenstellers
einfordern...
Also ich vermute die Aufgabe macht nur Sinn, wenn man das Vertauschen
zweier unabhängiger Züge als gleich behandelt.
Gemeint ist: Also wenn man 2 Züge innerhalb einer Zugkette tauscht und
dann immer noch auf dieselbe Konfiguration kommt, diese beiden Ketten
als gleich zu behandeln sind.
D. I. schrieb:> Ich verstehe das folgendermaßen:>> Zwei Lösungen sind gleich wenn die Wege die zu den Lösungen führen durch> Spiegelung / Drehung ineinander übergeführt werden können.>> Nimmt man z.b. das Feld so:>> .. .. 01 02 03 .. ..> .. .. 04 05 06 .. ..> 07 08 09 10 11 12 13> 14 15 16 17 18 19 20> 21 22 23 24 25 26 27> .. .. 28 29 30 .. ..> .. .. 31 32 33 .. ..>> Dann wären für meine Begriffe diese Zugketten identisch:>> 5->17, 24->10, 22->24> 5->17, 24->10, 26->24
Das wäre auch meine Interpretation von "identisch". Man könnte die
beiden Zugfolgen auch als "kongruent" bezeichnen.
Da bei dem Spiel aber nur 4 Rotationswinkel möglich sind, ist die Anzahl
der zu einer Kongruenzklasse gehörenden Lösungen maximal 8. In deinem
Beispiel lauten die 8 kongruenten Lösungen
1
05->17, 24->10, 22->24
2
05->17, 24->10, 26->24
3
15->17, 18->16, 30->18
4
15->17, 18->16, 06->18
5
29->17, 10->24, 12->10
6
29->17, 10->24, 08->10
7
19->17, 16->18, 04->16
8
19->17, 16->18, 28->16
D. I. schrieb:> Ich glaube ich muss mal ne Clarification des Aufgabenstellers> einfordern...
Woher stammt die Aufgabe denn?
D. I. schrieb:> Also ich vermute die Aufgabe macht nur Sinn, wenn man das Vertauschen> zweier unabhängiger Züge als gleich behandelt.
Ja, solche Zugfolgen könnte man ebenfalls als gleich ansehen.
Auch nicht kongruente Zugfolgen, die sich aber aus kongruenten
Teilfolgen zusammensetzen, würde ich als gleich betrachten.
Aber welche "Gleichheitskriterien" hast du denn in deinem Programm
implementiert, um auf die Anzahl voin 24 zu kommen? 24 ist ja schon eine
sehr übersichtliche Anzahl. Wenn man zeigen kann, dass sich die
restlichen 80 Billiarden auf triviale Weise aus diesen 24 ableiten
lassen, ist das doch ein Superergebnis.
Yalu X. schrieb:> Aber welche "Gleichheitskriterien" hast du denn in deinem Programm> implementiert, um auf die Anzahl voin 24 zu kommen? 24 ist ja schon eine> sehr übersichtliche Anzahl. Wenn man zeigen kann, dass sich die> restlichen 80 Billiarden auf triviale Weise aus diesen 24 ableiten> lassen, ist das doch ein Superergebnis.
In dem ich einfach einen fiesen Bug drin hatte, der dafür gesorgt hat
unerlaubt viel abzuschneiden ;) Also, nicht der Rede wert.
Ich sitze gerade dran Zug vertauschen zu implementieren. Im Moment habe
ich kein Programm welches in absehbarer Zeit terminiert :/
Aber für heut ists dann erstmal gut, außerdem gehts in 3 Tagen erstmal
nach Ungarn und dann schau mer mal weiter.
Yalu X. schrieb:> D. I. schrieb:>> Ich glaube ich muss mal ne Clarification des Aufgabenstellers>> einfordern...>> Woher stammt die Aufgabe denn?
Aus der Firma in der ich aktuell arbeite, da gibts zum Sommerurlaub
immer so eine "Challenge" für den schnellsten Algo zu einem Problem.
Allerdings zweifel ich im Moment daran, dass die Aufgabensteller eine
Musterlösung gemacht haben und naja als ICPC'ler a.D. bin ich präzisiere
Aufgabenstellungen gewöhnt :)
Ich denke ich bringe mal die Schokoladenaufgabe ein :x
Die Aufgabensteller haben sich nochmal ans Herz gefasst und die
Aufgabenstellung dahingehend angepasst, dass man keine Wege mehr ausgibt
sondern nur noch die Anzahl aller möglichen Gewinnwege möglichst
effizient berechnen soll (~8.1 * 10^16).
Da terminiert mein Algo auch zu vertretbaren Zeiten.
PegSolitaire_1000.gif
(5,9 KB)
