15 Rätsel

Das 15er-Puzzle (auch bekannt als Edelsteinpuzzle , Bosspuzzle , Spiel der Fünfzehn , Mystisches Quadrat u. a.) ist ein Schiebepuzzle . Es besteht aus 15 quadratischen, von 1 bis 15 nummerierten Spielsteinen in einem Rahmen mit vier Positionen Höhe und vier Positionen Breite, wobei eine Position frei bleibt. Spielsteine ​​in derselben Zeile oder Spalte wie die freie Position können horizontal bzw. vertikal verschoben werden. Ziel des Puzzles ist es, die Spielsteine ​​in numerischer Reihenfolge (von links nach rechts, von oben nach unten) anzuordnen.

Benannt nach der Anzahl der Steine ​​im Rahmen, wird das 15er-Puzzle auch als „16er-Puzzle“ bezeichnet , was auf seine Gesamtsteinkapazität hinweist. Ähnliche Bezeichnungen gibt es für Varianten des 15er-Puzzles in verschiedenen Größen, wie beispielsweise das 8er-Puzzle mit 8 Steinen in einem 3×3-Rahmen.

Das n- Puzzle ist ein klassisches Problem zur Modellierung von Algorithmen mit Heuristiken . Gängige Heuristiken hierfür sind das Zählen der falsch platzierten Spielsteine ​​und die Berechnung der Summe der Taxidistanzen zwischen jedem Block und seiner Position in der Zielkonfiguration. ^{[ 1 ]} Beide Heuristiken sind zulässig . Das heißt, sie überschätzen niemals die Anzahl der verbleibenden Züge, was die Optimalität bestimmter Suchalgorithmen wie A* gewährleistet . ^{[ 1 ]}

Johnson & Story (1879) nutzten ein Paritätsargument , um zu zeigen, dass die Hälfte der Ausgangspositionen des n-ten Puzzles unabhängig von der Anzahl der Züge unlösbar ist. Dazu betrachteten sie eine Binärfunktion der Kachelkonfiguration, die unter jedem gültigen Zug invariant ist , und teilten damit den Raum aller möglichen markierten Zustände in zwei zueinander unzugängliche Äquivalenzklassen gleicher Größe auf. Dies bedeutet, dass die Hälfte aller Positionen unlösbar ist, sagt aber nichts über die verbleibende Hälfte aus.

Die Invariante ist die Parität der Permutation aller 16 Quadrate plus die Parität der Taxidistanz (Anzahl der Zeilen plus Anzahl der Spalten) des leeren Quadrats von der unteren rechten Ecke. Dies ist eine Invariante, da jeder Zug sowohl die Parität der Permutation als auch die Parität der Taxidistanz verändert. Befindet sich das leere Quadrat in der unteren rechten Ecke, so ist das Puzzle nur dann lösbar, wenn die Permutation der verbleibenden Teile gerade ist.

Johnson & Story (1879) zeigten außerdem, dass auf Brettern der Größe m × n , wobei m und n beide größer oder gleich 2 sind, alle geraden Permutationen lösbar sind . Dies lässt sich durch Induktion über m und n beweisen , beginnend mit m = n = 2. Daraus folgt, dass es genau zwei Äquivalenzklassen von zueinander erreichbaren Anordnungen gibt und dass die beschriebene Parität die einzige nichttriviale Invariante ist, obwohl äquivalente Beschreibungen existieren.

Archer (1999) lieferte einen weiteren Beweis, der auf der Definition von Äquivalenzklassen mittels eines Hamiltonschen Pfades basiert .

