Fünfzehnerspiel auf Torus

Das klassische Spiel

Das klassische Fünfzehnerspiel, auch Boss-Puzzle genannt, bsteht aus einer quadratischen Anordnung von Steinen mit den Aufschriften 1 bis 15 einschliesslich einem leeren Feld. Die Aufgabe ist nun, aus einer ungeordneten Anordung die Steine in eine geordnete zu bringen, in den meisten Aufgaben mit der 1 links oben und dem leeren Feld rechts unten. Dazu kann immer nur ein benachbarter Stein in das leere Feld bewegt werden

Spiel

Zwei klassische alte und selbst gefertigte Fünfzehner- Schiebespiele aus meiner Sammlung.

Spiel

Der Vollständigkeit wegen sei ergänzt, dass zu Werbezwecken manchmal an Stelle der Zahlen auch Buchstaben oder eine Zeichnung verwendet wurden.
Es existieren zahlreiche Beschreibungen des Spiels, z.B. in [2], sowie eine lesenswerte Darstellung seiner Geschichte von Slocum und Sonneveld mit zahlreichen Abbildungen [1]. Auch die Probleme der Lösbarkeit und die Strategien zur Bestimmung von Lösungen mit den wenigsten Zügen werden im Internet behandelt [3]..

Die neue Geometrie

Noch interessanter wird das Spiel, wenn man seine Geometrie ändert, indem die vier Seiten des Feldes miteinander verbunden werden. Naheliegend ist die Verbindung des rechten mit dem linken Rand und des oberen mit dem unteren. Die Steine können dann eine Begrenzung überschreiten und treten an der gegenüber liegenden wieder ein - sofern ein leeres Feld diese Bewegung zulässt. Diese Zuordnung lässt sich auch dreidimensional beschreiben indem man sagt, das Spiel liegt auf einem Ring, auch Torus genannt
Eine solche Anordnung ist für Ungeübte schwer vorstellbar, deshalb zeige ich hier eine Animation, die das Entstehen der Anordnung verdeutlicht. Verwendet wird dabei ein ebenes Feld 8 x 8 und nicht 4 x 4, aber das Prinzip bleibt das gleiche.

Video: Das ebene Spielfeld wird zu einem Torus
Quelle: Wikipedia Torus

Technisch ist soetwas nicht ausführbar, weil sich beim Verschieben die Krümmung der Steine ständig ändern müsste. Man kann sich jedoch damit behelfen, dass man bei der zweidimensionalen Darstellung auf dem Bildschirm bleibt und diese so programmiert als würdem sich die Steine bewegen wie auf einem Torus.

Unter dem Begriff Torus Puzzle existieren ähnliche Spiele ohne ein leeres Feld, man kann daher nur ganze Zeilen oder Spalten verschieben, eine Art 2D-Version von Rubik's Cube. Diese Variante ist hier nicht gemeint.

Das einzige mir bekannte Programm (Kenntnisstand Juli 2021), das ein Fünfzehnerspiel mit freiem Feld auf Torus nachahmt ist das Boss-Puzzle auf der Webseite www.tan-gram.de [4] von Kollegin Barbara Haeberlin. Diese Webseite ist schon allein wegen ihres Inhalts und seiner Darstellung absolut lesenswert.

Ich gebe rundweg zu, den Quellcode studiert und mit Erlaubnis der Autorin (danke) und mit einigen Änderungen versehen für das nachfolgende Programm verwendet zu haben.

für dieses Spiel muss Javascript aktiviert sein
Basisprogramm aus www.tan-gram.de

Eine kurze Anleitung:

-- reset setzt die Stellung der Steine zurück, sollte auch benutzt werden
wenn keine roten Steine angezeigt werden,
-- mixer erzeugt eine durchmischte Anordnung der Steine,
-- rechteck gibt ein ebenes Spielfeld,
-- torus erstellt die oben besprochene Geometrie,
-- rote Steine sind jene, die mit einem Klick bewegt werden können.

