Tämä asiakirja on saatavilla myös suomeksi. This document is also available in English.
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.
| Variante | GCC 9.2.1 | clang 8.0.1 |
|---|---|---|
C -DRECURSION |
27,7 s | 31,2 s |
C++ -DRECURSION |
28,7 s | 27,6 s |
| C | 26,9 s | 29,4 s |
| C++ | 27,6 s | 27,1 s |
C++ -DHEAP_STACK |
27,7 s | 28,1 s |
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:
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 der clang-Löser 15 599 Sekunden (4 Stunden, 19 Minuten und 59 Sekunden) verbraucht hat.
März 2024 ist es mir nicht gelungen, einen Kreuz aus 6 hölzernen Quadern zusammenzubauen, so habe ich ein Programm geschrieben, das die Lösungen findet. Einer von den Quadern ist ganz mit dem Volumen 2×2×8. Bei den anderen Quadern fehlen in der Mitte 2×2×4 einige Würfel. Obwohl ich während der Suche keine Suchbäume ausschließe, werden die Lösungen in etwa 0,2 Sekunden gefunden.