WikiDer > Schiebepuzzle

Ein Schiebepuzzle

Das Schiebepuzzle ist ein Puzzle, normalerweise auf einem Brett von 4 mal 4 Feldern mit 15 verschiedenen Kacheln, wodurch ein Feld leer bleibt, und dann auch 15 Rätsel erwähnt, aber auch in anderen Dimensionen vorkommen. In der Standardvariante haben die 15 Plättchen die Nummern 1 bis 15. Eine andere Möglichkeit ist, dass sich die Plättchen in einem Spielzustand wie in a . befinden Puzzle eine Figur bilden (bei einem Puzzle ist die Anzahl der Teile sehr gering, aber die Schwierigkeit als Schiebepuzzle und als Puzzle sind mehr als addiert: es ist nicht so einfach, zwei Teile nebeneinander zu sehen wenn das Bild weitergeht; das Lösen des Puzzles ist teilweise nur gedanklich). Eine Kachel kann immer auf das leere Feld verschoben werden, wodurch die Position der Kachel und des leeren Felds vertauscht wird.

Das Spiel besteht darin, die Kacheln zunächst viele Male so zu verschieben, dass sie in einer scheinbar zufälligen Reihenfolge auf dem Brett liegen, aber dann die Kacheln in der richtigen Reihenfolge zurück auf das Brett legen.

Das Spiel kann online gespielt werden, und es gibt mehrere Apps mit diesem Rätsel.^[1] Es gibt auch Varianten wie 3 mal 3 und 7 mal 7. Die Spielflächen müssen nicht quadratisch sein, beispielsweise ist auch 4 mal 7 möglich. Neben dem Lösen an sich kann es darum gehen, so schnell wie möglich in der Zeit und/oder in der Anzahl der Schichten zu lösen. Manchmal wird das gleichzeitige Bewegen einer Reihe von zwei oder mehr Kacheln als ein Zug gezählt.

Konstruktion

Heutzutage wird das Puzzle oft aus Plastikblöcken aufgebaut, die mit Schienen verbunden sind, so dass man nur schieben kann und nicht Betrug indem Sie einen Block anheben. Dadurch wird auch verhindert, dass unmögliche Aufgaben gestellt werden: Beim Vertauschen zweier Blöcke entsteht ein unlösbares Rätsel, siehe unten. Es ist nicht unmöglich, das Puzzle zu zerlegen.

Geschichte

Ein unlösbares Rätsel heraus Sam Loyds Cyclopedia of 5000 Puzzles; dieses wird manchmal als 14-15-Puzzle bezeichnet, nachdem diese Zahlen getauscht wurden.

Die Originalausgabe besteht aus losen Blöcken in einem quadratischen Tablett.^[Quelle?] Die Würfel können herausgenommen, gemischt und zurückgelegt werden, wodurch manchmal ein unlösbares Problem entsteht.

Das Rätsel ist am Ende des 19. Jahrhundert bekannt geworden, vor allem durch die Hände von Sam Loyd, der behauptete, der Erfinder zu sein. 1880 war das Puzzle ein Riesenerfolg, vor allem in Amerika Wut, sowohl bei Erwachsenen als auch bei Kindern:

1880 fielen ganze Regionen der Vereinigten Staaten einer beispiellosen Sucht zum Opfer. „Es ist buchstäblich zu einer Epidemie im ganzen Land geworden“, schrieb The Weekly News Demokrat im Emporia (Kansas). „Ganze Städte sind abgelenkt, die Leute können nicht schlafen und das macht sie verrückt.“ Die Epidemie hat auch erreicht Europa sogar Australien und Neuseeland.Das Nachrichten-Demokrat schrieb: „Kein so kleines Kind ist davon nicht gepackt, kein Mann so stark oder erhaben, sondern fasziniert davon.“^[2]

Andere Schiebepuzzles

Im weiteren Sinne ist ein Schiebepuzzle ein Puzzle, bei dem man zum Beispiel Blöcke auf einem Brett verschieben muss Hauptverkehrszeit, Mondsperre und Sokoban. Die drei genannten funktionieren nach dem gleichen Prinzip wie 'das' Schiebepuzzle, haben jedoch Einschränkungen durch Anweisungen für den Spieler, die Form der Spielsteine, Hindernisse auf dem Brett oder Bewegungseinschränkungen.

Layout von Spielzuständen basierend auf Permutationen von Kacheln und leeren Feldern

