Sokoban

Regeln Rules

1. Schieben Sie die braunen Kisten mit möglichst wenigen Zügen an die mit grüne  Kreisen gekennzeichneten Plätze!
2. Kisten können nur einzeln geschoben werden. Es ist nicht möglich, eine Kiste zu ziehen oder zwei Kisten gleichzeitig zu schieben.
3. Minimieren Sie in erster Linie die Zahl der Züge mir Kistenbewegungen, in zweiter Linie die Zahl der Züge insgesamt.

1. Push the brown boxes to the spaces marked with green circles in as few moves as possible!
2. Crates can only be pushed one at a time. It is not possible to pull a crate or push two crates at the same time.
3. The primary criterion is the level of moves required to move the boxes; only secondarily is the total level of moves considered.

Das Diagramm rechts zeigt eine mögliche die Endstellung (der Sokoban kann sich auch auf einer anderen Position befinden).

Aufgaben

Der Level gibt den durchschnittlichen Schwierigkeitsgrad der Aufgaben in einer Sammlung an (je größer die Zahl, desto schwieriger). Die Zahl wird aus den durchschnittlichen Lösungszeiten aller Level der jeweiligen Aufgabensammlung berechnet. Einzelne Level einer Sammlung können jedoch deutlich leichter oder schwerer sein als der Durchschnitt.

Lexikon

Ursprung und Hintergrund:

Sokoban wurde 1982 von Hiroyuki Imabayashi erfunden und von Thinking Rabbit in Japan auf den Markt gebracht; Spektrum Holobyte brachte Sokoban 1984 dem Rest der Welt. Aufgrund der einfachen und eleganten Regeln wurde Sokoban schnell populär. Der Name Sokoban bedeutet soviel wie "Lagerarbeiter", "Lagerverwalter" oder – salopp übersetzt – "Kistenschieber".

Aufgrund des großen Erfolges kamen schnell diverse Klone auf den Markt, teilweise mit abgeänderten oder neuen Regeln. Das Original hatte 50 Aufgaben, die heute einen Quasi-Standard bilden, der in keiner Sammlung fehlen darf. Darüber hinaus gibt es tausende Aufgaben ambitionierter Aufgaben-Autoren, die im Internet veröffentlicht werden und wurden. Und natürlich gibt es auch eine Reihe kommerzieller Aufgabensammlungen.

Das Sokoban-Programm auf diesen Seiten folgt den Original-Regeln und ermöglicht es Ihnen, einige der oben erwähnten Freeware-Aufgaben online zu lösen.

Bezeichnungen:

Andere Bezeichnungen für Sokoban gibt es fast ebenso viele wie es Implementierungen gibt: Sokofun, Pokoban, Warehouse, Sokobox, Sokozone, Pixelschieber, Paoban, Kisten schieben, Boxxle, Bilboban, Pushing Blocks, u.v.a.m.

Literatur:

Wikipedia

Sokoban Wiki

Pushing Blocks is NP-Hard von Erik D. Demaine

Sokoban is PSPACE-complete

Aufgabenautoren:

Leider sind viele Autorenseiten nicht mehr online, daher wird diese Liste immer kürzer.

Evgenyi Grigoriev

David W. Skinner (nicht mehr online)

Aymeric di Peloux (nicht mehr online)

François Marques

Yoshio Murase

Jordi Domènech

Aufgabensammlungen:

Bjorn Kallmark

Sokoban Projekt

Frantisek Pokorny

Lee J Haywood Maps

Let's Logic

Rangliste der Löser

Aus Aufwandsgründen können die Rekordlisten leider nicht tagesaktuell gehalten werden; wir werden uns aber bemühen, sie mindestens einmal monatlich zu aktualisieren. Auf Basis der Highscoresn gibt es auch eine Rangliste der Löser. (Danke an Gerhard, der die Idee dazu hatte.)