Algorithmus für 5x5 Puzzle (Geduldspiel) gesucht

Geht es um dieses Puzzle hier?

  https://app.box.com/s/e46s46chzjgtyko1lrtu

Da ist allerdings Aufgabenstellung etwas anders beschrieben als bei dir.

Edit: Ah, doch, die erste Variante, wo die Teile alle rechteckig sind
und zu einem Quadrat zusammengefügt werden müssen, entspricht genau
deiner Beschreibung.

FargoTof schrieb:

> Wie geht man das Ganze am Besten an?
>
> Meine bisherigen Ideen:
>
> - Ich platziere Stein 1 an der ersten leeren Position im Feld. Ich
> platziere Stein 2 an der nächsten freien Stelle im Feld und prüfe dann,
> ob die Bedingungen noch erfüllt sind. Falls ja: weiter. Falls nein,
> Stein wieder entfernen und auf die nächste freie Stelle legen. usw. usf.

Der Begriff für diese Art der universellen Problemlösung ist 
'Backtracking'. Das Backtracking Verfahren ist immerhin so mächtig, dass 
sich eine ganze Programmiersprache drum herum entwickelt hat - Prolog.

> Ich denke allerdings, dass das nicht unbedingt die optimale Lösung ist

Was ist schon 'optimal'.
Erste Voraussetzung dafür ist es erst mal, dass du überhaupt zu einer 
Lösung kommst. Bist du soweit? Hast du ein Programm, welches die 
Aufgabenstellung löst?

> insbesondere auch, weil u.U. schon die ersten beide Steine so gelegt
> werden können, dass die anderen unabhängig von der Farbe allein schon
> gar nicht mehr im Quadrat platziert werden können.

Ja und?
Wenn ein Stein nicht mehr platziert werden kann, dann ist das bisherige 
offenbar keine sinnvolle Anordnung, da sich dadurch keine Lösung 
erzielen lässt -> 1 Backtrack Schritt, der zuletzt gelegte Stein wird 
anders gelegt und nachgesehen, ob es damit möglich ist zu einer Lösung 
zu gelangen.

> Was meint ihr dazu?

Probier deine unterschiedlichen Strategien aus, in dem du jeweils ein 
Programm dafür schreibst. Dann machst du Untersuchungen darüber, welches 
Verfahren wie lange dauert und wie sich das Zeitverhalten entwickelt. 
Dazu ist es oftmals auch eine gute Idee, sich im Detail anzusehen, wie 
eigentlich das Programm zur Lösung kommt (das Programm gibt zb nach 
jedem Schritt eine Zwischenlösung aus und protokolliert mit was es warum 
getan hat). Daraus zieht man dann seine Schlüsse und erkennt, wann 
welches Verfahren sich wie gut eigenet. So etwas nennt man dann 
'Lernen'.
Und ja. Man kann viel davon lernen, indem man dasselbe Problem mit 
unterschiedlichen Lösungsstrategien einfach durchprobiert. Niemand hat 
seine Karriere damit angefangen, dass er von Haus aus wusste, welches 
Verfahren sich wann besonders gut eignet. Erfahrung gewinnt man nur 
dadurch, indem man die Dinge macht.

FargoTof schrieb:
> Interessanterweise habe ich insgesamt acht Lösungen erhalten (da jeweils
> vier identisch sind und nur um 0°, 90°, 180°, 270° verdreht also zwei
> Lösungen)

... von denen wahrscheinlich die eine das Spiegelbild der anderen ist :)

FargoTof schrieb:

> Tatsächlich habe ich das Spiel gestern relativ schnell gelöst bekommen,
> und zwar mit Variante 1. In neun (neun Teile!) ineinander
> verschachtelten Schleifen

Gut.

Jetzt nimmst du dir das ganze nochmal vor und löst die ineinander 
verschachtelten Schleifen durch eine rekursive Funktion.