Wir betrachten den Fall eines rechteckigen (möglicherweise quadratischen) Puzzles mit ich Reihen und nein Spalten (ein Brett von ich×n Felder). Die Anzahl der denkbaren Spielzustände (alle Stellungen der mn Elemente: mn - 1 Kacheln und das leere Feld) ist das Fakultät der Anzahl der Felder, d.h. m! Chancen. Zwei Spielzustände werden als gleichwertig definiert, wenn einer durch mehrmaliges Verschieben in den anderen überführt werden kann. Diese Beziehung ist in der Tat a Äquivalenzrelation.

Es gibt mehrere Möglichkeiten, einen Spielzustand und den Übergang von einem zum anderen zu beschreiben und die Möglichkeit oder Unmöglichkeit auszudrücken, diesen Übergang durch Gleiten zu erreichen.

Eine Möglichkeit besteht darin, sich den Übergang als a . vorzustellen Permutation von mn Elemente, nämlich die Positionen der Kacheln und die des leeren Raums. Die Permutation ist pro Zug immer ungerade, da jeder Zug ein Plättchen und das leere Feld vertauscht. Wenn zwei Spielzustände äquivalent sind, ist die Parität der Permutation der mn Elemente, die einer auf den anderen überträgt, gleich denen des Manhattan Entfernung zwischen den leeren Feldern der beiden Spielzustände (mit anderen Worten: mit gleicher oder unterschiedlicher Farbe der beiden leeren Felder auf a Schachbrettmuster). Dies folgt einfach aus der Beobachtung, dass eine Verschiebung die Parität der Permutation und auch die Parität der besagten Manhattan-Distanz (eine Änderung der Farbe des leeren Quadrats in einem Schachbrettmuster) ändert.

Umgekehrt, wenn von zwei Spielzuständen die Parität der Permutation der mn Elemente, die einer in den anderen überträgt, ist gleich dem Manhattan-Abstand zwischen den leeren Quadraten der beiden Spielzustände, und ich und nein sind mindestens zwei, oder ich = 1 und nein < 4 oder umgekehrt, dann sind die beiden Spielzustände äquivalent.^[3]

Spins und Spiegel der Spielposition

Aus Spiegelungen und Drehungen der Spielposition (was natürlich nur die Gesamtposition betrifft, nicht die Positionen der Kacheln), können wir folgern, ob diese durch Verschieben erreicht werden können. Für diese Eigenschaften behandeln wir für ich und nein die Werte 2 bis 5; sie gelten auch für größere Seiten modular 4, also wenn die Werte von ich und nein, unabhängig voneinander, wird ein Vierer hinzugefügt.^[4]

Die Spiegelung in der horizontalen Achse beträgt nein(int(ich/2)) vertauscht, während das leere Quadrat in einem Schachbrettmuster die gleiche Farbe behält desdaich ist ungerade; ichnein(int(ich/2)) muss also ungerade sein, dies ist bei einem Spielfeld von 2×3, 2×5, 3×2, 3×4, 5×2, 5×3, 5×4, 5×5 der Fall, jedoch nicht mit einem Spielfeld von 2×2, 2×4, 3×3, 3×5, 4×2, 4×3, 4×4, 4×5. Spiegelung in der vertikalen Achse gilt natürlich analog mit ich und nein getauscht, ist es beim Schieben beispielsweise bei einem Spielfeld von 3×5 möglich, jedoch nicht bei einem Spielfeld von 5×3.

Drehung um 180 Grad entspricht int(mn/2) vertauscht, während in einem Schachbrettmuster das leere Quadrat die gleiche Farbe behält wie ichnein ist gerade, kann also gescrollt werden, wenn ichnein int(mn/2) ist gerade. Die Drehung kann durch Schieben mit gleichen Werten erreicht werden und wenn mindestens einer 2 ist, und nicht in den Fällen 3×4, 4×3, 3×5, 5×3, 4×5, 5×4. Die Fälle, in denen das Spiegeln in der horizontalen Achse und das Spiegeln in der vertikalen Achse beide möglich sind oder beide nicht möglich sind.

Quadratisches Spielbrett

Das Obige galt für ein quadratisches Spielbrett:

• Spiegeln in der horizontalen oder vertikalen Achse kann mit Schiebedesda . erfolgen nein ist ein Vierfaches plus 1.
• Sie können sich immer um 180 Grad drehen.

Außerdem bei einem quadratischen Spielbrett:

Eine Drehung um 90 Grad entspricht int(nein²/4) zyklischer Austausch von 4 Elementen, die ungerade Permutationen sind, während das leere Quadrat in einem Schachbrettmuster die gleiche Farbe behält desdanein seltsam. Die Rotation kann daher mit dem Schieben desda int(nein²/4) nein ist seltsam, das ist wie nein ist nicht vervierfacht.

