Histoire du genre

Les origines du Sokoban

Sokoban-Lettres n’invente pas son mécanisme : il le reprend à un jeu japonais de 1982 dont la formule n’a pratiquement pas bougé depuis. Comprendre d’où vient cette formule aide à comprendre pourquoi elle résiste aussi bien au temps — et ce que l’ajout des lettres y change.

Un gardien d’entrepôt

Le mot sōkoban (倉庫番) signifie « gardien d’entrepôt » en japonais. Le jeu est l’œuvre de Hiroyuki Imabayashi et fut publié en 1982 par Thinking Rabbit, un studio japonais dont il fut le premier titre marquant. Il paraît sur les micro-ordinateurs japonais de l’époque, à une période où le puzzle sur ordinateur personnel est encore un genre à définir.

Le principe tient en une phrase : un personnage pousse des caisses dans un entrepôt vu de dessus, jusqu’à ce que chaque caisse repose sur un emplacement marqué. Il ne peut pas les tirer, il ne peut pas en pousser deux à la fois, et il ne peut pas traverser un mur.

Pourquoi si peu de règles suffisent

La plupart des jeux gagnent en profondeur en ajoutant des systèmes. Le Sokoban fait l’inverse : sa profondeur vient d’une seule asymétrie. Pousser est possible, tirer ne l’est pas.

Cette asymétrie a une conséquence redoutable : la plupart des coups sont irréversibles. Dans un jeu de taquin, toute configuration atteinte peut être défaite. Dans un Sokoban, une caisse poussée dans un coin y reste pour toujours. Le joueur ne perd donc pas en manquant d’adresse ; il perd en ayant mal anticipé, parfois trente coups plus tôt, et sans que rien ne l’en avertisse sur le moment.

C’est aussi ce qui explique la sensation particulière du genre : le moment décisif d’une partie n’est presque jamais celui où l’on constate l’échec.

Un problème difficile, au sens précis du terme

Le Sokoban a très tôt intéressé les chercheurs en intelligence artificielle, et pas par curiosité : il constitue un banc d’essai particulièrement hostile pour les algorithmes de planification.

Les travaux menés dans les années 1990 ont établi que la version généralisée du jeu — sur une grille de taille arbitraire — est un problème PSPACE-complet. En clair : il appartient à une classe de difficulté dont on ne connaît aucune méthode de résolution efficace en général, et il est au moins aussi difficile que tout autre problème de cette classe. Des résultats antérieurs avaient déjà montré sa NP-difficulté en le rapprochant des problèmes de planification de mouvement.

Ce qui rend le Sokoban dur pour une machine n’est pas le nombre de coups possibles à chaque instant — il est faible, souvent moins d’une dizaine — mais la profondeur des solutions et la présence de configurations sans issue. Une recherche naïve explore pendant des heures des branches condamnées depuis longtemps. Les solveurs efficaces consacrent donc l’essentiel de leur intelligence à une seule tâche : reconnaître le plus tôt possible qu’une position est perdue.

Quarante ans de portages

Le Sokoban s’est propagé comme peu de jeux : sa logique tient en quelques dizaines de lignes de code et ses niveaux en quelques octets de texte. Il a été porté sur pratiquement toutes les plateformes ayant existé depuis, souvent par des amateurs, souvent accompagné de collections de niveaux conçues par des passionnés. Des jeux de niveaux de référence servent encore aujourd’hui à comparer les solveurs entre eux.

Cette diffusion doit beaucoup à une propriété rare : un niveau de Sokoban est une donnée, pas un programme. Une grille se décrit en caractères — un mur, un sol, une caisse, une cible — ce qui a permis à des milliers de niveaux de circuler indépendamment de toute implémentation.

Ce que les lettres changent

Dans un Sokoban traditionnel, les caisses sont interchangeables. Le problème consiste à couvrir un ensemble d’emplacements ; peu importe quelle caisse occupe lequel.

Sokoban-Lettres retire cette liberté. Chaque caisse porte une lettre, les emplacements forment un mot à lire de gauche à droite, et une caisse marquée « R » n’a plus qu’une destination possible. Le problème cesse d’être une couverture d’ensemble pour devenir une affectation contrainte : il faut non seulement amener chaque caisse à bon port, mais le faire dans un ordre où aucune ne bloque la route d’une autre.

L’effet est net sur des grilles de taille modeste. Une disposition qui serait triviale avec des caisses anonymes peut demander une réflexion sérieuse dès lors que l’ordre est imposé, parce que chaque lettre déjà rangée devient un obstacle pour les suivantes. C’est ce qui permet de conserver des grilles lisibles sur un écran de téléphone sans sacrifier la difficulté.

Un second effet, moins attendu, tient à la mémoire. Le mot à former donne au joueur une prise que le Sokoban classique n’offre pas : on retient plus facilement « il faut que le R passe avant le O » qu’une position abstraite. Les modes de difficulté jouent précisément là-dessus, en masquant tout ou partie des étiquettes.

Pour aller plus loin

Les règles complètes de cette variante sont exposées dans le guide, et les partis pris de conception dans la page À propos. Le Défi du Jour propose une grille par date, identique pour tous.