Voila. Du hast die Lösung soweit verändert, dass sie nicht mehr mit 
einer ganz bestimmten Anzahl an Klötzchen funktioniert, sondern das du 
die Anzahl der Klötzchen auch von einem Benutzer eingeben lassen kannst. 
Wenn der die Anzahl wie in der ursprünglichen Aufgabenstellung eingibt, 
dann kommt wieder dieselbe Lösung raus. Aber man kann auch andere 
Vorgaben machen und zb sich mal ansehen, wieviele Lösungen es für jede 
Anzahl an Klötzchen gibt.

Als Anregung könntest du dir zb. mal eine Lösung zum '8-Damen-Problem' 
ansehen. Das ist eines der klassischen Beispiele für Backtracking.
(Beim 8-(Schach)Damen Problem geht es darum, 8 Damen auf einem 
Schachbrett so anzuordnen, dass keine Dame eine andere schlagen kann)

Ich habe das Puzzle auch mal programmiert und dabei die Klötzchenfarben
wie in diesem Link gewählt:

  https://app.box.com/s/e46s46chzjgtyko1lrtu

Das Programm findet in 7,5 ms 320 Lösungen. Wenn von denjenigen, die
durch Rotation, Spiegelung oder Vertauschen der beiden Zweierklötzchen
(die die gleichen Farben haben) ineinander übergehen, jeweils alle bis
auf eine weglässt, bleiben immer noch 20 Lösungen übrig. Ich habe zwar
nicht alle auf Richtigkeit überprüft, es sind aber definitiv mehr als 2
unterschiedliche Lösungen.

@FargoTof:

Sind bei dir die Klötzchen vielleicht anders eingefärbt, dass es bei dir
nur so wenig Lösungen gibt? Wenn ja, würde mich interessieren, wie.

zeigt mal euren Code.
Was mich bei solchen Aufgaben immer nervt, ist, dass man teilweise mehr 
Zeit damit verbringt, die Spielmechanik zu implementieren, als den 
eigentlichen Lösungsalgorithmus.

geht IMHO auch ohne  Rekursion oder verschachtelte Schleifen, oder ?
(was nicht heißen soll, dass es einfacher/besser wäre: ich finde die 
Rekursion auch einfacher..)

aber nur von der IDEE her:

ist das nicht eine 9 Stellige "Zahl" in einem 100er Zahlensystem?
die man auch als 18-Stellige Zahl im Dezimalsystem Darstellen könnte

also 10^18 (100^9) Möglichkeiten

also einfach eine Schleife von 0 bis 999999999999999999 (was praktisch 
ist, weil sich das mit 64bit locker ausgeht..)

viele Möglichkeiten scheiden dann recht schnell aus, weil sich Steine 
überlappen oder aus dem Spielfeld ragen.., aber das ist mit anderen 
Methoden ja ähnlich)

ich Frage mich aber jetzt wie man so viele Möglichkeiten (oder hab ich 
mich verrechnet) in 7,5 ms schafft??

Edit: Nachtrag: wobei sich die Rekursive Methode natürlich VIEL 
einfacher optimieren lässt (damit auch die 7,5 ms wohl möglich sind..)

Robert L. schrieb:
> ist das nicht eine 9 Stellige "Zahl" in einem 100er Zahlensystem?
> die man auch als 18-Stellige Zahl im Dezimalsystem Darstellen könnte

Ich nehme an, die 9 Stellen stehen für die 9 Teile, die platziert werden
sollen und die 100 verschiedenen Ziffern für die 25 möglichen Positionen
multipliziert mit den 4 möglichen Orientiereungen für jedes Teil.

Ja, so kann man das rekursionsfrei und ohne verschachtelte Schleifen
machen. Aber, wie du schon richtig erkannt hast, lässt sich auf diese
Weise der Suchbaum nicht (oder nur sehr umständlich) beschneiden, und
1e18 ist halt schon eine ziemlich große Zahl. Selbst wenn man jede Zahl
(d.h. Anordnung der Teile) in nur 1 ns überprüfen könnte, würde die
komplette Suche über 31 Jahre dauern.

