Quadro - Ein Puzzle mit nur 12 Teilen


Wenn man dieses Puzzle zum ersten Mal sieht, denkt jeder: Na ja eine Nachmittagsbeschäftigung, dann ist das Problem gelöst. Die zwölf Teile sind auf einem Schachbrett unterzubringen, ohne dass dabei eines der Teile über das Spielfeld hinausragt.

Spielfeld des Puzzles Quadro mit seinen 12 Teilen

Ich habe dieses Spiel durch meinen Bekannten, Herrn Fleischhammer, kennen gelernt. Er war schon pensioniert und ist in dem gleichen Computerclub Mitglied, in dem auch ich Mitglied bin. Er hatte wiederum einen anderen Bekannten, der eines Tages die Idee hatte aus einer Sperrholzplatte, auf die er ein Schachbrett aufgemalt hatte, ein Puzzle mit 12 Teilen zu fertigen.  Gesagt, getan! Das Puzzle war fertig. Aber er hatte sich keine Skizze zur ursprünglichen Lage der Puzzleteile gemacht. Er hatte genauso wie viele seiner Bekannten, die sich dann in den folgenden Monaten mit diesem Problem befasst haben, dieses Problem unterschätzt.

Wer das Problem rechnerisch erfasst erkennt, dass jedes der Teile in vier unterschiedlichen Stellungen auf dem Schachbrett platziert werden kann. Die Anzahl der Permutationen (möglichen Kombinationen) beträgt also 48! (Fakultät), ca 10 hoch 61 Möglichkeiten, eine 1 mit 61 Nullen, eine unvorstellbar große Zahl. Da schnauft selbst der Taschenrechner.

Man muss also danach suchen, wie die Zahl der Strukturen, die man prüft und weiterverfolgt, klein gehalten werden kann. Dies gelingt mit dem Aufbau einer Baumstruktur. Man fängt oben links mit dem ersten Teil an und versucht ein weiteres Teil anzufügen. Die Zweierkombinationen, wo dies geklappt hat, schreibt man in die erste Zeile einer Liste im Speicher. Nun fügt man an diese Kombinationen jeweils ein weiteres Teil an und muss natürlich dabei jedes Mal prüfen, ob sich das Teil auch lückenlos im Schachbrett einfügen lässt. Die neue Liste wird nun wesentlich länger. Aber wenn man dies geschafft hat, kann man die erste Liste aus dem Speicher löschen. Andererseits wird aber auch die Auswahl der zur Verfügung stehenden Puzzleteile immer geringer. Damit wird es  auch immer schwieriger Teile zu finden, die passen. Die neu angestrickte Liste wächst damit immer langsamer und wird nachdem man ca 6 Teile angefügt hat, mit jedem weiteren Zyklus kürzer. Man kann nun Speicherplatz sparen, indem man erst mal die Liste für alle Möglichkeiten mit 6 Teilen aufbaut und dann bei jeder der so gefundenen Möglichkeiten einzeln überprüft, ob und wie weit sich weitere Teile anfügen lassen. Insgesamt überprüft das Programm 541774 Strukturen und errechnet 16 Lösungen. Allerdings nur 4 grundsätzlich verschiedene Lösungen. Wenn man das Schachbrettmuster auch noch berücksichtigt gibt es nur eine Lösung.

Der Bekannte, der dieses Spiel erfunden hat, hat die Lösung, die ich 1996 in meiner Freizeit erarbeitet habe, leider nicht mehr erlebt. Er war inzwischen an Krebs gestorben. Aber seine Frau lebte noch. Ca ein halbes Jahr dauerte es bis ich das Programm lief. Mehrere Versuche scheiterten an mangelndem Speicherplatz und an den unausweichlichen Logikfehlern, infolge der Komplexität des Problems.

Das Programm ermöglicht es einem natürlich auch selbst die Puzzleteile mit der Maus in jeder gewünschten Richtung auf dem Schachbrett zu platzieren. Download des Programms Quadro Nach dem download einfach die selbstentpackenede Datei Quadro.exe starten und in einen noch nicht vorhandenen Ordner entpacken.


Inhalt

Index

weiter