Dieses Puzzle hat eine wirklich spektakuläre Geschichte, denn es ging auch um viel Geld für die erste Lösung. Das Geduldspiel ist höllisch schwer, es wurde selbst für den Computer als unlösbar betrachtet und dann wurde es von zwei Mathematikern gelöst! Aber der Reihe nach. Es handelt sich um Eternity aus dem Jahr 2009:
209 Teile sollen einen nahezu regelmäßigen zwölfeckigen Rahmen vollständig füllen. Dem Rahmen liegt ein regelmäßiges Dreieckgitter zugrunde.
Die 209 Teile bestehen jeweils aus 12 Hälften der gleichseitigen Elementardreiecke, die entlang ganzer oder halber Kanten entlang von Gitterlinien zusammengefügt wurden. Solche Teile heißen heute Polydrafter, da im Englischen ein Drafter ein Zeichendreieck mit den Winkeln von 30, 60 und 90 Grad bezeichnet. Polydrafter aus 12 Draftern heißen Dodekadrafter. Früher hießen diese Teile auch Dodecadudes. Hier einige der 209 Teile:
Es gibt viele Dodekadrafter, die für solch ein Puzzle ungeeignet erscheinen: Steine mit Löchern können nicht verwendet werden, Steine mit nach außen ragenden spitzen 30-Grad-Winkeln bergen eine Verletzungsgefahr, symmetrische Steine machen das Spiel einfacher und werden deshalb verboten usw. Übrig bleiben insgesamt 770 verschiedene Dodekadrafter [1]. 209 davon wurden für das Puzzle ausgewählt. Weil üblicherweise Polyformpuzzles schon mit 30 Steinen auch für Computer anspruchsvoll sind, konnte man annehmen, dass es mit 209 Teilen praktisch unlösbar wird. Deshalb wurde vom Erfinder Christopher Monckton ein Preisgeld von einer Million britischer Pfund für die Lösung des Puzzles ausgesetzt [2]. Es war bekannt, dass es mindestens eine Lösung gibt, diese lag im Tresor des Erfinders.
Aber es stellte sich als Denkfehler heraus, dass derartige Polyformpuzzles mit wachsender Steinzahl durch exponentielles Wachstum immer komplizierter werden [3]. Dies gilt zumindest, wenn es insgesamt sehr viele Lösungen gibt und man nur nach einer Lösung davon sucht. Und hier gibt es sehr viele Lösungen, deren Zahl wird mittlerweile auf mindestens 10⁸⁰ geschätzt. Die erfolgreiche Lösungsstrategie war folgendermaßen:
Erstens werden die 209 Steine entsprechend ihrer Nützlichkeit grob sortiert. Zweitens stellte man fest, dass sich mit 70 einigermaßen nützlichen Steinen viele der kompakt geformten Rahmen mit einer Fläche von 420 Elementardreiecken des Gitters vollständig füllen lassen.
Damit war das weitere vorgehen klar: Man versucht im ersten Schritt den Rahmen zu rund zwei Dritteln zu füllen, indem man möglichst wenige der nützlichsten Steine verwendet. Der dafür notwendige Aufwand hängt näherungsweise linear von der Größe der Fläche ab und nicht exponentiell wie vermutet. Da man immer mehr Steine zur Verfügung hat als nötig, kann schnell der nächste Stein eingebaut werden. Für die letzten 70 Steine hat man die Hoffnung, dass sich die Restfläche mit den 70 Steinen, von denen viele sehr nützlich sind, auch füllen lässt. Hier ist eine komplexere Analyse mit Backtracking nötig, aber die Chancen stehen nicht schlecht, zumindest bei mehreren Versuchen eine Lösung zu finden.
Wie könnten die Steine für das Eternity-Puzzle ausgewählt und die dazugehörige Lösung gefunden worden sein? Eine ganz einfache Möglichkeit ist die folgende: Zunächst wählen wir eine deutlich zu große Steinmenge, z.B. alle nicht-symmetrischen Dodekadrafter. Mit diesen Steinen zur Auswahl wird der Rahmen gefüllt. Wenn die Steinmenge deutlich größer ist als nötig, dann ist dies ganz einfach, der Computer findet schnell passende Steine. Alle übrigen Steine werden weggeworfen und fertig ist das Puzzle: Wir haben eine scheinbar zufällig ausgewählte Steinmenge und eine Lösung für den Tresor [4]. Das das Puzzle so extrem schwer erschien, wurde als "Hilfe" die Position des Steins Nr. 34 im Rahmen angegeben. Dies war die Position dieses Steins in der einzig bekannten Lösung und es wurde nicht verlangt, dass dieser Stein unbedingt dort liegen muss. Tatsächlich sind bisher mehrere Lösungen von Eternity bekannt, und der Stein Nr. 34 liegt niemals an diese Position. Die Lösung von Christopher Monckton aus dem Tresor ist nicht öffentlich bekannt.
Auf Grund des spektakulären Preisgeldes erzielte das Eternity-Puzzle einen Verkaufsrekord: Im ersten Monat war Eternity das meistverkaufte Spiel aller Zeiten in Großbritannien, in den ersten beiden Jahren wurden rund 225.000 Exemplare verkauft [5]. Die Mathematiker Alex Selby und Oliver Riordan fanden am 15. Mai 2000 eine Lösung und erhielten den Preis im September des Jahres. Im Video [6] erklärt Oliver Riordan, wie sie Eternity gelöst haben.
Design: Christopher Monckton
Hersteller: Ertl Europe Company
Erscheinungsjahr: 1999
Shopping: Gelegentlich gebraucht lieferbar, Preis ca. 20€