Um den Suchbaum klein zu halten, bin ich bei meinem Algorithmus
folgendermaßen vorgegangen:

Die Teile werden nacheinander jeweils so platziert, dass ihre linke
obere Ecke möglichst weit oben und (bei mehreren Möglichkeiten)
möglichst weit links im Spielfeld zu liegen kommt.

Beispiele:

1

Erstes Teil:

2

 —————          —————          —————          —————

3

|ooo  |        |o    |        |oo   |        |o    |

4

|     |        |o    |        |     |        |o    |

5

|     |  oder  |o    |  oder  |     |  oder  |     |

6

|     |        |     |        |     |        |     |

7

|     |        |     |        |     |        |     |

8

 —————          —————          —————          —————

9

10

Wenn bereits einige Teile platziert sind (Felder mit #):

11

 —————          —————          —————          ————— 

12

|#####|        |#####|        |#####|        |#####|

13

|##ooo|        |##o  |        |##oo |        |##o  |

14

|#    |  oder  |# o  |  oder  |#    |  oder  |# o  |

15

|     |        |  o  |        |     |        |     |

16

|     |        |     |        |     |        |     |

17

 —————          —————          —————          —————

Diese Vorgehensweise hat folgende Vorteile:

- Für das i-te hinzugefügte Teil (i=1..9) müssen maximal 4·(10-i)
  Möglichkeiten durchprobiert werden (10-i Teile in 4 Orientierungen),
  da die Position bereits festgelegt ist. Eine erschöpfende Suche müsste
  also 4⁹·9!≈ 1e11 Kombinationen  untersuchen (ein Zehnmillionstel der
  obigen 1e18), was auch ohne weitere Optimierung durchaus schon im
  Bereich des Machbaren läge.

- Die Teile werden von Anfang an recht dicht gepackt, so dass sich
  schnell Situationen ergeben, wo auf Grund unpassender Farben keine
  weiteren Teile mehr angelegt werden können, der Suchbaum an dieser
  Stelle also abgeschnitten wird.

- Löcher von der Größe eines einzelnen Felds, bei deren Auftreten eine
  Fortsetzung Suche Zeitverschwendung wäre, können bei dieser Methode
  erst entstehen, wenn das Spielfeld schon fast komplett gefüllt ist.
  Man muss sie deswegen nicht explizit vermeiden.

Für jedes hinzugefügte Teil wird sofort überprüft, ob es geometrisch und
farblich passt. Wenn nicht, wird die Suche mit der nächsten Alternative
fortgesetzt. Dadurch reduziert sich die Anzahl der Knoten des Suchbaums
auf 48193.

Um schnell entscheiden zu können,

- welche Teile jeweils noch verfügbar sind,

- auf welchem Feld diese platziert werden sollen und

- welche Farben auf jedem Feld noch erlaubt sind,

habe ich noch etwas Bit-Magic einfließen lassen, so das am Ende wirklich
nicht mehr allzu viel zu rechnen ist.

Der eigentliche Lösungsalgorithmus steckt in der Funktion solve, die
sich in bis zu 9 Ebenen rekursiv aufruft und jeweils beim Erreichen der
letzten Ebene eine Lösung ausgibt.

FargoTof schrieb:
> Moin,
>
> hier nochmal wie versprochen meine Blöcke (als Auszug aus meinem
> Java-Programm.. jaja, Java... ;)):

entspricht:

1

enum Color {

2

  RED    = 1<<0,// black

3

  YELLOW = 1<<1,//Bloc.COLOR_GRAINED

4

  GREEN  = 1<<2,//Bloc.COLOR_GREEN

5

  BLUE   = 1<<3,// COLOR_BROWN  

6

