Erstellen Sie einen Freecell-Solver mit wenigen Zügen

54

Im Spiel Freecell musst du vier Grundpfähle in Farbe von Ass bis König auf einem Grundriss bauen, auf dem du in wechselnden Farben abwärts baust. Es kann jedoch immer nur eine Karte gleichzeitig erstellt werden. Daher erhalten Sie vier "freie Zellen", die jeweils eine Karte enthalten können, mit deren Hilfe Sie ganze Sequenzen verschieben können. Die Idee ist, dass Sie nach Bedarf einzelne Karten in die freien Zellen hinein- und herausweben, um das Spiel zu lösen.

Ihre Aufgabe ist es, ein Programm zu erstellen, das diese Spiele in möglichst wenigen Zügen löst.

Ihr Programm nimmt eine Folge von 52 Karten in folgendem Format als Eingabe:

2S 9H 10C 6H 4H 7S 2D QD KD QC 10S AC ...

Welche werden im ersten Layout in dieser Reihenfolge behandelt:

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 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52

Und geben Sie eine Liste der Züge zurück, um das Spiel zu lösen. Jeder Zug wird in diesem Format sein:

  • Eine Zahl, die die Stapelnummer ( 1bis 8) darstellt, oder eine freie Zelle ( Abis D), die den Quellstapel darstellt.
  • Eine andere Zahl oder ein anderer Buchstabe, die bzw. der den Zielstapel oder die freie Zelle oder Fdie Grundlage dieser Klage darstellt.

Die Ausgabe sieht ungefähr so ​​aus:

18 28 3A 8B 8C 85 B5 35 4F etc.

Sobald eine Karte in das Fundament gelegt wurde, kann sie nicht mehr entfernt werden. Da jeweils nur eine Karte bewegt wird, sind für das Bewegen einer Folge von 3 Karten 5 Züge und für eine Folge von 5 Karten 9 Züge erforderlich.

Wenn ein Spiel nicht lösbar ist, sollte Ihr Programm dies anzeigen. Ihr Programm muss jedoch in der Lage sein, jedes lösbare Spiel zu lösen.

Ihr Programm wird anhand der 32.768 Angebote des ursprünglichen Microsoft FreeCell-Programms bewertet. Um gültig zu sein, muss Ihr Programm jeden Deal mit Ausnahme von Deal # 11.982 , der nicht lösbar ist, erfolgreich lösen . Ihre Punktzahl ist die Gesamtzahl der Züge, die erforderlich sind, um diese 32.767 Deals zu lösen.


Eine Datei mit allen Decks im von der obigen Spezifikation geforderten Format steht hier zum Download bereit (5,00 MB-Datei): https://github.com/joezeng/pcg-se-files/raw/master/freecell_decks

Joe Z.
quelle
1
Jetzt muss ich nur noch den Zufallsgenerator nappen, mit dem diese 32.768 Spiele generiert wurden. : S
Joe Z.
3
Der Generator ist hier: rosettacode.org/wiki/Deal_cards_for_FreeCell
nutki
1
Das ist ein guter Punkt. Wie würden Sie mit dem Fall umgehen, in dem sich beispielsweise zwei Karten mit derselben Farbe und Nummer (wie 7C und 7S) in freien Zellen befinden? Wenn Sie dann von "C" auf eine schwarze 8 wechseln, kann es sich um eine dieser beiden Karten handeln.
Joe Z.
2
Sie könnten möglicherweise einige Antworten erhalten, indem Sie die Einschränkung aufheben, dass alle lösbaren Deals von der Einreichung gelöst werden müssen. Dann Punktzahl basierend auf der Anzahl der gelösten Deals, dann mit den wenigsten Zügen.
mbomb007
1
Können die Karten 0-indiziert werden?
Tuskiomi

Antworten:

22

C 64.643 Bytes, Score: ~ 6,5 Millionen

Das folgende Stack-Snippet (mit freundlicher Genehmigung von Mego) gibt den gesamten Code als einzelne eigenständige C-Datei aus:

Laden Sie hier die Originalquelle herunter . Verwenden Sie GCC und führen Sie es makedann anhand der Richtlinie in der Readme aus.

Meine Formatierung ist schlecht (alle verschiedenen Dateien befinden sich in einem Codeblock) und dies könnte mehr Golf gespielt werden (12 KB bis). Jede Hilfe würde geliebt werden!

Ein Teil des Codes ist nicht von mir. Ich habe es aus einer nicht urheberrechtlich geschützten Quelle verwendet. Ich habe jedoch festgelegt, dass die Eingabe- / Ausgabemethode innerhalb der Herausforderung liegt (eine lange Aufgabe, da ich bei C (5 Stunden) schrecklich bin). Ich musste auch einen Großteil des Codes neu schreiben und alles debuggen. Vielen Dank an meinen Vater, der mir geholfen hat, eine Gummiente zu sein (und auf meine Speicherverwaltungsfehler hingewiesen hat) und an alle TNB-Mitglieder, die sich mit meinen wütenden Schimpfen über Segfaults und C auseinandergesetzt haben.

Christopher
quelle
Sie können verwenden, um diese um die Antwort Längenbeschränkung zu bekommen und haben alle Ihre Codes in der Antwort, anstatt einen externen Download benötigen.
Mego
@ Mego ich meine ja, aber es ist in mehreren Dateien
Christopher
Es ist einfach, mehrere C-Dateien zu einer einzigen zu kombinieren.
Mego
Hier ist ein Stack-Snippet, das den Code in einer einzigen Datei zusammenfasst.
Mego
@mego kannst du das in bearbeiten? Auf dem Handy
Christopher