Je suis désolé

Sokoban est un casse-tête classique de transport dans lequel le joueur incarne un magasinier qui doit pousser des caisses vers des emplacements de stockage désignés. Le joueur peut se déplacer dans quatre directions et pousser (mais jamais tirer) une seule caisse à la fois. La difficulté réside dans la planification minutieuse des coups, car pousser une caisse dans un coin ou contre un mur peut rendre le casse-tête insoluble. Sokoban est d'une simplicité trompeuse dans son concept, mais peut s'avérer extrêmement difficile, certains niveaux nécessitant des centaines de coups pour être résolus.

Règles

1. Le personnage du joueur (le magasinier) se déplace sur une grille : vers le haut, vers le bas, vers la gauche ou vers la droite.
2. Le niveau contient des caisses (boîtes) et des emplacements cibles (marqués par des points, des losanges ou des dalles de sol plus foncées).
3. Le joueur peut pousser une caisse en marchant dessus, à condition que l’espace derrière la caisse soit vide (pas de mur ni d’autre caisse).
4. Le joueur ne peut pas tirer les caisses, pousser deux caisses à la fois, ni traverser les murs ou les caisses.
5. Le niveau est terminé lorsque toutes les caisses sont placées sur un emplacement cible.
6. Certains niveaux comportent le même nombre de caisses et d’emplacements cibles ; d’autres peuvent comporter plus d’emplacements cibles que de caisses.

Stratégies

• Évitez les angles : une caisse poussée dans un angle (à la jonction de deux murs) reste coincée de manière définitive, sauf si cet angle est un emplacement cible. Demandez-vous toujours si une poussée risque d’entraîner une impasse.
• Évitez de coller les caisses contre les murs : une caisse poussée à plat contre un long mur ne peut glisser que le long de ce mur. S’il n’y a pas d’emplacement cible sur ce mur, la caisse est de fait bloquée.
• Procéder à rebours : visualisez l’état final (toutes les caisses sur leurs cibles) et réfléchissez à ce que doivent être les derniers mouvements. En partant de la solution et en remontant à rebours, vous pouvez déterminer l’approche nécessaire.
• Résolvez d’abord la partie la plus difficile : identifiez la caisse ou la cible la plus contrainte — celle qui dispose du moins de chemins d’accès possibles. Résolvez-la en premier, puis progressez vers l’extérieur.
• Préservez la mobilité : gardez les couloirs dégagés pour pouvoir manœuvrer. Ne bloquez pas vos propres voies de déplacement en poussant des caisses dans des positions qui coupent l’accès.
• Utilisez généreusement la fonction « Annuler » : dans les versions numériques, la fonction « Annuler » est indispensable. Poussez une caisse avec prudence, observez les conséquences et annulez l’action si cela conduit à une impasse.

Sokoban a été créé en 1981 par Hiroyuki Imabayashi, étudiant dans une université japonaise, dans le cadre d'un concours de jeux vidéo. Le nom « Sokoban » signifie « magasinier » en japonais (倉庫番). Le jeu a été édité en décembre 1982 par Thinking Rabbit, une société japonaise de logiciels, pour divers ordinateurs personnels japonais, notamment le NEC PC-8801 et la série Sharp MZ.

Le jeu original comprenait 90 niveaux de difficulté croissante, entièrement conçus par Imabayashi. L’élégante simplicité des règles — déplacement dans quatre directions et poussée —, combinée à l’extraordinaire profondeur des énigmes, a fait de Sokoban un classique instantané. Le jeu a été porté sur pratiquement toutes les plateformes informatiques des années 1980 et 1990, notamment DOS, Macintosh, Amiga et de nombreuses consoles.

Sokoban a eu une influence profonde tant sur la conception des jeux de réflexion que sur l’informatique. En 1997, des chercheurs ont démontré que Sokoban est PSPACE-complet, ce qui signifie qu’il figure parmi les problèmes les plus difficiles à résoudre sur le plan informatique dans sa catégorie. Cela signifie qu’il n’existe aucun algorithme efficace connu pour résoudre des niveaux arbitraires de Sokoban — même les ordinateurs doivent essentiellement recourir à une recherche par force brute, assortie d’optimisations astucieuses. Malgré cette difficulté théorique, des solveurs spécialisés pour Sokoban ont été développés, avec des programmes tels que « Festival » et « YASS » capables de résoudre de nombreux niveaux complexes.

Ce casse-tête a inspiré d’innombrables variantes et successeurs spirituels. Parmi les exemples notables, on peut citer « Boxxle » pour Game Boy (1989), « Kwirk » (1989), « Stephen’s Sausage Roll » de Stephen Lavelle (2016) et « Baba Is You » (2019), qui déconstruit le genre des casse-têtes de poussée en faisant des règles elles-mêmes des objets pouvant être poussés. La communauté internationale de Sokoban gère de vastes collections de niveaux conçus par les joueurs — les plus célèbres étant les collections « Microban » et « Sasquatch » de David W. Skinner. Les concours annuels de Sokoban mettent les concepteurs au défi de créer des niveaux de plus en plus ingénieux, et le jeu reste l’un des casse-têtes les plus étudiés et les plus appréciés de l’histoire de l’informatique.