Accueil / algorithme du solveur Sokoban
Guide de l’algorithme Sokoban

Algorithme de Sokoban : comment la recherche trouve une solution

Un algorithme de Sokoban transforme le puzzle en recherche parmi les états du plateau. Il mémorise les caisses, les cases accessibles, les poussées possibles et les états connus.

Ce guide explique le fonctionnement d’un solveur. Utilisez la page du solveur en ligne pour saisir un plateau ASCII et obtenir un parcours.

Mis à jour le 16 novembre 2026Pour les joueurs, créateurs de niveaux et programmeurs curieux

Plateau de Sokoban montrant caisses, buts, murs et cases d’accès

Un solveur évalue le plateau comme un graphe d’états, pas seulement comme une image.

Réponse rapide : En bref : le solveur conserve un état compact, calcule par remplissage les cases accessibles, génère les poussées légales et élimine les états répétés ou manifestement bloqués. Les liens vers les états parents permettent de restituer la solution sous forme de déplacements.

L’unité utile est généralement une poussée, plutôt qu’un pas avec une flèche. Marcher entre deux poussées change la position du joueur sans déplacer de caisse. Le plateau peut donc devenir un graphe : un nœud est une position connue et une arête une poussée légale accompagnée de la marche nécessaire pour atteindre la caisse suivante.

Ce graphe est vaste car les poussées ne sont pas toujours réversibles. Il faut se placer de l’autre côté d’une caisse pour la déplacer, sans pouvoir la tirer hors d’un mauvais coin. Chaque nœud doit indiquer quelles cases portent des caisses et quelles cases restent accessibles sans les déplacer.

Lorsque toutes les cibles sont occupées, le solveur remonte les liens parents jusqu’au départ et reconstitue le parcours. La suite de directions peut contenir beaucoup de marche, mais les décisions essentielles sont les poussées qui changent l’état.

Comment représenter l’état du plateau

Le plateau comprend des données fixes et variables. Les murs et les cibles sont lus une seule fois. Les coordonnées des caisses et la région accessible du joueur changent. Deux positions du joueur sont souvent équivalentes s’il peut circuler entre elles sans traverser de caisse. Leur normalisation évite de remplir la file de positions de marche redondantes.

Élément de l’étatInformation conservéeUtilité
Murs et ciblesGéométrie fixeDéfinit les cases praticables et la condition de réussite.
Disposition des caissesUne coordonnée par caisseDétermine les poussées et affectations aux cibles possibles.
Région du joueurCases accessibles sans pousserIndique de quels côtés les caisses sont accessibles.
Parent et actionÉtat précédent et direction de pousséePermet de rejouer la solution plutôt que de répondre seulement oui ou non.

Une table de transpositions, ou ensemble des états visités, conserve une clé pour chaque état normalisé. Revoir la même disposition et la même région accessible ne révèle aucune nouvelle continuation. On échange ainsi de la mémoire contre de la vitesse.

Plateau de Sokoban pour planifier les caisses avec une cible contrainte et une zone de stockage libre

Schéma explicatif : l’ordre des caisses modifie les états accessibles après chaque poussée. L’image illustre le principe, sans être une capture du code.

Comment la frontière de recherche s’étend

Après lecture d’un état, un remplissage calcule la zone praticable. Pour chaque caisse, quatre directions sont vérifiées. La poussée est légale si la destination est libre et si le joueur atteint la case opposée. Le solveur crée ensuite un état avec la caisse déplacée et recalcule la région accessible.

L’ordre de recherche détermine les garanties. La recherche en largeur examine d’abord les courtes suites de poussées : à coût égal par arête, elle minimise leur nombre. La recherche en profondeur suit une branche et consomme moins de mémoire de frontière, mais peut rester longtemps dans une branche inutile. La recherche à coût uniforme ou A* associe coûts et heuristique ; les propriétés de cette estimation déterminent la portée du résultat.

  1. Lire.Identifier murs, cibles, caisses et joueur ; rejeter les comptes incorrects et les symboles non pris en charge.
  2. Atteindre.Marquer le sol accessible sans déplacer de caisse.
  3. Développer.Générer les poussées dont les cases d’appui et d’arrivée sont valides.
  4. Élaguer et enregistrer.Ignorer doublons et blocages évidents, puis mémoriser parent et poussée.
  5. Terminer.S’arrêter quand toutes les cibles sont couvertes ou annoncer l’absence de parcours dans la limite fixée.

Il n’est pas nécessaire de conserver chaque trajet à pied. Après une poussée, une seule région accessible normalisée suffit pour produire les suivantes. Un solveur compact peut ainsi fonctionner dans le navigateur.

Pourquoi élaguer les blocages

Sans élagage, la recherche perd du temps sur des positions sans issue. La règle la plus simple est le coin sans cible : une caisse contre deux murs perpendiculaires ne peut plus sortir. Cette branche est éliminée immédiatement. On vérifie aussi les murs sans cible compatible, les groupes 2×2 immobilisés et les caisses qui ferment un couloir d’une case.