Man erkennt sehr schnell, dass in einem normalen (ebenen) 15-Puzzle ein leeres Feld 2 oder 3 oder 4 Nachbarn zum Ziehen haben kann wäherd im 15-Puzzle Torus ein leeres Feld immer 4 Nachbarn besitzt. Des weiteren sind die Freiheiten für Züge auf dem Torus grösser. Da stellt sich die Frage, worin sich die Lösungen für identische Ausgangsstellungen unterscheiden.

Da ich bereits ein Programm zum Lösen eines ebenen 4 x 4 Puzzles mit möglichst wenigen Zügen geschrieben hatte (Strategie depth-first search with sum of Manhattan distances), war es leicht, dieses nach einigen Änderungen dem Spiel auf Torus anzupassen.

Lösungen

Die Ausgabgsstellungen sind als Zahlenfolge der Steine in der 1. Reihe von links nach rechts, danch in der 2. Reihe von links nach rechts usw. angegeben. Eine Null markiert die freie Stelle. In dieser Form lassen sich Stellungen am einfachsten mit einem Programm einlesen und ausgeben.

Point 1. Beispiel: 15,14,12,13,8,11,10,9,4,7,6,5,3,2,1,0
-eben: 1 Lös. mit mind. 72 Zügen:

5 9 13 12 10 11 14 15 8 4
7 14 15 8 4 7 3 2 1 5
9 13 11 15 7 3 2 1 5 9
13 11 15 10 8 4 3 2 1 5
9 13 11 15 12 8 4 3 2 1
5 9 13 11 15 12 8 4 3 2
1 5 9 13 14 6 10 7 6 10
11 15

-Torus: 1 Lös. mit mind. 36 Zügen:
3,15,13,3,1,12,10,6,12,10,14,2,10,14,3,1,15,4,5,9,8,5,9,12,7,11,6,7,11,10,14,15,4,13,1,4,

Point 2. Beispiel: 4,8,12,15,3,6,7,14,2,10,11,13,1,5,9,0
-eben: 1 Lös.mit mind.36 Zügen:

13 14 15 12 8 4 3 2 1 5
9 13 14 15 12 8 4 3 2 1
5 9 13 14 15 12 8 4 3 2
1 5 9 13 14 15

-Torus: 4 Loes mit mind. 32 Zügen:
L.1
15,12,8,4,3,14,12,8,4,3,14,2,1,5,9,15,13,12,8,4,3,14,2,1,5,9,14,2,1,5,9,13,
L.2
9,12,15,4,3,14,4,3,8,5,1,2,14,8,5,1,2,14,13,9,12,15,3,4,8,5,1,2,14,13,9,12,
L.3
9,12,15,14,3,4,8,5,1,2,13,9,14,3,4,8,5,1,2,14,12,15,3,4,8,5,1,2,14,13,9,12,
L.4
9,12,15,14,3,4,8,5,1,2,13,9,12,15,14,3,4,8,5,14,3,4,8,5,2,1,14,2,1,13,9,12,

Point 3. Beispiel:
-eben: 0,12,9,13,15,11,10,14,7,8,5,6,4,3,2,1
benötigt zur Lösung 80 Züge (s.a. [3a])

