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.

Kompiliert mit -O3 -DNDEBUG und einer Entwicklungsversion von clang 4.0.0 war das C++-Programm 10% schneller als das C-Programm. Mit GCC 6.2.1 und denselben Schaltern war das C-Programm ungefähr so schnell wie das clang-C++-Programm, und das GCC-C++-Programm war 25% langsamer. (Gegen meine Erwartungen wurde das GCC-C++-Programm etwas schneller, wenn std::array durch std::vector ersetzt wurde.)

Mit C++ template habe ich 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. Es wäre interessant, die Rekursion durch eine Schleife über einen Suchstapel zu ersetzen.

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 433 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.

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 433 Lösungen des 4×4×4-Puzzles