Wilson (1974) untersuchte die Verallgemeinerung des 15-Puzzles auf beliebige endliche Graphen , wobei das ursprüngliche Problem ein 4×4 -Gittergraph war . Das Problem weist einige Sonderfälle auf, in denen die Lösung entweder trivial ist oder eine einfache Kombination der Lösungen desselben Problems auf Teilgraphen darstellt. Genauer gesagt, für Pfade und Polygone bietet das Puzzle keine Freiheit; ist der Graph unzusammenhängend , ist nur die Zusammenhangskomponente des Knotens mit dem „leeren Raum“ relevant; und existiert ein Verbindungsknoten , reduziert sich das Problem auf dasselbe Puzzle auf jeder der zweifach zusammenhängenden Komponenten dieses Knotens. Abgesehen von diesen Fällen zeigte Wilson, dass es – abgesehen von einem Ausnahmefall mit 7 Knoten – möglich ist, alle Permutationen zu erhalten, es sei denn, der Graph ist bipartit ; in diesem Fall können genau die geraden Permutationen erhalten werden. Der Ausnahmefall ist ein regelmäßiges Sechseck mit einer zusätzlichen Diagonale und einem zusätzlichen Mittelpunkt; nur1/6⁠ seiner Permutationen kann erreicht werden, was ein Beispiel für die exotische Einbettung von S ₅ in S ₆ liefert .

Bei größeren Versionen des n- Puzzles ist die Lösungsfindung einfach. Die Suche nach der kürzesten Lösung ist jedoch NP-schwer . Auch die Approximation der minimalen Anzahl an Zügen mit einer additiven Konstanten ist NP-schwer , es existiert aber eine Näherung mit polynomieller Laufzeit und konstantem Faktor. ^{[ 2 ] [ 3 ]} Beim 15-Puzzle variieren die Längen optimaler Lösungen zwischen 0 und 80 Einzelkachelzügen (es gibt 17 Konfigurationen mit 80 Zügen) ^{[ 4 ] [ 5 ]} oder 43 Mehrfachkachelzügen; ^{[ 6 ]} das 8-Puzzle lässt sich stets mit maximal 31 Einzelkachelzügen oder 24 Mehrfachkachelzügen lösen (Zahlenfolge A087725 ). Bei der Mehrfachkachel-Metrik werden nachfolgende Züge des leeren Feldes in derselben Richtung als ein Zug gezählt. ^{[ 6 ]}

Die Anzahl der möglichen Positionen des 24-Puzzles beträgt ⁠25!/2⁠ ≈7,76 × 10²⁴ , was zu viele sind, um die Gotteszahl mit Brute-Force-Methoden praktikabel zu berechnen ^. Im Jahr 2011 wurden untere Schranken von 152 Einzelkachelzügen bzw. 41 Mehrkachelzügen sowie obere Schranken von 208 Einzelkachelzügen bzw. 109 Mehrkachelzügen ermittelt. ^{[ 7 ] [ 8 ] [ 9 ] [ 10 ]} Im Jahr 2016 wurde die obere Schranke auf 205 Einzelkachelzüge verbessert. ^{[ 11 ]}

Die Transformationen des 15-teiligen Puzzles bilden ein Gruppoid (keine Gruppe, da nicht alle Züge zusammengesetzt werden können); ^{[ 12 ] [ 13 ] [ 14 ]} dieses Gruppoid wirkt auf Konfigurationen.

Da die Kombinationen des 15er-Puzzles durch 3-Zyklen erzeugt werden können , lässt sich beweisen, dass das 15er-Puzzle durch die alternierende Gruppe dargestellt werden kann . ^{[ 15 ]} Tatsächlich kann jedes Schiebepuzzle mit quadratischen Kacheln gleicher Größe durch dargestellt werden . ${\displaystyle A_{15}}$${\displaystyle 2k-1}$${\displaystyle A_{2k-1}}$

