Klotski

„Klotski“ ist ein Schiebepuzzle, bei dem der Spieler einen großen 2x2-Block an eine bestimmte Ausgangsposition verschieben muss, indem er diesen und andere Blöcke innerhalb einer begrenzten Schale verschiebt. Die Schale ist in der Regel 4 Spalten breit und 5 Zeilen hoch und enthält Blöcke verschiedener Größen – einen 2x2-Block, mehrere 2x1-Blöcke (horizontal oder vertikal) sowie 1x1-Blöcke – mit genau zwei leeren Feldern, die eine Bewegung ermöglichen. Die Herausforderung besteht darin, den großen Block durch das überfüllte Spielfeld zum Ausgang zu manövrieren, der sich meist unten in der Mitte befindet.

Regeln

1. Das Spielfeld ist eine 4×5-Anordnung, die Blöcke unterschiedlicher Größe und zwei leere Felder enthält.
2. Blöcke können horizontal oder vertikal in benachbarte freie Felder verschoben werden, dürfen jedoch nicht angehoben, gedreht oder auf andere Blöcke gelegt werden.
3. Das Ziel ist es, den großen 2x2-Block an eine Zielposition zu verschieben (in der Regel in die untere Mitte des Spielfelds, wo sich eine Öffnung befindet).
4. Alle anderen Blöcke sind Hindernisse, die so umgestellt werden müssen, dass ein Weg für den großen Block entsteht.

Blocktypen (klassische Konfiguration)

• 1 großer Block (2x2) – der, den Sie befreien müssen
• 1 hoher Block (1x2 vertikal)
• 4 mittelgroße Blöcke (2x1 horizontal oder 1x2 vertikal, je nach Konfiguration)
• 4 kleine Blöcke (1x1)
• 2 leere Felder

Strategien

• Stelle dir den Weg zum Ausgang vor: Der 2x2-Block benötigt einen freien, 2 Felder breiten Kanal von seiner aktuellen Position bis zum Ausgang. Deine Aufgabe ist es, diesen Kanal zu schaffen.
• Kleine Blöcke zuerst verschieben: Kleine 1x1-Blöcke sind am flexibelsten. Nutze sie, um vorübergehend Platz für das Verschieben größerer Blöcke zu schaffen.
• Kreisbewegungen vermeiden: Es kann leicht passieren, dass du versehentlich bereits Erreichtes rückgängig machst. Gehe bei jedem Zug bewusst vor und versuche, die allgemeine Bewegungsrichtung des großen Blocks im Blick zu behalten.
• Arbeite vom Ausgang aus nach oben: Schaffe zuerst Platz in der Nähe des Ausgangs und arbeite dich dann nach oben vor, um einen Weg für den großen Block zu schaffen, auf dem er nach unten rollen kann.
• Nutze Abstellplätze: Verschiebe Hindernisblöcke an Stellen, an denen sie nicht erneut bewegt werden müssen. Die Ecken sind oft gute Abstellplätze.
• Herausforderung „Minimale Züge“: Die klassische Konfiguration („Pennant Puzzle“ oder „Daughter in the Box“) erfordert mindestens 81 Züge. Der Versuch, sich diesem Minimum anzunähern, macht das Rätsel noch anspruchsvoller.

Die Ursprünge von „Klotski“ sind etwas unklar, da mehrere Personen die Erfindung für sich beanspruchen. Das Puzzle scheint zu Beginn des 20. Jahrhunderts in mehreren Ländern unabhängig voneinander entstanden zu sein. Varianten von Schiebepuzzles wurden zwischen 1900 und 1930 in den Vereinigten Staaten und in Europa patentiert. Der Name „Klotski“ leitet sich vom polnischen Wort „klocki“ ab, was „Blöcke“ bedeutet.

Die bekannteste Variante des Puzzles ist in China als „Hua Rong Dao“ (华容道) bekannt, benannt nach einem legendären Pass aus dem chinesischen Klassiker „Die Geschichte der Drei Reiche“. In der Geschichte muss der Kriegsherr Cao Cao nach seiner Niederlage in der Schlacht am Roten Kliff (208 n. Chr.) durch den Huarong-Pass fliehen. Im Puzzle steht der große Block für Cao Cao, während die anderen Blöcke Generäle darstellen, die ihm den Weg versperren. Dieser narrative Rahmen machte das Puzzle in China enorm beliebt, wo es seit über einem Jahrhundert ein fester Bestandteil der Kultur ist.

Im Westen tauchte das Puzzle unter verschiedenen Namen auf: „Pennant Puzzle“ (in den 1930er Jahren von der Embossing Company vermarktet), „Dad’s Puzzle“ und einfach „Sliding Block Puzzle“. Martin Gardner stellte Schiebepuzzles in seiner Kolumne in der Zeitschrift „Scientific American“ vor und machte sie so einem breiten mathematischen Publikum bekannt. Informatiker haben Klotski und seine Varianten als Benchmark-Probleme für Suchalgorithmen und KI-Planung verwendet.

Die mathematische Analyse von Klotski ist umfangreich. Es wurde nachgewiesen, dass das Puzzle in seiner allgemeinen Form PSPACE-vollständig ist, was bedeutet, dass es zu den schwierigsten Problemen gehört, die mit polynomialem Speicherplatz lösbar sind. Die klassische Konfiguration wurde computergestützt erschöpfend analysiert, wodurch die optimale Lösung mit 81 Zügen (bzw. 116, wenn jede Verschiebung eines einzelnen Feldes als Zug gezählt wird) bestätigt wurde. Es gibt zahlreiche Varianten unterschiedlicher Schwierigkeitsgrade, und die Entwicklung neuer, interessanter Konfigurationen ist nach wie vor ein aktives Feld der Puzzle-Entwicklung.