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?
Angehängte Dateien:
-
PegSolitaire_1000.gif
5,9 KB
Muss man dein Bild in Zusammenhang mit Solitär verstehen? Oder gehts da nicht um das Windows Spiel?
Ich kenn das Spiel unter dem Namen Solo-Halma. rein vom Gefühl her kommt mir 24 aber arg wenig vor.
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%29 Vlad 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
Guido C. schrieb: > Kennst Du diesen Artikel? Nein, danke für den Tipp, mal sehen ob er die 2,50€ wert ist...
Der Artikel ist tatsächlich nicht schlecht, er beantwortet zwar meine Frage nicht, liefert aber wertvollen Input die meine Berechnung beschleunigt.
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...
Hier steht das mit den 280 Möglichkeiten. http://de.wikipedia.org/wiki/Solit%C3%A4r_%28Brettspiel%29#Computerprogramme
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.
Thread beobachten
Seitenaufteilung abschalten
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.