Das Spiegeln um eine diagonale Achse beträgt (nein²-nein)/2 vertauscht, während das leere Quadrat in einem Schachbrettmuster die gleiche Farbe behält. Die Spiegelung kann mit Schiebedesda . erreicht werden nein ist ein Vierer oder ein Vierer plus 1. Die Fälle, in denen das Spiegeln in der horizontalen Achse und das Drehen um 90 Grad sowohl möglich als auch nicht möglich sind.

Anordnung der Spielzustände basierend auf der Reihenfolge der Kacheln entlang eines Pfads

Wählt man eine Reihenfolge aller Halbbilder entlang eines sich selbst schneidenden Pfades von horizontalen und vertikalen Liniensegmenten (wie zum Beispiel die durch die grüne Linie in der Abbildung gekennzeichnete Zickzack-Reihenfolge), so gilt für die Einteilung in zwei Äquivalenzklassen nur die Reihenfolge der mn - 1 Plättchen entlang dieses interessanten Weges; das mn zugehörige Spielzustände, die der Position des leeren Feldes entsprechen, sind eindeutig äquivalent. Die Klassifikation von Spielzuständen kann dann auf eine Klassifikation in Permutationen der mn - 1 Fliesen.

wenn ich und nein mindestens zwei sind, dann sind die mit Verschiebungen möglichen Permutationen de sogar Permutationen, dass die alternierende Gruppe Formen.

wenn ich = 1 jede Äquivalenzklasse hat nur eine Permutation von Kacheln, also gibt es ( nein - 1)! Äquivalenzklassen. Nur für nein = 3, dann gibt es zwei Äquivalenzklassen und dass die mit Verschiebungen möglichen Permutationen die geraden Permutationen sind (die Identität ist dann die einzige gerade Permutation). Für größere nein die geraden Permutationen, mit Ausnahme der Identität, sind bei Verschiebungen nicht möglich. Für kleinere nein es gibt nur eine Äquivalenzklasse. Dies ist natürlich analog zu ich und nein getauscht.

Zickzack-Reihenfolge der 16 Felder mit einem Spielzustand, bei dem die ersten 9 Spielsteine ​​in der Standardreihenfolge sind, mit zwei möglichen Zügen

Die Abbildung zeigt zwei Beispiele für Züge:

• Der blaue Pfeil: Das Plättchen bewegt sich vier Felder vorwärts, von der zweiten bis zur sechsten Position in der 15er-Reihe (ohne Berücksichtigung der Position des leeren Quadrats). Die Kachelnummer in Abhängigkeit von der Position in der 15er-Reihe geht beispielsweise von (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15) bis (1, 3, 4, 5, 6, 2, 7, 8, 9, 10, 11, 12, 13, 14, 15), repräsentiert die gerade Permutation (6 5 4 3 2) der Stellen oder die inverse gerade Permutation (2 3 4 5 6) der Kachelnummern.
• Der rote Pfeil: Das Plättchen rückt um zwei Stellen nach hinten, dies ist die gerade Permutation (9 8 7) der Plättchennummern.

Auf einem 2 mal 3 Brett gibt es 720 Spielzustände, diese Zahl reduziert sich auf 120, wenn die Position des leeren Feldes wieder außer Acht gelassen wird. Da der Pfad geschlossen werden kann, ist der zyklische Austausch trivial, sodass wir uns auf die Betrachtung von 24 Zyklen beschränken können. Bei jeder dieser drei Zahlen ist die Hälfte einer gegebenen Ausgangssituation eine mögliche Position. Der Zyklus ändert sich nicht beim Bewegen entlang der Spielfeldkante, sondern nur, wenn ein Plättchen an die gegenüberliegende Position im Zyklus verschoben wird (was einem zyklischen Vertauschen von drei aufeinanderfolgenden Plättchen entlang des Randes entspricht, wobei die direkte Reihenfolge entlang des Randes von . beibehalten wird). zwei der drei und der verbleibenden zwei der fünf Plättchen). Ab einem bestimmten Zyklus können 5 Zyklen mit einem solchen Zug erreicht werden, 5 mit zwei und 1 (nämlich die umgekehrte Zyklusreihenfolge) mit drei. Die 12 Zyklen können den 12 Ecken von a . zugeordnet werden Ikosaeder, wobei eine Bewegung einer Bewegung entlang einer Kante entspricht. Jede Seitenfläche entspricht einem Paar von Kacheln, die in den drei Zyklen, die den drei Eckpunkten der Seitenfläche entsprechen, in der gleichen Reihenfolge direkt hintereinander liegen. Die anderen drei Kacheln werden in diesen drei Zyklen immer zyklisch ausgetauscht.

