Coulisses
Comment les niveaux sont générés
Les grilles de Sokoban-Lettres ne sont pas dessinées une à une. Elles sont produites par un générateur à partir d’un mot et d’une graine, puis soumises à une série de contrôles et résolues par un solveur avant d’être publiées. Cette page décrit ce processus tel qu’il est réellement implémenté.
Un mot et une graine
Chaque niveau naît de deux données : le mot à former et une graine, un nombre qui alimente le générateur pseudo-aléatoire. La même paire produit toujours exactement la même grille, ce qui permet de reconstruire un niveau à l’identique et garantit que tous les joueurs reçoivent la même grille pour un même Défi du Jour.
Partir de la solution
Le générateur commence par placer les cibles : une ligne horizontale continue, sans mur, de la longueur du mot. S’il ne trouve pas de place pour une telle ligne, la tentative est abandonnée. Les caisses sont d’abord posées sur leurs cibles, puis éloignées par une série de poussées à rebours. Cette méthode garantit qu’au moins une solution existe : il suffit de rejouer le mélange à l’envers.
Un mélange qui n’a déplacé aucune caisse est rejeté, tout comme un mélange qui laisse une caisse dans un coin. Les lettres sont ensuite redistribuées entre les caisses, pour que la position de départ ne trahisse pas l’ordre du mot.
Des chapitres de plus en plus exigeants
Les réglages du générateur évoluent du premier au dixième chapitre de l’Aventure. Entre ces deux extrémités, chaque paramètre progresse de façon régulière :
- la densité de murs passe de 20 % à 30 % de la grille ;
- le nombre de poussées visé passe de 2,5 à 6 fois la longueur du mot ;
- la distance moyenne entre une caisse et sa cible doit passer d’au moins 2 cases à au moins 5 ;
- la part de caisses déjà proches de leur cible tolérée descend de 50 % à 20 % ;
- la part de caisses alignées tolérée descend de 60 % à 30 %.
Les contrôles de qualité
Une grille générée n’est pas forcément intéressante. Chaque candidate passe donc une série de portes, dans cet ordre : un nombre minimal de poussées dans la solution, une distance moyenne suffisante entre caisses et cibles, un écart suffisant entre les caisses, une dispersion suffisante sur la grille, puis des limites sur les caisses déjà proches de leur cible et sur les caisses alignées. Une grille qui échoue à l’une de ces portes est écartée.
Plusieurs candidates, une seule retenue
Pour chaque niveau, le générateur produit plusieurs grilles candidates — de 4 au premier chapitre jusqu’à 16 au dixième — et s’accorde jusqu’à 16 tentatives pour chacune. Parmi celles qui passent tous les contrôles, la mieux notée est conservée.
La vérification par le solveur
La candidate retenue est enfin soumise au solveur IDA*, qui cherche une solution économe en poussées. Une grille déclarée insoluble est rejetée. Le budget de recherche grandit avec les chapitres, de 100 000 à 500 000 positions examinées. Si ce budget est atteint sans conclusion, la grille est conservée — elle est soluble par construction — et son par est estimé plutôt que calculé. Le détail du par est expliqué dans score et par.
Pourquoi ce choix
Générer plutôt que dessiner permet de proposer chaque jour une grille inédite, dans trois langues et avec des mots différents, tout en garantissant que chacune est soluble. Les contrôles de qualité, eux, protègent contre les grilles triviales qu’un générateur produit naturellement. Les origines du Sokoban racontent comment le genre est passé des niveaux dessinés à la main aux niveaux calculés.