Das Puzzle wurde von Noyes Palmer Chapman ^{[ 16 ]} , einem Postmeister in Canastota, New York , „erfunden“. Er soll bereits 1874 Freunden ein Vorläuferpuzzle gezeigt haben, das aus 16 nummerierten Blöcken bestand, die in Viererreihen zusammengesetzt werden sollten, deren Summe jeweils 34 ergab (siehe magisches Quadrat ). Exemplare des verbesserten Puzzles gelangten über Chapmans Sohn Frank nach Syracuse, New York , und von dort über verschiedene Verbindungen nach Watch Hill, Rhode Island , und schließlich nach Hartford , Connecticut , wo Schüler der American School for the Deaf mit der Herstellung des Puzzles begannen. Bis Dezember 1879 wurden diese sowohl lokal als auch in Boston , Massachusetts , verkauft . Matthias Rice, der in Boston eine Holzwerkstatt betrieb, sah eines dieser Puzzles und begann im Dezember 1879 mit der Produktion. Er überzeugte einen Händler für Geschenkartikel, die Firma „Yankee Notions“, sie unter dem Namen „Gem Puzzle“ zu vertreiben. Ende Januar 1880 erregte Charles Pevey, ein Zahnarzt aus Worcester , Massachusetts, Aufsehen, indem er eine Geldprämie für die Lösung des 15-Puzzles auslobte. ^{[ 16 ]}

Das Spiel wurde 1880 in den USA zu einer wahren Leidenschaft . ^{[ 17 ]}

Chapman meldete am 21. Februar 1880 ein Patent für sein „Block-Solitär-Puzzle“ an. Dieses Patent wurde jedoch abgelehnt, wahrscheinlich weil es sich nicht ausreichend von dem am 20. August 1878 an Ernest U. Kinsey erteilten Patent für „Puzzle-Blocks“ (US 207124) unterschied. ^{[ 16 ]}

Von 1891 bis zu seinem Tod 1911 behauptete Sam Loyd , das Rätsel erfunden zu haben. Loyd hatte jedoch weder mit der Erfindung noch mit der anfänglichen Popularität des Rätsels etwas zu tun. Sein erster Artikel darüber erschien 1886, und erst 1891 beanspruchte er erstmals, der Erfinder zu sein. ^{[ 16 ] [ 18 ]}

Späteres Interesse wurde durch Loyds Angebot eines Preises von 1.000 US-Dollar (entspricht 35.833 US-Dollar im Jahr 2025) für denjenigen geweckt, der eine Lösung für eine von Loyd festgelegte Kombination finden konnte, nämlich die Vertauschung der Zahlen 14 und 15, die Loyd als 14-15-Rätsel bezeichnete . ^{[ 1 ]} Dies ist unmöglich, wie Johnson & Story (1879) bereits über ein Jahrzehnt zuvor gezeigt hatten , da es eine Transformation von einer geraden in eine ungerade Permutation erfordert.

Der in der UdSSR hergestellte Minuswürfel ist ein 3D- Puzzle mit ähnlichen Operationen wie das 15er-Puzzle.

Es gibt Varianten des 15er-Puzzles mit einer anderen Anzahl von Spielsteinen, zum Beispiel das 8er-Puzzle oder das 24er-Puzzle.

Schachweltmeister Bobby Fischer war ein Experte im Lösen des 15-teiligen Schachrätsels. ^{[ 19 ]} Es wurde gemessen, dass er es in 17 Sekunden lösen konnte; Fischer demonstrierte dies am 8. November 1972 in der „Tonight Show Starring Johnny Carson“ . ^{[ 20 ] [ 21 ]}

• Kombinationsrätsel
• Jeu de taquin , eine Operation auf schiefen Young-Tableaus, ähnlich den Zügen des 15er-Rätsels
• Klotski
• Mechanische Puzzles
• Probleme mit der Bewegung von Kieselsteinen
• Rubiks Würfel
• Drei-Tassen-Problem

• Die Geschichte des 15-Rätsels
• 15 Puzzlespiele
• Lösung des Fünfzehn-Rätsels
• Maximale Anzahl an Zügen, die für die m x n-Verallgemeinerung des 15-Rätsels erforderlich sind
• Optimaler Löser für 15 Rätsel mit Download-Option (von Herbert Kociemba)