Ein geschlossener Weg entlang aller Felder, wie oben auf einem 2 mal 3 Brett, ist nur bei einer geraden Anzahl von Feldern möglich. Ob Spielmodi zugänglich sind oder nicht, kann dann in Zyklen von ausgedrückt werden mn-1 Kacheln treten anstelle von Permutationen von auf mn-1 Fliesen. Dies reduziert die Anzahl der Fälle von (mn-1)! zu (mn-2)!

Kachelnummerierung

Oft sind die Kacheln eines 15er-Puzzles von 1 bis 15 nummeriert, mit dem möglichen Spielzustand (oft der Zielzustand), zeilenweise gelesen (immer von links nach rechts), der numerischen Reihenfolge und mit dem leeren Feld im letzten Zeile. Die erreichbaren Spielzustände sind dann diejenigen, bei denen, in Zick-Zack-Reihenfolge gelesen, die Kachelreihenfolge eine ungerade Permutation der Zahlenreihenfolge ist. Dies ist zB nicht der Fall, wenn die Kacheln zeilenweise gelesen (immer von links nach rechts) in numerischer Reihenfolge stehen und das leere Feld in der ersten Zeile steht. In Zick-Zack-Reihenfolge gelesen, dies ist eine Kachelreihenfolge, die aus der numerischen Reihenfolge mit vier Vertauschungen erhalten werden kann.

Es wurden Puzzles hergestellt, deren Kacheln nicht nummeriert sind, zum Beispiel gibt es ein Werbepuzzle mit den Buchstaben TEMP-OZAK-TUCH-JES. Stellt sich heraus, dass es nicht lösbar ist, kann das Problem durch Vertauschen von zwei identischen Buchstaben gelöst werden (siehe auch unten).Es gibt auch einen mit der Familie Feuerstein (Fred, Wilma, Betty und Barney). Jede Person ist auf vier Plättchen abgebildet, außer Barney, der kleiner ist, und auf drei Plättchen. Sie können die Personen in verschiedene Reihenfolgen bringen. Nicht jede Bestellung ist möglich.

Schritt-für-Schritt Lösung

Dann gehe davon aus, dass ich und nein mindestens zwei sein. Das Problem besteht darin, von einem bestimmten Spielmodus zu einem bestimmten äquivalenten Zielspielmodus zu gelangen (oft zum Beispiel ein Standardmodus mit dem leeren Feld unten rechts).

Die Komplexität des Puzzles ist nicht allzu groß, da es bis auf die letzten zwei oder drei Zeilen Zeile für Zeile gelöst werden kann: wenn oben und/oder unten ganze Spielsteinreihen im richtigen Finale gelandet sind (ohne Regeln, wo das leere Feld sein sollte), dann kann das Puzzle (wenn es lösbar ist) weiter gelöst werden, ohne diese Plättchen zu verschieben.

In Querrichtung gilt dann logischerweise das Gleiche, danach bleibt ein 2×3 oder 3×2 Puzzle übrig.

Das Platzieren einer Plättchenreihe an der richtigen Endstelle (die erste nach dem abgeschlossenen Teil des Puzzles) kann, wenn mindestens 3 Reihen übrig bleiben, auch Plättchen für Plättchen sein, außer bei den letzten beiden Plättchen: Es muss Vor dem Setzen des vorletzten Plättchens , bereiten Sie die Installation des letzten vor. Zum Beispiel könnte man die Kachel, die an vorletzter Stelle sein sollte, zuerst auf die letzte und die Kachel, die an letzter Stelle liegen soll, darunter legen, dann die vorletzte Stelle leeren und dann die letzten beiden Kacheln in Position.

Beim abschließenden Lösen des 2×3- oder 3×2-Rätsels bleibt weniger Spielraum. Abgesehen von den Zügen entlang der Kante dieses 6-Felder-Spielbretts können drei weitere Überquerungen auf die andere Seite des 5-Felder-Zyklus erforderlich sein, siehe oben. Mit zwei davon lässt sich das Problem auf das Lösen eines verbleibenden 2×2-Puzzles reduzieren. Wenn die beiden Kacheln, die auf einer der kurzen Seiten des Rechtecks ​​enden sollen, in der Position entlang der Kante unmittelbar hintereinander liegen, jedoch in der falschen Reihenfolge (in der richtigen Reihenfolge gesehen, also liegen drei dazwischen), dann diese Zahl von drei wird zuerst auf eins reduziert, indem man eine der ersten beiden Plättchen überkreuzt. Dann kann dieser herausgenommen werden, indem man ihn die Überfahrt machen lässt. Wenn die beiden an ihren Platz gebracht werden, löst die letzte Phase das verbleibende 2×2-Puzzle, was trivial ist. Wenn nicht bekannt war, ob die Zielspielposition erreicht werden konnte und diese noch nicht berechnet wurde, wird dies nun klar. Wenn zwei Kacheln identisch sind, gibt es immer eine Lösung. Ein unlösbares verbleibendes 2×2-Puzzle bedeutet, dass die beiden Kopien getauscht werden müssen, siehe unten.

