CoddyRun
Le backtracking est souvent perçu comme une technique abstraite : on “essaie”, on “échoue”, on “revient en arrière”… mais ce n’est pas toujours évident de visualiser ce qui se passe réellement.
Ce programme transforme cette idée en animation vivante, où chaque étape du raisonnement devient visible.
Objectif : trouver un chemin de S à E dans un labyrinthe
Le labyrinthe est composé de cases libres, de murs, d’impasses et d’un point de départ et d’arrivée. L’algorithme explore les cases une par une, avance quand c’est possible, recule quand il est bloqué, et finit par trouver (ou non) un chemin valide.
Une visualisation pensée pour apprendre
L’animation montre :
- les cases visitées en vert,
- les impasses en rouge,
- la case en cours d’examen en jaune,
- la pile d’appels récursifs qui grandit et rétrécit en temps réel,
- des compteurs qui suivent les visites, les retours arrière et la profondeur maximale atteinte.
On voit littéralement l’algorithme réfléchir, se tromper, corriger, progresser.
Le principe du backtracking illustré
L’algorithme suit une logique simple :
- Avancer tant qu’une direction est possible.
- Si toutes les directions échouent, marquer l’impasse et revenir en arrière.
- Répéter jusqu’à trouver la sortie ou conclure qu’il n’y en a pas.
Cette mécanique, souvent difficile à imaginer, devient limpide grâce à l’animation.
Un final visuel
Si un chemin est trouvé, l’animation se termine par un clignotement doré du parcours complet : une manière élégante de mettre en valeur la solution.
Pourquoi ce programme est précieux pédagogiquement
- Il dédramatise la récursion en la rendant visible.
- Il montre que les impasses font partie du processus, et même qu’elles aident l’algorithme à “apprendre”.
- Il permet de comprendre que le backtracking n’est pas magique : c’est une méthode systématique, patiente, méthodique.
- Il offre une lecture intuitive d’un concept souvent jugé difficile.
Programme :
// Le backtracking expliqué : sortir d'un labyrinthe
@ toile et mémoire de l'animation
frames est un tableau
maToile est une toile
dimension(maToile, 650, 480)
@ Compteurs de l'animation
// On les range dans un tableau : ainsi les fonctions peuvent
// les modifier sans problème de portée de variable.
//
// stats[0] = cases visitées stats[5] = colonne examinée
// stats[1] = retours arrière stats[6] = ligne examinée
// stats[2] = profondeur de la pile stats[7] = mode victoire (0/1)
// stats[3] = profondeur maximale stats[8] = clignotement (0/1)
// stats[4] = 0 exploration / 1 retour arrière / 2 succès
stats est un tableau
pour k de 0 à 8
stats ajoute 0
fin pour
stats[5] vaut 99 // 99 = "aucune case examinée" (hors plateau)
stats[6] vaut 99
@ Le labyrinthe (0 = libre, 1 = mur)
// col 0 1 2 3 4 5
// lig 0 S . . . . . <- grand piège : couloir sans issue
// lig 1 . # # # # .
// lig 2 . . . . # .
// lig 3 # . # # # #
// lig 4 . . . . . .
// lig 5 . # # # # E
//
// L'algorithme essaie DROITE en premier : il fonce donc dans le
// couloir du haut, explore 8 cases pour rien, puis dépile tout.
plateau est un tableau
ligne0 est un tableau
ligne0 ajoute 0
ligne0 ajoute 0
ligne0 ajoute 0
ligne0 ajoute 0
ligne0 ajoute 0
ligne0 ajoute 0
plateau ajoute ligne0
ligne1 est un tableau
ligne1 ajoute 0
ligne1 ajoute 1
ligne1 ajoute 1
ligne1 ajoute 1
ligne1 ajoute 1
ligne1 ajoute 0
plateau ajoute ligne1
ligne2 est un tableau
ligne2 ajoute 0
ligne2 ajoute 0
ligne2 ajoute 0
ligne2 ajoute 0
ligne2 ajoute 1
ligne2 ajoute 0
plateau ajoute ligne2
ligne3 est un tableau
ligne3 ajoute 1
ligne3 ajoute 0
ligne3 ajoute 1
ligne3 ajoute 1
ligne3 ajoute 1
ligne3 ajoute 1
plateau ajoute ligne3
ligne4 est un tableau
ligne4 ajoute 0
ligne4 ajoute 0
ligne4 ajoute 0
ligne4 ajoute 0
ligne4 ajoute 0
ligne4 ajoute 0
plateau ajoute ligne4
ligne5 est un tableau
ligne5 ajoute 0
ligne5 ajoute 1
ligne5 ajoute 1
ligne5 ajoute 1
ligne5 ajoute 1
ligne5 ajoute 0
plateau ajoute ligne5
@ Dessin d'une image de l'animation
procédure dessinerEtat()
effacer(maToile)
remplir(maToile, #0e121b)
valeurCase est un nombre
x est un nombre
y est un nombre
largeurEtapes est un nombre
largeurRetours est un nombre
nbBlocs est un nombre
dernierBloc est un nombre
xb est un nombre
// Bandeau de titre
rectangle_arrondi(maToile, 16, 12, 618, 44, 12, #1b2233)
label(maToile, 36, 36, "BACKTRACKING : essayer, échouer, revenir en arrière", #ecf0f1, 17)
label(maToile, 36, 51, "Recherche récursive d'un chemin de S vers E", #7f8fa6, 11)
// Cadre du plateau
rectangle_arrondi(maToile, 16, 66, 342, 342, 16, #1b2233)
pour lig de 0 à 5
pour col de 0 à 5
valeurCase vaut plateau[lig][col]
// Position de la case : 22 et 72 = première case, 56 = écart
x vaut 22 + col * 56
y vaut 72 + lig * 56
// Halo jaune autour de la case en cours d'examen
si col = stats[5] et lig = stats[6] alors
rectangle_arrondi(maToile, x - 5, y - 5, 60, 60, 14, #f6c945)
fin si
// Ombre portée : donne du relief aux cases
rectangle_arrondi(maToile, x + 2, y + 3, 50, 50, 10, #080b11)
si valeurCase = 1 alors
// Mur : rectangle sombre avec un liseré plus clair
rectangle_arrondi(maToile, x, y, 50, 50, 10, #33405a)
rectangle_arrondi(maToile, x + 8, y + 8, 34, 34, 7, #3d4d6b)
sinon si valeurCase = 2 alors
// Chemin en cours : encore dans la pile d'appels
si stats[7] = 1 et stats[8] = 1 alors
rectangle_arrondi(maToile, x, y, 50, 50, 10, #f6d743)
sinon
rectangle_arrondi(maToile, x, y, 50, 50, 10, #27d17c)
fin si
rectangle_arrondi(maToile, x + 18, y + 18, 14, 14, 7, #ffffff)
sinon si valeurCase = 3 alors
// Impasse : on ne repassera plus jamais par là
rectangle_arrondi(maToile, x, y, 50, 50, 10, #e85b5b)
label(maToile, x + 17, y + 35, "X", #ffffff, 22)
sinon
// Case libre encore inexplorée
rectangle_arrondi(maToile, x, y, 50, 50, 10, #e8eef6)
fin si
fin pour
fin pour
// Pastilles Départ (0,0) et Arrivée (5,5)
rectangle_arrondi(maToile, 35, 85, 24, 24, 12, #1b2233)
label(maToile, 42, 102, "S", #ffffff, 15)
rectangle_arrondi(maToile, 315, 365, 24, 24, 12, #1b2233)
label(maToile, 322, 382, "E", #ffffff, 15)
// Panneau latéral : légende et compteurs
rectangle_arrondi(maToile, 366, 66, 268, 342, 16, #1b2233)
label(maToile, 388, 92, "TABLEAU DE BORD", #ecf0f1, 14)
rectangle_arrondi(maToile, 388, 100, 224, 2, 1, #2b3650)
label(maToile, 388, 122, "LÉGENDE", #6c7d95, 11)
rectangle_arrondi(maToile, 388, 131, 16, 16, 5, #33405a)
label(maToile, 412, 144, "Mur infranchissable", #dfe6ee, 13)
rectangle_arrondi(maToile, 388, 155, 16, 16, 5, #e8eef6)
label(maToile, 412, 168, "Case libre, non visitée", #dfe6ee, 13)
rectangle_arrondi(maToile, 388, 179, 16, 16, 5, #27d17c)
label(maToile, 412, 192, "Chemin en cours (pile)", #dfe6ee, 13)
rectangle_arrondi(maToile, 388, 203, 16, 16, 5, #e85b5b)
label(maToile, 412, 216, "Impasse : retour arrière", #dfe6ee, 13)
rectangle_arrondi(maToile, 388, 227, 16, 16, 5, #f6c945)
label(maToile, 412, 240, "Case examinée", #dfe6ee, 13)
rectangle_arrondi(maToile, 388, 254, 224, 2, 1, #2b3650)
// Barre : nombre de cases visitées
label(maToile, 388, 276, "Cases visitées", #6c7d95, 11)
rectangle_arrondi(maToile, 388, 282, 224, 8, 4, #2b3650)
largeurEtapes vaut stats[0] * 6
si largeurEtapes > 224 alors
largeurEtapes vaut 224
fin si
si largeurEtapes > 0 alors
rectangle_arrondi(maToile, 388, 282, largeurEtapes, 8, 4, #3fa9f5)
fin si
// Barre : nombre de retours arrière
label(maToile, 388, 306, "Retours arrière (backtracks)", #6c7d95, 11)
rectangle_arrondi(maToile, 388, 312, 224, 8, 4, #2b3650)
largeurRetours vaut stats[1] * 18
si largeurRetours > 224 alors
largeurRetours vaut 224
fin si
si largeurRetours > 0 alors
rectangle_arrondi(maToile, 388, 312, largeurRetours, 8, 4, #e85b5b)
fin si
// La pile d'appels récursifs, dessinée bloc par bloc
label(maToile, 388, 336, "Pile d'appels récursifs", #6c7d95, 11)
pour i de 0 à 11
rectangle_arrondi(maToile, 388 + i * 18, 344, 15, 24, 4, #232d44)
fin pour
nbBlocs vaut stats[2]
si nbBlocs > 12 alors
nbBlocs vaut 12
fin si
dernierBloc vaut nbBlocs - 1
si nbBlocs > 0 alors
pour i de 0 à dernierBloc
xb vaut 388 + i * 18
si i = dernierBloc alors
rectangle_arrondi(maToile, xb, 344, 15, 24, 4, #f6c945)
sinon
rectangle_arrondi(maToile, xb, 344, 15, 24, 4, #3fa9f5)
fin si
fin pour
fin si
label(maToile, 388, 388, "1 bloc = 1 appel récursif", #6c7d95, 11)
// Barre d'état : ce que fait l'algorithme à cet instant
rectangle_arrondi(maToile, 16, 418, 618, 46, 12, #1b2233)
si stats[4] = 2 alors
rectangle_arrondi(maToile, 30, 430, 6, 22, 3, #f6d743)
label(maToile, 48, 448, "Chemin trouvé ! La pile contient la solution complète.", #f6d743, 13)
sinon si stats[4] = 1 alors
rectangle_arrondi(maToile, 30, 430, 6, 22, 3, #e85b5b)
label(maToile, 48, 448, "Impasse : aucune direction possible, on dépile et on recule.", #ffb3b3, 13)
sinon
rectangle_arrondi(maToile, 30, 430, 6, 22, 3, #27d17c)
label(maToile, 48, 448, "Exploration : on avance et on empile un appel récursif.", #b8f0d3, 13)
fin si
// On mémorise l'image
frames ajoute maToile
fin procédure
@ L'algorithme de backtracking
// Principe : essayer une direction, et si elle échoue, revenir
// exactement dans l'état d'avant pour essayer la suivante.
fonction chercherChemin(c, l)
// 1. Sortie du plateau ?
si c < 0 ou c > 5 ou l < 0 ou l > 5 alors
retourne faux
fin si
valeurCase est un nombre
valeurCase vaut plateau[l][c]
// 2. Mur (1), case déjà dans le chemin (2) ou impasse connue (3)
// Le cas "3" est important : une impasse déjà découverte n'est
// jamais réexplorée, l'algorithme apprend de ses échecs.
si valeurCase = 1 ou valeurCase = 2 ou valeurCase = 3 alors
retourne faux
fin si
// 3. On empile un appel : la profondeur augmente
stats[2] vaut stats[2] + 1
si stats[2] > stats[3] alors
stats[3] vaut stats[2]
fin si
// 4. On marque la case comme "chemin en cours"
plateau[l][c] vaut 2
stats[0] vaut stats[0] + 1
stats[4] vaut 0
stats[5] vaut c
stats[6] vaut l
appelle dessinerEtat()
// 5. Condition d'arrêt : on est arrivé en bas à droite
si c = 5 et l = 5 alors
stats[4] vaut 2
appelle dessinerEtat()
retourne vrai
fin si
// 6. On essaie les 4 directions, dans l'ordre
// Droite
si chercherChemin(c + 1, l) = vrai alors
retourne vrai
fin si
// Bas
si chercherChemin(c, l + 1) = vrai alors
retourne vrai
fin si
// Gauche
si chercherChemin(c - 1, l) = vrai alors
retourne vrai
fin si
// Haut
si chercherChemin(c, l - 1) = vrai alors
retourne vrai
fin si
// 7. RETOUR ARRIÈRE
// Les 4 directions ont échoué : cette case ne mène nulle part.
// On la marque en rouge, on dépile, et on rend "faux" à
// l'appel précédent qui essaiera sa direction suivante.
plateau[l][c] vaut 3
stats[1] vaut stats[1] + 1
stats[2] vaut stats[2] - 1
stats[4] vaut 1
stats[5] vaut c
stats[6] vaut l
appelle dessinerEtat()
retourne faux
fin fonction
@ Lancement du programme
// Trois images identiques au début : le temps de lire le plateau
appelle dessinerEtat()
appelle dessinerEtat()
appelle dessinerEtat()
resultatFinal est un booléen
resultatFinal vaut chercherChemin(0, 0)
si resultatFinal = vrai alors
// Petit final : le chemin solution clignote en or
stats[4] vaut 2
stats[7] vaut 1
stats[5] vaut 99
stats[6] vaut 99
pour p de 0 à 9
si stats[8] = 0 alors
stats[8] vaut 1
sinon
stats[8] vaut 0
fin si
appelle dessinerEtat()
fin pour
sinon
affiche "Aucun chemin possible."
fin si
animation(frames, 250)
