Die Faszination „wie Formen zusammen passen“ scheint wirklich elementar zu sein, wie die nun schon lange Geschichte des Pentomino zeigt. Die Problemstellung dieser einfachen Figuren aus fünf Quadraten sind so überaus vielfältig, dass man sich der anziehenden Wirkung schwer entziehen kann. Je länger man darüber nachdenkt, um so breiter dehnt sich das Feld aus, welches sich über verwandte Probleme erstreckt. Am Ende landet man in einem Ozean von Formen und Figuren.

Damit fing auch meine Beschäftigung mit dieser Materie an. Zusammen mit meinem Bruder habe ich viele Stunden mit der Suche nach Lösungen von Pentomino, Hexomino und anderen Puzzeln verbracht. Später – so um 1986 – wurde der erste Atari-PC mit der Suche nach Lösungen gequält. Damals entstand das Logelium Projekt mit einem Computerprogramm, welches eine gewisse Klasse von Puzzeln aus geometrischen Formen universell lösen konnte. Der Atari war auch einer der ersten PC, der eine brauchbare grafische Darstellung erlaubte. Ein Ausdruck aus dieser Zeit ist mir erhalten geblieben. (siehe unten)

Pentomino Lösung mit Nadeldrucker Nostalgia

Dann ist das Logelium für eine lange Zeit in einen Dornröschenschlaf verfallen. Geweckt wurde es wieder, als ich mehr zufällig in einem Artikel über die erfolgreiche Auflösung des Eternity Puzzels las. Das Eternity hat – wie mir scheint – zu seiner Zeit eine wahre Flut von Aktivität und Internet Artikeln ausgelöst, die sich mit mathematischen Puzzeln beschäftigen. Heute ist dieser Strom jedoch fast schon wieder versiegt, was leider vermuten lässt, das das Preisgeld doch den größten Teil der Motivation erzeugt hat — eigentlich schade.

Mich hat es jedoch dazu angeregt, das alte Modula2 Programm aus verstaubten Disketten aufzutauen und in eine modernere C++ Form zu gießen. Die heutige Geschwindigkeit der Rechner tut ein übriges, sodaß in Sekunden Lösungen errechnet werden, die damals Tage oder mehr an Rechenzeit benötigt haben.
In den Jahren dazwischen sind sehr viele interessante Arten von Puzzeln erfunden worden, wovon die meisten sich doch erstaunlicherweise mit dem Logelium berechenbar sind. Es sind aber auch Grenzen erkennbar geworden, die weitere Anregungen bergen. Nach und nach ist das Logelium so zu einem Konzept geworden, mit dem sich für viele Arten von Puzzeln die Lösungen finden lassen.

Das Logelium ist ein ganz privates Projekt, auf jeden Fall kein kommerzielles. Es hat auch keinen ernsthaften wissenschaftlichen Anspruch, sondern soll Spaß und Freude an mathematischen Experimenten und Einsichten bringen. Der Leser mit wenig mathematischen Interessen mag sich einfach an den grafischen Effekten erfreuen.

Die Welt der ganzen Zahlen und damit auch die Geometrie in festen Gittern ist noch immer nicht vollständig verstanden, vielleicht auch nur wenig beachtet. Die mathematischen Methoden, die sich in einem reellen oder komplexen Kontinuum so blendend bewährt haben, eignen sich nur sehr begrenzt, wenn nur ganze Zahlen zulässig sind. Der Ansatz die ganzen oder rationalen Zahlen als Sonderfall aller Zahlen zu betracheten hift nicht wirklich, obwohl das nicht falsch ist. Polynomische Gleichungen P(X₁, X₂, …, X_n) = 0 mit ganzzahligen Koeffizienten, für die nur ganze Zahlen als Lösungen zulässig sind, nennt man Diophantische Gleichungen. Geometrische Figuren in ganzzahligen Gittern gehören auch in diese Kategorie. Die bekannten Pythagoräischen Dreiecke sind das Paradebeispiel. Schon im Altertum hat sich Diophantos (um 250 BC) mit solchen Fragen befaßt. Die Schwierigkeit der Materie ist auch über die Zeit nicht geringer geworden, denn die Frage nach der allgemeinen Lösbarkeit von Diophantischen Gleichungen — Hilberts 10. Problem — ist nicht entscheidbar, wie man seit kurzem weiß.