Optimale Bewegungsabläufe

Für ein Brett von 4 mal 4 hat sich folgendes über optimale Zugfolgen gezeigt:

• Mit einem Tile-Shift kann jede Position in 80 Zügen gelöst werden. Es gibt sechs Positionen, die 80 Züge erfordern.^[5]
• Mit mehreren Kachelverschiebungen kann jede Position in 43 Zügen gelöst werden. Es gibt sechzehn Positionen, die 43 Züge erfordern.^[6]

Fall, in dem einige Kacheln identisch sind

Eine besondere Situation ergibt sich, wenn die mn - 1 Kacheln sehen zwei gleich aus. Angenommen, in den Puzzle-Kacheln werden die darauf befindlichen Texte unterschieden, das wären zwei Plättchen mit dem gleichen Text. Dann ist ein Spielzustand im Sinne der Gestaltung von Kachelkopien von einem Spielzustand im Sinne der Gestaltung von Texten zu unterscheiden: Es sind dann immer zwei Konfigurationen von Kachelkopien mit gleicher Textgestaltung (mit einem imaginären Austausch) denkbar identischer Kacheln, sieht das Ergebnis gleich aus), mit einer in der einen und einer in der anderen Äquivalenzklasse. Aus jeder denkbaren Konfiguration von Kachelkopien kann daher eine bestimmte Textkonfiguration erreicht werden. Wenn das Rätsel nicht lösbar erscheint, weil am Ende alle Steine ​​stimmen außer zwei, die vertauscht wurden, dann müssen die beiden identischen Steine ​​vertauscht werden (man kann das Rätsel also nicht einfach zeilenweise lösen, wie bei allen anderen Fliesen). Wenn zum Beispiel in einem 2 mal 3 Puzzle die Lösung "der. Tag" ist und die Startposition "zB hinzufügen" ist. dann stellt sich heraus, dass das erste d von "add eg." muss in die erste Zeile zurückkehren, und das zweite d muss in die zweite Zeile zurückkehren. Bei einem größeren Puzzle kann es schwierig sein, frühzeitig festzulegen, welches von zwei identischen Plättchen auf das eine und welches auf das andere gelegt werden soll. Man probiert dann eine Option aus, und wenn das nicht funktioniert, kann man, wie erwähnt, immer noch die beiden tauschen. Genauso funktioniert es mit den trivialen Spielbrettern 1 mal 3 und 2 mal 2. Diese Fälle sind zur Veranschaulichung nützlich, aber es ist sofort klar, welche Kopie auf welches der beiden Zielfelder gelegt werden soll.

Wenn vier Kacheln zwei identische Texte aufweisen, sind immer vier Konfigurationen von Kachelkopien mit der gleichen Textkonfiguration denkbar, mit zwei in der einen und zwei in der anderen Äquivalenzklasse. Von jeder denkbaren Konfiguration von Kachelkopien können dann immer zwei Konfigurationen von Kachelkopien mit einer bestimmten Textkonfiguration erreicht werden. Scheint das Rätsel nicht lösbar zu sein, weil am Ende alle Steine ​​bis auf zwei vertauscht sind, muss ein Paar aus zwei identischen Steinen getauscht werden.

Wenn drei Kacheln den gleichen Text haben, sind immer sechs Konfigurationen von Kachelkopien mit der gleichen Textkonfiguration denkbar, mit drei in der einen und drei in der anderen Äquivalenzklasse. Aus jeder denkbaren Konfiguration von Kachelkopien können dann drei Konfigurationen von Kachelkopien mit einer bestimmten Textkonfiguration erreicht werden. Wenn das Rätsel nicht lösbar erscheint, weil am Ende alle Steine ​​bis auf zwei vertauscht sind, müssen zwei der drei identischen Steine ​​vertauscht werden.

Wissenswertes

Das Französisch Name für das Puzzle wird international für eine Operation in der Kombinatorik: jeu de taquin.

Externer Link

• Spielen Sie das Puzzle-Spiel online für viele Dimensionen

Siehe die Kategorie 15 Rätsel von Wikimedia Commons für Mediendateien zu diesem Thema.