Fünfzehnerspiel

Das Spiel besteht aus 15 kleinen Quadraten mit den Zahlen 1 bis 15. Diese können in einem quadratischen Rahmen mit 4x4 Feldern horizontal und vertikal verschoben werden, wobei das leere Feld als Ausweichplatz dient. Die Aufgabe besteht darin, von einer beliebigen Anordnung der 15 Zahlen mit dem leeren Feld rechts unten die Grundstellung mit allen Zahlen in der richtigen Reihenfolge und dem leeren Feld rechts unten zu erreichen.

Geschichte

Das Spiel, auch Boss-Puzzle genannt, wird in den USA in den 1870er Jahren erfunden und verbreitet sich sehr schnell. Sein Erfolg ist mit demjenigen des Rubik-Würfels in den 1980er Jahren vergleichbar.

Um 1880 stellt Sam Loyd das unter dem Namen 14-15-Puzzle bekannte Problem: In der Ausgangsstellung stehen alle Zahlen in der richtigen Reihenfolge mit Ausnahme von 14 und 15, die vertauscht sind. Für die Lösung des Problems setzt Sam Loyd einen Preis von 1000 US $ aus. Viele beteiligen sich am Wettbewerb, aber niemand gewinnt, weil das Problem unlösbar ist.

Mathematik

Es gibt ein einfaches Kriterium um festzustellen, ob das Problem lösbar ist: Man denkt sich die 4 Zeilen nacheinander angeordnet und zählt jeweils die Paare von Zahlen, die in der falschen Reihenfolge sind. Ist die Anzahl gerade, ist das Problem lösbar, andernfalls ist es nicht lösbar. In mathematischer Sprache kann das Kriterium so beschrieben werden: Bei einer vollständig ausgeführten Bewegung (mit dem leeren Feld rechts unten) bleibt die Parität der Permutation der Zahlen 1 bis 15 erhalten. Da die Grundstellung eine gerade Permutation ist, sind nur Ausgangsstellungen lösbar, die ebenfalls gerade Permutationen sind. Offen bleiben allerdings die Fragen, wie viele Schritte nötig sind und wie man die Aufgabe mit der kleinsten Anzahl Schritte löst.