Hallo in die Runde, ich habe nach einiger Zeit mal wieder ein Geduldsspiel in die Hände bekommen, welches ich vor Jahren gekauft, aber nie gelöst habe: 25 Holzwürfel (je 5 Stück von 5 verschiedenen Farben) sind zu sieben 3er und zwei 2er Blöcken zusammengeklebt. Diese Blöcke müssen nun so in ein 5x5 Quadrat gelegt werden, dass jede Farbe pro Reihe und Spalte genau einmal vorkommt. Ich habe zwar schon ein wenig über Algorithmen für "15er-Puzzle" gelesen, die u.U. durchaus artverwandt sind, kann das aber nicht auf mein Puzzle anwenden, da ja nicht aus einer Ausgangslage durch eine bestimmte Zugfolge eine Lösung erreicht werden muss. 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. Ich denke allerdings, dass das nicht unbedingt die optimale Lösung ist, 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. - Ich erzeuge mir nacheinander mögliche Anordnungen von 1x1-Würfeln im Quadrat und prüfe dann, ob es möglich ist, diese Anordnung mit den vorgegebenen Blöcken abzudecken. Ob das allerdings unbedingt schneller geht, weiß ich auch nicht - Generell könnte man ja auch ALLE möglichen Platzierungsreihenfolgen berechnen und dann Stein 1 an die erste mögliche freie Stelle, Stein 2 erst an die nächste, dann die übernächste. dann die überübernächste setzen, usw., aber dass dürfte wohl die Variante größten Aufwands werden... Dazu 9 Schleifen ineinander zu schachteln mag hier zwar funktionieren, ist aber auch nicht soooo schön, zumal es ja auch die entsprechenden Abbruchbedingungen geben müsste.. Was meint ihr dazu? Viele Grüße, FargoTof
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.
:
Bearbeitet durch Moderator
Starte in einem "Eck" da dort bereits gewisse vereinfachende Einschränkgungen gelten. Dann verwende eine Breitensuche anstelle eine Tiefensuche. Da davon auszugehen ist das das "Spiel" von "Menschen" lösbar ist ist das ein intuitiv gewinnversprechender Ansatz. Außerdem ist zu erwarten dass es mehrere mögliche Lösungen gibt, die Breitensuche also bereits recht früh zu einer Lösung führt. Bei der Breitensuche kann man dann wieder optimieren in dem du die Liste der möglichen Platzierungen sortierst, z.b. das "Bauteil" das am wenigsten mögliche Platzierungen zulässt als nächstes verwendest.
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.
:
Bearbeitet durch User
Guten Morgen! Karl Heinz schrieb: > Erfahrung gewinnt man nur > dadurch, indem man die Dinge macht. Ja ja, hast ja recht ;) Tatsächlich habe ich das Spiel gestern relativ schnell gelöst bekommen, und zwar mit Variante 1. In neun (neun Teile!) ineinander verschachtelten Schleifen werden nacheinander immer mehr Steine versucht im Spielfeld zu platzieren und falls nötig wieder rückwärts so weit entfernt, bis man weiter voran kommt (bzw. letztlich bis zum Ziel). 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) und das auch wirklich schnell (<10s). Großen Optimierungsbedarf sehe ich insofern erstmal nicht ;) Viele Grüße, FargoTof
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 :)
Hmm. Darauf bin ich noch nicht gekommen. :D Muss aber tatsächlich so sein. Umso komplizierter dann eigentlich, sich das Rätsel auch genau so zu überlegen, dass es nur "eine" Lösung gibt... Es wird sicherlich Konstellationen von Blöcken geben, die mehrere Lösungen ermöglichen. Sollte ich vllt. mal versuchen herauszufinden ;)
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)
:
Bearbeitet durch User
Naja, die anzuordnenden Blöcke sind ja farblich alle unterschiedlich zusammengesetzt. Insofern müsste man den Benutzer auch das erstmal definieren lassen. Das werde ich daher erstmal sein lassen.. Aber dem 8-Damen-Problem werde ich mich durchaus mal annehmen. Gern auch rekursiv, denn mit rekursion habe ich soweit kaum Berührungspunkte, da schadet es nicht, sich mal wieder damit auseinanderzusetzen... :)
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.
:
Bearbeitet durch User
Yalu X. schrieb: > 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. Ich kann leider schon wieder hier von Arbeit den verlinkten Inhalt nicht öffnen.. Und ich finde auch grad kein Foto von meinem Puzzle. Ich liefere aber nachher mal nach, wie die Blöcke bei mir zusammengesetzt sind.
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..)
:
Bearbeitet durch User
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.
:
Bearbeitet durch Moderator
Moin,
hier nochmal wie versprochen meine Blöcke (als Auszug aus meinem
Java-Programm.. jaja, Java... ;)):
Bloc myBloc = new Bloc();
myBloc.addStone(Bloc.COLOR_GREEN);
myBloc.addStone(Bloc.COLOR_BROWN);
myBloc.setNumber(1);
blocs.add(myBloc);
myBloc = new Bloc();
myBloc.addStone(Bloc.COLOR_GRAINED);
myBloc.addStone(Bloc.COLOR_WHITE);
myBloc.setNumber(2);
blocs.add(myBloc);
myBloc = new Bloc();
myBloc.addStone(Bloc.COLOR_WHITE);
myBloc.addStone(Bloc.COLOR_BLACK);
myBloc.addStone(Bloc.COLOR_GRAINED);
myBloc.setNumber(3);
blocs.add(myBloc);
myBloc = new Bloc();
myBloc.addStone(Bloc.COLOR_GREEN);
myBloc.addStone(Bloc.COLOR_BROWN);
myBloc.addStone(Bloc.COLOR_GRAINED);
myBloc.setNumber(4);
blocs.add(myBloc);
myBloc = new Bloc();
myBloc.addStone(Bloc.COLOR_WHITE);
myBloc.addStone(Bloc.COLOR_BLACK);
myBloc.addStone(Bloc.COLOR_BROWN);
myBloc.setNumber(5);
blocs.add(myBloc);
myBloc = new Bloc();
myBloc.addStone(Bloc.COLOR_WHITE);
myBloc.addStone(Bloc.COLOR_GRAINED);
myBloc.addStone(Bloc.COLOR_BROWN);
myBloc.setNumber(6);
blocs.add(myBloc);
myBloc = new Bloc();
myBloc.addStone(Bloc.COLOR_BLACK);
myBloc.addStone(Bloc.COLOR_WHITE);
myBloc.addStone(Bloc.COLOR_GREEN);
myBloc.setNumber(7);
blocs.add(myBloc);
myBloc = new Bloc();
myBloc.addStone(Bloc.COLOR_GRAINED);
myBloc.addStone(Bloc.COLOR_GREEN);
myBloc.addStone(Bloc.COLOR_BLACK);
myBloc.setNumber(8);
blocs.add(myBloc);
myBloc = new Bloc();
myBloc.addStone(Bloc.COLOR_BLACK);
myBloc.addStone(Bloc.COLOR_BROWN);
myBloc.addStone(Bloc.COLOR_GREEN);
myBloc.setNumber(9);
blocs.add(myBloc);
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
:
Bearbeitet durch User
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.
:
Bearbeitet durch Moderator
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
:
Bearbeitet durch User
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 ;-)
:
Bearbeitet durch Moderator
Thread beobachten
Seitenaufteilung abschaltenBitte 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.