Der Algorithmus des Logelium hat sich über die Zeit weiterentwickelt. Der erste Ansatz war ein Netz von sich gegenseitig verbundenen Zellen, die das Gitter darstellen. Die Figuren kann man dann als Pfade darstellen, die in diesem Netz navigieren. Es stellte sich schnell heraus, dass diese Modellierung zwar eine schöne Abstraktion von vielen Puzzeln ist, jedoch bei der Umsetzung in ein Programm nicht zur besten Ablaufgeschwindigkeit führt. Daher wurden Bitreihen zur grundlegenden Datenstruktur für die Darstellung der Figuren ausgewählt.
Die Grundzüge des Logelium Algorithmus sollen in folgenden am Beispiel des TriTetraTan Puzzel erläutert werden. Jedes Puzzel hat seine eigene Abbildung in die Logelium Datenstruktur. Diese Abbildung wird vollständig durch eine generische Konfiguration bestimmt und ist in einigen Fällen auch recht trickreich.
Die 18 Figuren des TriTetraTan Puzzel bestehen aus den vier TriTans A,B,C,D und den 14 TetraTans. Diese Figuren passen in ein Quadratgitter, wobei jedes Gitterelement in beiden Diagonalen geschnitten ist.
Jede TriTetraTan Figur kann in dem Quadratgitter bis zu acht Lagen einnehmen, die durch drehen und spiegeln der Figur entstehen. Die Lagenzahl kann in anderen Gittern auch anders sein. Die Lagen aller Figuren sind in der Figurenkonfiguration des Logelium bereits hinterlegt. Zum einen ist diese Information für ein Puzzel statisch und unabhängig von der zu lösenden Form, zum andern kann man zum z.B. leicht eine Version mit einseitigen Figuren herstellen, indem man die gespiegelten Lagen zu einer eigenen Figur macht.
Das nächste Bild zeigt die Lagen der Figur »Q« der TriTetraTans.
Wenn die Figur symmetrisch ist, sind nicht alle Lagen verschieden. Somit hat »X« nur eine Lage, »H« zwei, »B«, »D«, »I«, »M«, »R«, »S«, »V«, »W« und »Z« haben vier Lagen.
In der zu lösenden Form kann nun jede Figur in einer Lage viele Positionen einnehmen, die durch X-Y-Koordinaten beschrieben werden. Dabei wird die erste Zelle von unten nach oben und von links nach rechts als Ursprungspunkt angesehen.
Beispielnotation: Q.1@3.1 ( Figur »Q«, Lage 1, Position X=3 Y=1 )
Das System von Zellen und Atomen ist recht flexibel und erlaubt die Modellierung sehr vieler verschiedener Puzzelarten. Die Zellen sind durch den Spalten- und Reihen-Index eindeutig benannt. Innerhalb jeder Zelle gibt es mindestens ein Atom, in unserem Fall in der Regel vier und manchmal zwei. Jedes Atom der Form ist entweder ganz oder gar nicht überdeckt.
Das Bild unten zeigt eine Lösung mit TriTetraTans und die Nummerierung der Atome, die mit den Zellen von unten nach oben und von links nach rechts erfolgt und innerhalb der Zellen eine feste Reihenfolge hat.
Jede Position einer Figur kann durch die enthaltenen Atome beschrieben werden, die im Logelium durch eine Bitreihe dargestellt werden. Die 136 Atome der zu lösenden Form bilden auch eine Bitreihe, welche die Summe der Bitreihen der einzelnen Positionen ist. Die folgende Liste beschreibt arithmetisch die obige Lösungsgleichung, wobei die Bitreihen hexadezimal (MSB) notiert sind.
Z.1@1.1 A00000F0 00014000
00000000 00000000 00
K.2@1.1 5F00000C 00000000 00000000 00000000 00
Q.1@3.1 00F00001 68000000 00000000 00000000 00
F.1@4.1 000F0000 17000000 00000000 00000000 00
H.1@5.1 0000FF00 00000000 00000000 00000000 00
R.3@3.2 00000002 800017C0 00000000 00000000 00
C.3@5.2 00000000 00F00005 00000000 00000000 00
M.3@6.2 00000000 000C0000 F0000140 00000000 00
G.8@1.3 00000000 0002A800 05C00000 00000000 00
B.1@4.3 00000000 00000030 000F0000 00000000 00
I.6@5.3 00000000 0000000A 00001680 00050000 00
V.3@1.4 00000000 00000000 0A300017 00000000 00
S.2@4.4 00000000 00000000 0000E800 17000000 00
W.4@1.5 00000000 00000000 00000028 0000FA00 00
X.1@2.5 00000000 00000000 00000000 E80005C0 00
D.1@4.5 00000000 00000000 00000000 00C0003C 00
J.2@5.5 00000000 00000000 00000000 003A0003 C0
A.3@5.6 00000000 00000000 00000000 00000000 3F
Jedes Gittersystem hat natürlich eine spezifische Systematik der Anordnung von Zellen und Atomen. Diese können hier nicht alle aufgezeigt werden. Dreidimensionale Gitter werden z.B. in Schichten zerlegt, die dann nacheinander zweidimensional betrachtet werden. Dies unterstützt dann auch die grafische Darstellung als Tableau. Für manche Puzzel gibt es auch verschiedene Möglichkeiten der Modellierung.
Bein Einlesen der Textdatei, welche die zu lösende Form beschreibt, wird die zugehörige Puzzel- und Gitterdefinition ermittelt. Die Gültigkeit aller Parameter und der Formbeschreibung wird geprüft und eine Liste der Zellen mit allen Eigenschaften aufgebaut. Alle Figuren mit allen Lagen werden geprüft und bereitgestellt.
Es werden sämtliche Positionen von allen Figuren in allen Lagen berechnet und als Bitreihe abgelegt. Dies kann bei großen Puzzeln zu erheblichem Speicherbedarf führen. Für jedes Atom werden zwei Listen angelegt, welche die Positionen referenzieren. Die Hauptliste enthält alle Positionen, welche das betreffende Atom berühren und die Nebenliste diejenigen, für welche der Atomindex minimal ist. Über die Nebenliste ist jede Position eindeutig einem Atom zugeordnet.
Zur Berücksichtigung der Symmetrie der Form werden alle überzähligen Positionen der Lagen einer ausgewählten Figur gestrichen, die sich durch Drehen oder Spiegeln ineinander abbilden lassen. Die betreffende Figur muss dabei die volle Ausprägung aller möglichen Lagen besitzen. Diese Methode ist nur für zweiseitige Figurensätze ohne doppelte Figuren anwendbar.
Weiterhin werden alle Positionen gestrichen, für welche es keine Fortsetzung gibt, da diese unter keinen Umständen Teil einer Lösung sein können. Dies ist zum Beispiel der Fall, wenn kleine Bereiche abgeschnitten sind. Um eine Position zu behalten, muss es zu jedem freien Atom mindestens eine weitere geben, die sich zusätzlich zu dieser in die Form setzen lässt. Dies Verfahren wird rekursiv so lange fortgesetzt, bis eine stabile Teilmenge von Positionen übrig bleibt.
Je mehr Positionen ausgeschlossen werden können, um so effektiver ist das anschließende Verfahren.
Bei der obigen Form des TriTetraTan Puzzel werden wegen der zweifachen diagonalen Spiegelsymmetrie nur die Lagen 1+2 der Figur »K« verwendet.
Im Schritt 2 und 3 ergeben sich insgesamt 1331 Positionen der 18 Figuren, die im Schritt 4 um 191 auf 1140 vermindert werden können.
Im allereinfachsten Fall wird zu jedem Rekursionsschritt jeweils der kleinste freie Atomindex gesucht und dann die Positionen der zugehörigen Nebenliste der Reihe nach verwendetet, um zu versuchen, diese in die Form zu setzen. Da es sicher ist, dass bei diesem Vorgehen immer alle Atome mit kleinerem Index bereits besetzt sind, genügen die Positionen der Nebenliste.
Das Prüfen der Positionen geht sehr schnell, da nur logische UND Operationen, die für einen Rechner elementar sind, Anwendung finden. Ist die Prüfung positiv, kann also eine Position gesetzt werden, wird die nächste Rekursionsstufe angefangen. Zum Setzen der Position ist eine logische ODER Operation erforderlich, die auch rechnertechnisch elementar ist. Zuvor wird die Ausgangssituation gesichert.
Eine Lösung ist natürlich gefunden, wenn keine freien Bits mehr vorhanden sind. Sind auf einer Stufe sämtliche Positionen einer Liste samt allen rekursiven Folgestufen abgearbeitet, wird auf die vorige Stufe zurückgegangen, um dort mit der nächsten anstehenden Position fortzusetzen.
Dies Verfahren ist unter dem Terminus Backtracking bekannt.
Parallel zum Ablauf der Backtracking-Rekursion können nebenläufige Bedingungen geprüft werden, welche zu jeder Zeit erfüllt sein müssen. Dazu eignen sich alle Bedingungen, die einen Zahlenwert ermitteln, welche sich mit dem Setzen der Positionen aufaddieren. Damit ist dann auch für jede Lösung der Bedingungswert der ganzen Form gleich der Summe der Werte der enthaltenen Positionen. Somit lässt sich auf jeder Stufe prüfen, ob der Zielwert mit den restlichen zur Verfügung stehenden Teilwerten überhaupt erreicht werden kann.
Die wichtigsten solcher Bedingungen sind sogenannte Paritäten, wovon wiederum die Schachbrettparität die einfachste ist. Diese hat je nach Position positive oder negative Werte, wobei aber der absolute Wert nur von der Figur abhängt. Die Schachbrettparität berechnet sich als Summe der Atome auf gedachten weißen Zellen minus Summe der Atome auf schwarzen Zellen.
Es ist äußerst effektiv, Bedingungen zu kennen, die für eine Zwischenlösung ausschließen, dass diese Teil einer ganzen Lösung ist. Auch hier ist das Abschneiden von kleinen Bereichen ein sehr anschauliches Beispiel. Denn sobald das geschehen ist, macht die Fortführung der Rekursion keinen Sinn.
Trotz der guten Absicht ist die Erkennung von Sackgassen zweischneidig, da durch ständige aufwändige Prüfungen während der Rekursion der mögliche Gewinn gemindert wird. Damit besteht sehr leicht die Gefahr, dass die Sackgassenerkennung kontraproduktiv wird. Die Aufwände dieser Prüfungen müssen also sehr sorgfältig ausbalanciert werden.
Es gibt ab und zu Gründe von der oben beschriebenen Reihenfolge der Atome für den nächsten Schritt abzuweichen. Ein Extremfall liegt vor, wenn es für ein Atom überhaupt nur noch eine einzige Position gibt. Diese Position ist dann erzwungen und es macht keinen Sinn, die zugehörige Figur an anderer Stelle zu verwenden. Eine Verallgemeinerung dieser Idee besteht darin, das Atom mit der kleinsten Anzahl von gültigen Positionen zu finden und die Überdeckung dort fortzusetzen. Dadurch wird dynamisch jeweils das nächste zu belegende Atom bestimmt. Dieser Ansatz ist für Backtracking unter dem Terminus "Methode der minimalen Verzweigung" bekannt. Doch auch hier ist der große Rechenaufwand der Überprüfung ein Problem, was natürlich beachtet werden muss. Aus diesem Grund wird das Verfahren nur bis zu einer gewissen Tiefe der Suche genutzt und die weiteren Schritte mit dem Standardverfahren bearbeitet.
Es gibt auch Gründe bestimmte Atome, z.B. Ecken, sofort zu besetzen. Dies kann zusätzlich manuell konfiguriert werden und führt dann zu einer statischen Reihenfolge der betreffenden Atome. Die Option der statischen Reihenfolge sollte immer mit der dynamischen kombiniert werden, da sonst leicht Engpässe entstehen.
Im Verlauf der Backtracking Rekursion mit dem Standardverfahren wurden 69.625.204 Positionen erfolgreich gesetzt.
Es wurden 255.233 Sackgassen erkannt und die Rekursion vorzeitig abgebrochen.
Insgesamt wurden 31 Lösungen (PDF) gefunden.
Die Frage, ob und wann man dem Ergebnis einer rechnergestützen Suche nach Lösungen trauen kann, ist eine wirklich schwierige Frage. Bei einer sehr großen Anzahl von Lösungen läßt sich selbst die Aussage, daß alle Lösungen korrekt sind, wiederum nur rechnergestützt bestätigen. Das gleiche gilt für die Frage, ob alle gefundenen Lösungen wirklich verschieden sind.
Zudem ist die Fragestellung der Glaubwürdigkeit vielschichtig und am Ende bleiben immer noch Fragen übrig.
Zunächst muß man sicher sein, daß das Konzept der Modellierung des Puzzels und das Konzept des Algorithmus fehlerfrei ist. Dies ist schon nicht einfach, bewegt sich aber im Rahmen üblicher mathematischer und logischer Überlegungen. Der theoretische Beweis der Richtigkeit ist ohnehin nicht möglich, wie man weiß.
Natürlich kann man das Konzept sehr schlicht gestalten, doch die Notwendigkeit zur Optimierung (z.B. dem oben beschiebenen Erkennen von Sackgassen) lassen das Konzept sehr schnell komplex und unübersichtlich werden. Man ist halt kein unsterblicher Gott, sondern will das Ergebnis doch noch innerhalb der eigenen Lebenszeit erfahren.
Die Programmierung formt das Konzept zu einer in einer technischen Programmiersprache geschriebenen Code um. Jeder der solch eine Unternehmung kennt, weiß wie viele Fehler sich selbst bei äußerster Sorgfalt einschleichen können. Dabei sind diejenigen Fehler besonders tückisch, welche nur in besonderen Konstellationen in Erscheinung treten und daher besonders subtil sind und lange unerkannt bleiben können. Nicht unerwähnt bleiben soll auch die Möglichkeit, daß die ausführende Hardware während der langen Laufzeit des Programms fehlerhaft arbeitet.
Was bleibt, ist: testen, testen, testen. Das heißt einerseits Vergleichen mit manuell ermittelten Lösungen kleiner Formen und auch Vergleich mit den Ergebnissen unabhängiger Konzepte und Programme. Auf diese Weise entsteht eine wachsende Glaubwürdigkeit des Lösungsmechanismus. Da der Logelium Algorithmus in sich unsymmetrisch ist, hilft auch der Kreuzvergleich von gedrehten oder gespiegelten Formen. Diese müssen natürlich immer zum selben Ergebnis führen.
Am Ende stellt man fest, daß man den Grad der Glaubwürdigkeit zwar erhöhen kann, aber die 100% sind grundsätzlich unerreichbar. Dieses Grundsätzliche mag einem nicht gefallen, fußt aber auf einer theoretischen Ursache der Grenze der praktischen Berechenbarkeit. Philosophisch betrachtet stellt sich sofort die Frage nach der Grenze der Erkenntnis überhaupt. Meiner Ansicht nach wird jede Erkenntnis mit wachsender Komplexität immer unsicherer. Daß ich dabei die Glaubwürdigkeit von Puzzle-Logik kühn auf alle Erkenntnisprozesse generalisiert habe, ist schon klar.