Tämä asiakirja on saatavilla myös suomeksi. This document is also available in English.

Marko Mäkelä: Programmieren: Lösen der Pentomino Puzzles

Ich mag kombinatorische Probleme, aber wenn möglich, löse ich sie mit roher Gewalt. Um 2000 rum habe ich die Lösungen des 6×10 Pentomino Puzzle in ein paar CPU-Wochen auf einigen 266 MHz Pentium II Rechnern berechnet.

Meine Lösung in der Programmiersprache C ist eine Tiefensuche. 2013 machte ich eine triviale Verbesserung, um unmögliche Suchbäume auszuschließen, in denen die Größe eines Lochs nicht durch 5 teilbar ist. Das Ausschließen kann mit Hilfe von Flutfüllung realisiert werden. Auf einem mit 2,5 GHz getaktetem Intel Core i5-2520M System hat das optimierte C-Programm alle Kombinationen in etwa 4 Minuten durchgesucht.

Eine Version in C++ nützt die STL aus. Auf meinem System war das optimierte C++-Programm langsamer als das C-Programm, wegen der dynamischen Speicherverwaltung in der Flutfüllung. In dem C-Programm wurde die Warteschlange mit einem Ringpuffer-Feld realisiert, während in dem C++-Programm die std::list eingesetzt wurde.

Der Unterschied in der Rechenleistung ist Januar 2014 verschwunden, als ich bemerkt habe, dass die Warteschlange in diesem Fall besser als eine Menge dargestellt werden kann. So wird eine Zelle höchstens einmal aus der Warteschlange zurückgeholt. Desweiteren kann die Menge als ein Bitfeld (64-Bit Integer) dargestellt werden, genau wie das Pentomino-Brett (6×10). Die Rechenleistung ist um 60% verbessert geworden, als ich merkte, dass die schon gefüllten Zellen von dem Bitfeld entfernt werden können, so dass niemals eine bereits gefüllte Zelle zurückgeholt wird. Noch mehr Leistung (alle 2 339 Lösungen in 40 Sekunden finden) gab es, nachdem ich symmetrische Lagen des ersten Klotzes eliminierte. Für den I-förmigen Klotz gibt es 56 Lagen vor und 14 Lagen nach dieser Vereinfachung.

Dezember 2016 habe ich die den C++14 Kennwort constexpr eingesetzt, so dass die Bitfelder entsprechend zu den Klötzen (bis zu 8 unterschiedliche Orientierung je Klotz) schon während der Kompilierung umgewandelt werden. Weiterhin habe ich versucht, die Bitfelder entsprechend zu allen 2 014 Lagen der Klötze während der Kompilierung initiieren zu lassen. Das war eine schlechte Idee nicht nur wegen der Kolmogorow-Komplexität (die Lagen können in weniger als 2 014×64 Bits von Code initiiert werden) aber auch weil clang verweigert hat, die lange Berechnung während der Kompilierung durchzuführen.

August 2019 habe ich die Rekursion durch eine Schleife über einen Suchstapel ersetzt. Mit einem statisch allokierten Feld für den Stapel wird die Suche etwas schneller als mit der originalen Rekursion (-DRECURSION). Wie erwartet, ist dynamische Allokierung (-DHEAP_STACK, nur in C++) etwas langsamer. Achtung: Die Option -DRECURSION wird die Suche in einer anderen Reihenfolge durchführen als der Suchstapel.

Mit C++ template hatte ich früher versucht, die Rekursion vom Kompilierer entfalten zu lassen, da die Suchtiefe ja auf 12 festgelegt ist. Das hat jedoch die Laufzeit ein wenig verlängert.

Kompiliert mit -O3 -DNDEBUG -mtune=native -march=native und clang 8.0.1 war das C++-Programm 8% schneller als das C-Programm. Mit GCC 9.2.1 und denselben Schaltern war das C-Programm 3% schneller als das C++-Programm. Der größte Ausreißer ist das vom clang kompilierte C-Programm, das wesentlich langsamer ist als der Rest.

Laufzeiten (Intel® Xeon® E5-2630 v4, 2,2 GHz)
Variante GCC 9.2.1 clang 8.0.1
C -DRECURSION 27,7 s31,2 s
C++ -DRECURSION 28,7 s27,6 s
C 26,9 s29,4 s
C++ 27,6 s27,1 s
C++ -DHEAP_STACK 27,7 s28,1 s

3-dimensionale Puzzles

Anfang 2014 hat meine Frau eine 4×4×4 Puzzle auf dem Flohmarkt gefunden. Der Würfel wird mit einem Klotz der Größe 4 und mit 12 Klötzen der Größe 5 gepackt: 4×4×4=4+12×5=64. Anders als in dem Pentomino Puzzle sind diese Klötze nur eine Untermenge aller möglichen Klötze dieser Größe, und es scheint 20 434 Lösungen zu geben. Mit kleinen Änderungen kann die gleiche Lösung eingesetzt werden:

  1. Wegen Einfachkeit werden die Klötze als Zeichenketten dargestellt.
  2. Jede Zeichenkette wird in ein Bitfeld umgewandelt, das das Brett bzw. den Würfel darstellt.
  3. Jeder Klotz wird gedreht und geschoben, um alle mögliche Lagen im Puzzle zu erzeugen.
  4. Beginne die Tiefensuche mit dem Klotz der Größe 4.
  5. Ist ein Loch nicht durch 5 teilbar, schließe die Teillösung aus, da es kein Platz für alle restlichen Klötze (Größe 5) gibt.

Dezember 2016, als ich den Löser nach C++14 umgewandelt habe, habe ich einen Fehler in meiner Suche nach symmetrischen Lagen festgelegt. Wird ein Klotz um jeden Axel gedreht, gibt es 4×4×4 bzw. 64 mögliche Lagen. Für den kleinen Klotz in meinem Puzzle sind 12 von den Lagen unterschiedlich. Viele von diesen 12 Lagen sind aber miteinander symmetrisch, wenn man den Klotz in eine Ecke des Würfels stecken und dann den gesamten Würfel in allen 64 Lagen drehen, ohne den Klotz relativ zum Würfel zu schieben. Wenn man den kleinen Klotz beliebig innerhalb des Würfels schieben kann, gibt es insgesamt nur 15 unterschiedliche Lagen, statt 261 wie mein ursprüngliches Programm es berechnet hat.

GCC 9.2.1 erzeugt einen wesentlich schnelleren Löser für AMD64 als clang 8.0.1. August 2019 hat das von GCC kompilierte Löser die Suche in 14 063 Sekunden (3 Stunden, 54 Minuten und 23 Sekunden) vollendet, während das clang-Löser 15 599 Sekunden (4 Stunden, 19 Minuten und 59 Sekunden) verbraucht hat.

Herunterladen

pentomino.c
Pentomino-Löser in C
pentomino.C
Pentomino-Löser in C++
pentomino.png
Bild von allen 2 339 Lösungen des 6×10-Puzzle
pentomino.pl
Ein Progrämmchen, das das Bild von allen 2 339 Lösungen erzeugt
puzzle3d.C
Löser eines dreidimensionalen 4×4×4-Puzzles in C++
puzzle3d.txt.gz
Die 20 434 Lösungen des 4×4×4-Puzzles