  WHITE  = 1<<4 //COLOR_WHITE

7

};

8

9

struct Part {

10

  int n;

11

  uint8_t colors[3];

12

};

13

14

struct Part parts[] = {

15

  [1<<0] = { 3, { WHITE, RED, YELLOW } },

16

  [1<<1] = { 3, {  GREEN, BLUE, YELLOW } },

17

  [1<<2] = { 3, { WHITE, RED, BLUE } },

18

  [1<<3] = { 3, { WHITE, YELLOW, BLUE } },

19

  [1<<4] = { 3, { RED, WHITE, GREEN } },

20

  [1<<5] = { 3, { YELLOW, GREEN, RED } },

21

  [1<<6] = { 3, { RED, BLUE, GREEN } },

22

  [1<<7] = { 2, { YELLOW, WHITE } },

23

  [1<<8] = { 2, { GREEN, BLUE } }

24

};

in Yalus code 
(Beitrag "Re: Algorithmus für 5x5 Puzzle (Geduldspiel) gesucht")

und produziert:

1

B-R-W Y G    G Y W-R-B     W-R-Y B G    G B Y-R-W

2

      | |    | |                 | |    | |      

3

Y-G-R W B    B W R-G-Y     R-B-G Y W    W Y G-B-R

4

        |    |                   | |    | |      

5

R W B-G Y    Y G-B W R     Y G-B W R    R W B-G Y

6

| |                | |     |                    |

7

W Y G-B-R    R-B-G Y W     B W R-G-Y    Y-G-R W B

8

| |                | |     | |                | |

9

G B Y-R-W    W-R-Y B G     G Y W-R-B    B-R-W Y G

10

11

12

B Y R-W-G     G-W-R Y B    W R Y-B-G   G-B-Y R W

13

| |                 | |    | |               | |

14

R G W-Y-B     B-Y-W G R    R B G W-Y   Y-W G B R

15

| |                 | |    | | |           | | |

16

W R B G Y     Y G B R W    Y G B R W   W R B G Y

17

    | | |     | | |              | |   | |      

18

Y-W G B R     R B G W-Y    B-Y-W G R   R G W-Y-B

19

      | |     | |                | |   | |      

20

G-B-Y R W     W R Y-B-G    G-W-R Y B   B Y R-W-G

2 Lösungen, der rest sind Spiegelungen, die ich nebeneinander gepackt 
habe

Die unteren 4 Lösungen sind Spiegelungen der oberen 4 Lösungen an der 
Diagonale. Dadurch ist die Lösung bis auf die Spiegelungen tatsächlich 
eindeutig.

Karl Heinz schrieb:
> Aber man kann auch andere Vorgaben machen und zb sich mal ansehen,
> wieviele Lösungen es für jede Anzahl an Klötzchen gibt.
>
> Als Anregung könntest du dir zb. mal eine Lösung zum '8-Damen-Problem'
> ansehen. Das ist eines der klassischen Beispiele für Backtracking.

Wobei man in der Regel nur EINE Lösung sucht und nicht alle, das kann 
nämlich die Laufzeit empfindlich erhöhen.

Manchmal interessiert natürlich auch, wieviele Lösungen es gibt.
Gerade beim 8-Damen-Problem ist der Suchraum nicht besonders groß, so
dass man recht fix alle Lösungen suchen kann. Das Progrämmchen im Anhang
braucht dafür gerade einmal 16 µs (ohne Ausgabe). Es liefert 92 Löungen
bzw. 12, die nicht durch Spiegelung oder Rotation aus anderen Lösungen
hervorgehen.

Frage zu den 2 C Progrämmchen hier..
die wurden (wohl nicht nur aus Sicht eines Pascal programmierers ;-) ) 
wohl eher auf Geschwindigkeit Optimiert, denn auf 
Lesbarkeit/Verständlichkeit..