Wenn man erkennt, dass die Überdeckungsprobleme der Puzzel durch Diophantische Gleichungen beschrieben werden können, befindet man sich schon mitten in einem unübersichtlichen Gelände. Hier lohnt es, zu experimentieren und sich überraschen zu lassen. Das Logelium arbeitet mit Bool'schen Gleichungen und Ungleichungen, dafür aber mit vielen. Die meisten Klassen von Puzzles sind wegen ihrer Endlichkeit natürlich immer theoretisch entscheidbar, selbst wenn die konkrete Berechnung an der immensen Tiefe scheitert. Man findet eine unendliche Endlichkeit vor, die ziemlich furchterregend ist. Die praktische Entscheidbarkeit ist jedenfalls äußerst begrenzt.

Da ich beruflich viel unterwegs bin, habe ich viel Zeit im Flugzeug oder Hotel mit der Erfindung von neuen Logelium Komponenten zugebracht, die sonst mit miserablen Fernsehprogrammen gefüllt worden wäre.

Einen Teil des Materials will ich nun über den Weg des Internets bekannt machen, soweit es meine Zeit zulässt. Dabei wähle ich nur einige Themen aus, welche nicht schon vielfach dargestellt und betrachtet wurden. Es geht mir also überhaupt nicht um Vollständigkeit, sondern darum, einige neue oder wenig beachtete Aspekte von Puzzeln zu beleuchten.

Wenn ich dann auch noch ein paar wache Wesen auf diesem Globus anzusprechen und erfreuen und vielleicht zum mitdenken anzuregen kann, ist der Zweck meiner Motivation schon erreicht. Nach und nach werde ich ausgewählte Kapitel hinzufügen und freue über jeden hilfreichen Kommentar.

Das Logelium findet Lösungen zu Überdeckungsproblemen aller Arten, die auf Figuren in periodischen Gittern beruhen. Die Gitter können zwei- oder auch drei-dimensional sein. Mit mehr Dimensionen habe ich noch nicht gearbeitet, obwohl ich außer der anschaulichen Darstellung kein prinzipielles Problem sehe. Das ganze hat einen sehr experimentellen Charakter, da die Auswahl der Puzzel und der Formen nach subjektiven Kriterien geschieht.

Hier einige Beispiele mit allen Lösungen (PDF):

TriTetraTan	Pentomino	B-Tetromino	Delta-Tri-Stick	Hexiamond

Die grundsätzliche Methode ist Brute-Force-Backtracking mit einigen Spezialeffekten. Da ich an  P  !=  NP  glaube, erübrigt sich der Versuch, eine magische Formel zu finden, die das vollständige Durchlaufen des Suchbaums vermeidet. Durch Beachtung von Nebenbedingungen wie z.B. Parity lassen sich zwar ganze Zweige des Baums ausschließen, was jedoch nichts an der grundsätzlichen Charakteristik ändert.

Das ursprüngliche Problem wird zuvor von überflüssigen geometrischen Eigenschaften abstrahiert und in eine algebraische Form gewandelt. Dieser Ansatz hat sich als sehr erfolgreich herausgestellt und ermöglicht gleichzeitig die Bearbeitung einer großen Klasse von Puzzeln. Die relativ komplexe Definition der Figuren, die dazu notwendig ist, wird dabei in Kauf genommen.

Im Laufe der Zeit haben sich mehrere Varianten entwickelt, die deutlich unterschiedlich schnell arbeiten. Wie allgemein bekannt ist, spielt dabei die Wahl der Datenstrukturen und eine große Rolle. Gute Programmiertechnik ist natürlich auch wichtig, um Geschwindigkeit zu erreichen. Weiterhin sind die Kriterien zum Erkennen von Zweigen des Suchbaums, die keine Lösung haben können, ein wichtiges Instrument. Für die Betrachtung der Effizienz sind natürlich diejenigen Probleme am interessantesten, für die sich alle Lösungen finden lassen. Nur durch die vollständige Suche durch den Baum hat man eine Basis, welche die verschiedenen methodischen Ansätze vergleichbar macht.

Der generelle Leitgedanke besteht eher darin, die Möglichkeiten der Methode auszuloten, als für Aufgabenstellungen spezialisierte Lösungsverfahren zu finden. Die untersuchten Varianten sind daher nicht spezifisch für ein Puzzel, sondern immer generisch angelegt.

Bei Experimentieren mit Problemen mit vielen Figuren, wobei "viel" da schon bei 50 anfängt, bekommt man schnell einen Eindruck von der unermesslichen Tiefe der Suchräume. Auch mit den heute verfügbaren Rechnern wird schnell die Grenzen des Machbaren erreicht. Ich wünsche mir immer noch einen Rechner mit der 10¹⁰⁰-fachen Leistung zum nächsten Geburtstag. Aber da müssen wir alle wohl noch warten.

Impressum