-Torus: 18 Loes mit mind. 44 Zügen:
L.1
12,9,13,12,4,1,12,4,15,7,6,14,7,6,8,5,14,8,5,14,10,11,9,13,2,3,13,15,1,13,15,2,3,15,14,9,6,5,9,10,11,7,8,12,
L.2
12,9,13,12,4,1,12,4,15,7,6,14,7,6,14,5,8,14,5,8,10,11,9,13,2,3,13,15,1,13,15,2,3,15,14,9,6,5,9,10,11,7,8,12,
L.3
12,9,13,12,4,1,12,4,15,14,6,7,8,5,10,11,14,6,7,8,5,14,9,13,2,3,13,15,1,13,15,2,3,15,14,9,6,5,9,10,11,7,8,12,
L.4
12,9,13,12,4,1,12,4,15,14,6,7,8,11,14,6,7,5,11,14,9,13,2,3,13,15,1,13,15,2,3,15,14,9,10,7,5,8,9,10,6,5,8,12,
L.5
12,9,13,12,4,1,12,4,15,14,6,7,14,6,7,5,8,14,5,8,10,11,9,13,2,3,13,15,1,13,15,2,3,15,14,9,6,5,9,10,11,7,8,12,
L.6
12,9,13,12,4,1,12,4,15,14,6,5,8,11,14,7,5,8,11,14,9,13,2,3,13,15,1,13,15,2,3,15,14,9,10,6,7,5,9,10,6,7,8,12,
L.7
12,9,13,12,4,1,12,4,15,14,6,5,10,11,14,7,8,14,9,13,2,3,13,15,1,13,15,2,3,15,14,10,11,6,7,9,6,7,5,8,9,5,8,12,
L.8
12,9,13,12,4,1,12,4,15,14,6,5,10,11,14,7,8,14,9,13,2,3,13,15,1,13,15,2,3,15,14,9,7,6,5,8,9,10,11,7,6,5,8,12,
L.9
12,9,13,12,4,1,12,4,15,14,6,5,10,11,14,6,5,7,8,14,9,13,2,3,13,15,1,13,15,2,3,15,14,9,6,5,7,8,9,10,11,7,8,12,
L.10
12,9,13,12,4,1,12,14,15,7,8,11,10,15,6,5,11,10,9,3,2,13,15,6,7,9,6,7,5,8,9,5,8,12,14,4,1,14,13,15,3,2,14,13,
L.11
12,9,13,12,4,1,12,14,6,7,8,5,10,11,15,6,7,8,5,15,9,3,2,13,3,2,15,9,6,5,9,10,11,7,8,12,14,4,1,14,13,15,14,13,
L.12
12,9,13,12,4,1,12,14,6,7,8,11,15,6,7,5,11,15,9,3,2,13,3,2,15,9,10,7,5,8,9,10,6,5,8,12,14,4,1,14,13,15,14,13,
L.13
12,9,13,12,4,1,12,14,6,7,15,6,7,5,8,15,5,8,10,11,9,3,2,13,3,2,15,9,6,5,9,10,11,7,8,12,14,4,1,14,13,15,14,13,
L.14
12,9,13,12,4,1,12,14,6,5,8,11,15,7,5,8,11,15,9,3,2,13,3,2,15,9,10,6,7,5,9,10,6,7,8,12,14,4,1,14,13,15,14,13,
L.15
12,9,13,12,4,1,12,14,6,5,10,11,15,7,8,10,11,15,9,3,2,13,15,6,7,9,6,7,5,8,9,5,8,12,14,4,1,14,13,15,3,2,14,13,
L.16
12,9,13,12,4,1,12,14,6,5,10,11,15,7,8,15,9,3,2,13,3,2,15,10,11,6,7,9,6,7,5,8,9,5,8,12,14,4,1,14,13,15,14,13,
L.17
12,9,13,12,4,1,12,14,6,5,10,11,15,7,8,15,9,3,2,13,3,2,15,9,7,6,5,8,9,10,11,7,6,5,8,12,14,4,1,14,13,15,14,13,
L.18
12,9,13,12,4,1,12,14,6,5,10,11,15,6,5,7,8,15,9,3,2,13,3,2,15,9,6,5,7,8,9,10,11,7,8,12,14,4,1,14,13,15,14,13,

Die Beispiele zeigen, dass das Fünfzehnerspiel auf Torus wegen der grösseren Zahl von Zugmöglichkeite mit jedem Stein mit einer geringeren Zahl von Zügen in der Lösung auskommt.
Eine vollständige mathematisch-theoretische Behandlung steht noch aus

Zugabe

In diesem Online-Spiel lief beim Ziehen der 15 nach rechts etwas schief:

Fünfzehnerspiel

Der Grund ist sofort erkennbar: die Javascript-Schachtel liegt nicht waagerecht.

Literatur, Webseiten

[1] Jerry Slocum, Dic Sonneveld: The 15 Puzzle: How it Drove the World Crazy. 2006
dazu: Rezension

[2a] Wikipedia 15-Puzzle,

[2b] Mathematische Basteleien Fünfzehnerspiel

[3a] Kociemba 15-Puzzle Optimal Solver,

[3b] Takahashi 15puzzle Optimal solver

[3c] DelphiForFun 15Puzzle

[4] Tan-gram >Spiele >Boss

xxx