wie "beweist" man hier jetzt, dass die Lösung richtig ist, und es nicht 
doch noch Andere Möglichkeiten gibt
(das ist jetzt eher eine allgemein Fragen, nicht speziell auf diese 2 
Beispiele gerichtet)

sollte/müsste man nicht erst ein einfaches/verständliches und vor allem 
allgemeineres u.U. natürlich langsameres Programm schreiben,

quasi als "Beweis" ?

(vorallem uint64_t del[] ist sehr "woher zum Teufel kommt das")

konkret lässt sich das letzte Programm hier auch schlecht auf andere 
Spielfeldgrößen erweitern?

http://de.wikipedia.org/w/index.php?title=Damenproblem&redirect=no

Robert L. schrieb:
> Frage zu den 2 C Progrämmchen hier..
> die wurden (wohl nicht nur aus Sicht eines Pascal programmierers ;-) )
> wohl eher auf Geschwindigkeit Optimiert, denn auf
> Lesbarkeit/Verständlichkeit..

Genau so ist es ;-)

Robert L. schrieb:
> wie "beweist" man hier jetzt, dass die Lösung richtig ist, und es nicht
> doch noch Andere Möglichkeiten gibt
> (das ist jetzt eher eine allgemein Fragen, nicht speziell auf diese 2
> Beispiele gerichtet)

Ja, wie beweist man, dass ein Programm korrekt ist? Das ist oft sehr
schwierig und deswegen Gegenstand aktueller Forschung.

Dazu braucht man erst einmal eine formale und allgemein akzeptierte
Definition des Problems. Dann kann man versuchen, mit viel Logik vom
Programmcode auf diese Definition zu schließen oder umgekehrt.

Als formale Definition könnte man den C-Code selbst heranziehen, dann
wäre der Beweis der Korrektheit trivial. Nur würde vermutlich kaum
jemand diese Definition des Problems akzeptieren ;-)

Programme in funktionalen Programmiersprachen lassen sich oft (vor
allem, wenn Effizienz unwichtig ist) so schreiben, dass sie weniger wie
ein Programm, sondern eher wie eine mathematische Beschreibung des zu
lösenden Problems aussehen. Ich habe mal das 8-Damen-Problem auf diese
Weise in Haskell formuliert. Zusammen mit den Kommentaren (jeweils
eingeleitet durch "--") sollte der Code auch für Nichthaskellianer
halbwegs verständlich sein. Hat man ihn verstanden, ist schnell
einzusehen, dass dieser Code das Problem korrekt beschreibt.

Anmerkung: Damit der Code ohne große Haskell-Kenntnisse verständlich
ist, ist er sehr geradlinig gehalten, enthält deswegen absichtlich viel
Copy/Paste und ist auf eine feste Zahl von Feldern (8×8) beschränkt. Die
Zusammenfassung der Copy/Paste-Teile würde den Code kompakter und
universeller machen, gleichzeitig aber Wissen über ein paar spezielle
Haskell-Funktionen voraussetzen.

> sollte/müsste man nicht erst ein einfaches/verständliches und vor allem
> allgemeineres u.U. natürlich langsameres Programm schreiben,
>
> quasi als "Beweis" ?

Ja, wenn jeder akzeptiert, dass dieses verständlichere Programm korrekt
ist und es die gleichen Ergebnisse liefert, kann es als Beweis gelten.

Das Haskell-Programm im Anhang kann natürlich auch ausgeführt werden und
liefert dann tatsächlich die gleichen Lösungen wie das obige C-Programm.
Nur braucht es dafür mehr als die 20000-fache Zeit (die mit 360 ms aber
noch lange nicht astronomisch ist).

Das Vorgehen, am Anfang erst einmal einen einfachen und leicht
verifizierbaren Algorithmus zu programmieren und diesen anschließend
schrittweise zu optimieren, propagiert auch Richard Bird in seinem
genialen Buch "Pearls of Functional Algorithm Design" und erläutert es
anhand vieler Beispiele.

