Comment un jeu de puzzle devient un problème mathématique — et comment l'algorithme BFS trouve la solution optimale en un éclair.
↓ Défiler pour explorer
// 01
Les graphes, c'est quoi ?
Un graphe est l'une des structures mathématiques les plus utiles en informatique. L'idée est simple : on a des objets (les sommets) et des liens entre eux (les arêtes).
⭕
Sommet (nœud)
Un objet, une situation, une entité
↔
Arête (lien)
Une connexion entre deux sommets
🕸
Graphe
L'ensemble des sommets et des arêtes
On retrouve les graphes partout : plan du métro, réseau d'amis, routage sur internet, intelligence artificielle…
Exemple : graphe de villes. Sommets = villes, arêtes = trajets.
💡 Idée clé
Un graphe modélise n'importe quelle situation où des objets sont reliés. La question typique : quel est le chemin le plus court d'un point A à un point B ?
// 02
Une situation de jeu = un sommet
Dans Rush Hour, à chaque instant, les véhicules sont dans des positions précises. L'ensemble de toutes ces positions forme une configuration — ou état du jeu.
🔑 Principe fondamental
Chaque configuration unique du plateau = un sommet unique dans le graphe.
Deux configurations différentes = deux sommets différents.
Comment encoder un état ?
Pour représenter un état, on note la position de chaque véhicule. Pour un véhicule horizontal, on retient sa colonne. Pour un vertical, sa ligne.
Configuration A
R : colonne 0
B : ligne 0 → état = (R=0, B=0)
Sommet A
Configuration B
R : colonne 1
B : ligne 3 → état = (R=1, B=3)
Sommet B
Ces deux configurations sont distinctes : elles représentent donc deux sommets différents dans le graphe des états.
📐 Pour un Rush Hour complet
Avec 8 véhicules, l'état est encodé par 8 valeurs (une par véhicule). Deux états avec des valeurs identiques sont le même sommet. Deux états qui diffèrent, même d'un seul véhicule, sont des sommets différents.
// 03
Un déplacement = une arête
Depuis une configuration, on peut déplacer un véhicule d'une case. Ce geste fait passer le jeu vers une nouvelle configuration. Ce passage est exactement une arête dans le graphe !
État de départ
(R=0, B=1)
→
B descend d'1 case
→
État d'arrivée
(R=0, B=2)
Ce déplacement correspond à une arête dans le graphe, reliant le sommet (R=0, B=1) au sommet (R=0, B=2).
Le graphe se construit naturellement
En répertoriant tous les états possibles et tous les déplacements légaux, on construit le graphe complet du jeu :
Graphe des états d'une version simplifiée (voiture rouge R + bloqueur B). Chaque bulle = une configuration. Chaque trait = un déplacement d'un véhicule d'une case.
🎯 Reformulation du problème
Résoudre Rush Hour, c'est trouver le chemin le plus court dans ce graphe entre le sommet initial (position de départ) et n'importe quel sommet solution (voiture rouge à la sortie).
// 04
Le Parcours en Largeur (BFS)
Le Parcours en Largeur (en anglais Breadth-First Search, ou BFS) est un algorithme qui explore un graphe couche par couche, en commençant par le sommet de départ.
L'idée centrale : la file d'attente
Le BFS utilise une file d'attente (comme à la boulangerie : premier arrivé, premier servi). Chaque sommet découvert est ajouté à la file. On les traite un par un, dans l'ordre où ils sont arrivés.
📋 Algorithme BFS
Mettre le sommet de départ dans la file. Le marquer comme visité.
Tant que la file n'est pas vide : retirer le premier sommet de la file.
Pour chaque voisin non encore visité : l'ajouter à la file, le marquer visité, noter de quel sommet on vient.
Si un voisin est la solution : retracer le chemin et s'arrêter.
Démonstration interactive — cliquez sur "Étape suivante"
Observez comment le BFS explore le graphe niveau par niveau. La file d'attente est affichée en bas.
Non découvert
Dans la file (découvert)
Traité (visité)
Solution !
Prêt
Cliquez sur Étape suivante pour lancer le BFS.
File d'attente (FIFO) :
vide
Étape 0 / 6
Le chemin solution
Une fois la solution trouvée, on remonte les parents (le sommet depuis lequel on a découvert chaque sommet) pour reconstruire le chemin optimal :
Départ (S)→C→WIN 🏁
Distance minimale : 2 coups. BFS garantit qu'il n'existe pas de chemin plus court.
// 05
Pourquoi BFS donne la solution optimale ?
C'est la propriété la plus importante du BFS. Voici pourquoi il est garanti d'être optimal.
✅ Preuve d'optimalité (intuition)
Le BFS explore d'abord tous les sommets à distance 1, puis tous à distance 2, etc.
Donc, la première fois qu'il atteint la solution, c'est forcément par le chemin le plus court.
S'il existait un chemin plus court, le BFS l'aurait déjà exploré avant !
Comparaison avec DFS (Parcours en Profondeur)
Un autre algorithme, le DFS (Depth-First Search), plonge le plus loin possible avant de revenir en arrière. Il peut trouver une solution, mais pas nécessairement la plus courte !
Algorithme
Stratégie
Solution trouvée
Mémoire utilisée
BFS
Couche par couche
Optimale (minimum de coups) ✅
Proportionnelle au niveau exploré
DFS
En profondeur d'abord
Pas garantie optimale ❌
Proportionnelle à la profondeur
🏆 Pour Rush Hour : BFS est le choix parfait
On veut le minimum de coups pour sortir la voiture rouge. BFS explore toujours les configurations à N coups avant celles à N+1 coups, garantissant de trouver la solution optimale.
// 06
Complexité et enjeux
Combien d'états possibles ?
Dans un vrai Rush Hour (plateau 6×6, jusqu'à 16 véhicules), le nombre d'états possibles est astronomique. C'est ce qu'on appelle l'explosion combinatoire.
~10⁶
Estimation basse
Configurations atteignables dans un puzzle simple
<1ms
Temps de résolution
Pour un ordinateur moderne avec BFS
93
Record mondial
Coups minimum pour le puzzle le plus difficile jamais construit
Pourquoi l'ordinateur et pas nous ?
Un humain peut peut-être explorer mentalement quelques dizaines de configurations. Un ordinateur exécute le BFS sur des millions de sommets en une fraction de seconde.
# BFS en Python — version simplifiéefrom collections import deque
defbfs_rush_hour(etat_initial):
file = deque([etat_initial])
vus = {etat_initial: None} # sommet → parentwhile file:
etat = file.popleft() # retirer le premierif est_solution(etat):
return reconstruire_chemin(vus, etat)
for voisin in voisins(etat): # 1 coup possibleif voisin not in vus:
vus[voisin] = etat
file.append(voisin)
return None# pas de solution
Applications réelles des graphes + BFS
🗺
GPS / Navigation
Trouver le chemin le plus court entre deux villes
🌐
Réseaux sociaux
Trouver la chaîne d'amis la plus courte (6 degrés)
🤖
IA & Jeux
Résoudre Rubik's cube, Taquin, Sodoku… par exploration
🕸
Moteurs de recherche
Indexer le Web en explorant les liens de pages en pages
🧠 À retenir
Graphe des états : chaque configuration = un sommet, chaque coup = une arête.
BFS : explore couche par couche, garantit la solution avec le minimum de coups.
Complexité : des millions d'états, mais l'ordinateur les parcourt en millisecondes.