Certains échecs concernent l’accès plutôt qu’une caisse figée. Une cible correctement remplie peut occuper l’unique appui nécessaire à une autre caisse. Deux caisses peuvent encore glisser alors que le joueur n’atteint plus le côté permettant de les séparer. Ces cas difficiles motivent l’association de règles simples, de détection des doublons et d’un budget fini.

Exemple de blocage dans un coin de Sokoban illustrant l’élagage

Un blocage dans un coin se détecte avant une exploration profonde. Les pertes d’accès plus subtiles demandent des vérifications plus larges de l’état.

L’élagage doit préserver la justesse : une règle trop agressive peut supprimer une solution inhabituelle. Un petit outil doit expliquer les limites de ses règles, plutôt que présenter toute absence de solution comme une preuve.

Coût des poussées, de la marche et heuristiques

Il faut définir ce que signifie « solution la plus courte ». L’optimalité en poussées minimise les mouvements des caisses ; l’optimalité en déplacements tient aussi compte de la marche. Ces objectifs peuvent s’opposer : contourner une salle peut économiser une poussée et préserver une bonne affectation. Le solveur doit choisir ses priorités et les indiquer.

Une heuristique estime la distance restante. Une méthode simple associe caisses et cibles selon la distance sur la grille et pénalise les caisses coincées contre les murs. Les murs, appuis et ordres de déplacement compliquent cependant le parcours réel. L’estimation privilégie des états prometteurs sans prouver une distance exacte.

Pour un petit plateau, afficher la suite de déplacements, les poussées, les pas et les états examinés facilite la comparaison avec un plan personnel, sans suggérer une optimalité non démontrée.

Suivre un petit plateau

Voici un exemple à une caisse : # représente un mur, . une cible, $ une caisse et @ le joueur.

#####
# . #
# $ #
# @ #
#####

La région initiale comprend la case du joueur et le sol sous la caisse. Une poussée légale est possible : se placer dessous et pousser vers la cible du haut. Le solveur enregistre la nouvelle coordonnée, recalcule l’accès et constate que toutes les cibles sont occupées. Le lien parent permet de restituer la marche nécessaire suivie d’une poussée.

Sur un plateau difficile, la frontière contient plusieurs poussées candidates. Une branche menant à un coin est élaguée, tandis qu’une branche encore mobile reste en file. C’est la différence entre essayer au hasard et mémoriser les conclusions de la recherche.

Quand le solveur s’arrête ou refuse un plateau

Plusieurs raisons expliquent l’arrêt : nombres différents de caisses et de cibles, symbole inconnu ou joueur absent rendent l’entrée invalide. Un plateau valide peut dépasser les limites sûres de lignes, colonnes, caisses ou états visités. Une recherche limitée peut aussi épuiser sa frontière sans trouver de solution.

Seul ce dernier cas dans une recherche complète et illimitée justifie une affirmation mathématique d’insolubilité. Un outil en ligne limite généralement le travail pour conserver une page réactive. Un avertissement invite à réduire le plateau, vérifier un blocage ou raisonner à rebours. Le solveur de Sokoban associé documente ses limites pour petits plateaux et renvoie un message clair plutôt que de tourner indéfiniment.

Les créateurs peuvent vérifier une route avec le solveur puis faire tester le niveau par des personnes pour confirmer que son idée est comprise. Le guide de conception de niveaux de Sokoban décrit ce processus ; cet article explique la recherche sous-jacente.

FAQ de l’algorithme Sokoban

Qu’est-ce qu’un algorithme de résolution de Sokoban ?

C’est une recherche qui représente les caisses et le joueur, produit les poussées légales, écarte les blocages connus et reconstitue un parcours lorsque toutes les cibles sont occupées.

Le solveur examine-t-il chaque pression sur une flèche ?

Il regroupe généralement les déplacements dans une région accessible et développe les poussées comme arêtes principales. De nombreux chemins de marche équivalents sont ainsi supprimés.

Pourquoi l’élagage des blocages accélère-t-il la recherche ?

Il élimine les branches comportant des coins sans cible, des groupes immobilisés ou des passages fermés avant d’explorer leurs états suivants.

Le premier parcours trouvé est-il le plus court ?

Seulement si l’ordre de recherche et le modèle de coût le garantissent. Un solveur limité peut fournir un parcours utile sans prouver son optimalité en poussées ou en déplacements.

Que signifie la limite de recherche atteinte ?

L’outil a épuisé son budget de sécurité avant de prouver une solution ou son impossibilité. Essayez un plateau plus petit ou vérifiez la position manuellement ; ce message ne prouve pas l’absence de solution.

Sources et lectures complémentaires

Les états et régions accessibles sont confrontés à la référence des solveurs du wiki Sokoban. Les exemples d’ordre suivent Algorithmes de recherche élémentaires pour Sokoban. La croissance des états et les estimations de distance sont abordées dans la documentation du solveur Sokoban de Pavel Klavik. Ces sources traitent du jeu standard ; les limites propres à cet outil viennent du solveur Zeek lié.

Résoudre un petit plateau et examiner le résultat

Collez un plateau ASCII dans le solveur du navigateur, puis revenez relier la séquence aux états, aux poussées et à l’élagage.

Ouvrir le solveur de Sokoban