Die Verifikation der Optimierungsschritte erfolgt dort aber nicht über
den Vergleich der Programmausgaben, da damit zum einen i.Allg. nicht
alle Fälle abgedeckt werden können und zu anderen der initiale
Algorithmus oft so ineffizient ist, dass er nicht in akzeptabler Zeit
ausgeführt werden kann.

Vielmehr wird jeder Optimierungsschritt als eine Umformung von
Programmcode betrachtet. Jede dieser Umformungen ist so beschaffen, dass
deren Korrektheit beweisbar und in den meisten Fällen sogar
offensichtlich ist. Man kann sie sich ähnlich vorstellen wie die
Umformungen bei der Herleitung einer komplizierten mathematischen
Formel. Viele korrekte Umformungen nacheinander auf ein etwas Korrektes
angewandt ergeben wieder etwas Korrektes.

Am Schluss steht ein effizienter und nachweislich korrekter Algorithmus
in Form eines ausführbaren Programms. Dieser Algorithmus ist naturgemäß
nicht leicht zu verstehen, kann aber konsistent und vollständig durch
das ursprüngliche Programm und die Beschreibung der Optimierungsschritte
dokumentiert werden. Nachträgliche Änderungen oder Erweiterungen sind
leicht möglich, indem man sie erst am übersichtlichen Ursprungscode
vornimmt und danach sämtliche Optimierungsschritte in angepasster Form
wiederholt.

> (vorallem uint64_t del[] ist sehr "woher zum Teufel kommt das")

Das sind Bitmaps der von einer auf einem der 8 Felder der Grundlinie
stehenden bedrohten Felder:

1

10000001 00000010 00000100 00001000

2

01000001 10000010 00000100 00001000

3

00100001 01000010 10000100 00001000

4

00010001 00100010 01000100 10001000

5

00001001 00010010 00100100 01001001

6

00000101 00001010 00010101 00101010

7

00000011 00000111 00001110 00011100

8

       D       D       D       D

9

10

00010000 00100000 01000000 10000001

11

00010000 00100000 01000001 10000010

12

00010000 00100001 01000010 10000100

13

00010001 00100010 01000100 10001000

14

10010010 00100100 01001000 10010000

15

01010100 10101000 01010000 10100000

16

00111000 01110000 11100000 11000000

17

   D       D       D       D           D = Position der Dame

Jedes der acht 7×8-Muster bildet eine von acht 56-Bit-Binärzahlen, die
im Quellcode als Hexdazimalliterale dargestellt sind. Man hätte die
Zahlen vielleicht mit etwas Makro-Magic so hinschreiben können, dass die
obigen Muster deutlicher in Erscheinung treten.

Mit diesen Bitmaps können mit einer einzelnen Operation sämtliche von
einer Dame bedrohten Felder in einem durch eine 64-Bit-Zahl
dargestellten Spielbrett als belegt markiert werden (besser wäre es
eigentlich gewesen, die Bitmaps vorher zu invertieren, dann hätte man
sich bei der Verwendung den ~-Operator sparen können).

Robert L. schrieb:
> konkret lässt sich das letzte Programm hier auch schlecht auf andere
> Spielfeldgrößen erweitern?

Auf kleinere ja, auf größere nicht ohne weiteres. Das Programm nutzt die
Tatsache, dass man ein komplettes 8×8-Spielbrett in einer
64-Bit-Variablen und damit in einem Register eines 64-Bit-Prozessors
ablegen kann, weswegen sämtliche Operationen darauf sehr effizient
umgesetzt werden können.

Mir ging es primär nicht darum, das 8-Damen-Problem allgemein zu lösen
(dafür gibt es im Netz genügend Beispiele), sondern die Ausführungszeit
auf einen unsinnig kleinen Wert zu optimieren ;-)