Le 8-puzzle occupe très peu de place et possède une réputation démesurée. Huit tuiles carrées, numérotées de 1 à 8, sur un plateau 3×3. Une case est vide. Votre tâche : faire glisser les tuiles dans la case vide, un coup à la fois, jusqu’à ce que les nombres soient ordonnés — généralement 1‑2‑3 en haut, 4‑5‑6 au milieu, 7‑8‑vide en bas.
C’est le plus petit membre de la famille des N-puzzles. Le 15-puzzle est le cousin plus connu, mais le 8-puzzle est l’endroit où la plupart — enfants, étudiants, chercheurs en algorithmes de recherche — commencent.
Comment fonctionne un coup
La case vide est la seule chose que vous contrôlez vraiment. Vous ne pouvez glisser qu’une tuile directement au-dessus, en dessous, à gauche ou à droite de la case vide. Pas de diagonales. Pas de déplacement en l’air. Chaque coup est une tuile voisine qui glisse d’une case dans le trou, et le trou prend la place de la tuile.
Cette règle minuscule rend le puzzle intéressant. On a toujours l’impression d’avoir un ou deux coups utiles, et pourtant un plateau 3×3 cache 181 440 dispositions résolubles distinctes. (L’autre moitié — les insolubles — fait l’objet d’un guide sur la parité.)
La stratégie manuelle standard
Le truc auquel la plupart finissent par penser, et qui passe à l’échelle jusqu’à 4×4, 5×5 et au-delà :
- Résolvez la rangée du haut d’abord — placez 1, 2, 3 et n’y touchez plus.
- Résolvez ensuite la colonne de gauche — placez 4 et 7. La rangée et la colonne sont verrouillées.
- Le 2×2 restant — trois tuiles et un trou — n’a que deux états : résolu, ou une tuile décalée. Si elle est décalée, vous ne pouvez pas y remédier dans le 2×2 seul depuis une position résoluble ; il faut revenir dans le puzzle. (D’où l’importance de la parité.)
Le passage difficile est la dernière tuile d’une rangée ou d’une colonne. Pour placer le 3 dans le coin haut-droit, il faut d’abord glisser le 2 dans le coin, puis amener le 3 dessous, puis tourner la paire. Cette petite manœuvre en L est le même mouvement que vous utiliserez au 15-puzzle, au 24-puzzle et sur tous les autres formats.
Les solutions optimales sont courtes
Le 8-puzzle le plus dur se résout en 31 coups. C’est pour toutes les 181 440 positions de départ — la pire n’est qu’à 31 glissements de la solution.
Une position moyenne réclame environ 22 coups. Un ordinateur avec A* et une bonne heuristique trouve la solution optimale en microsecondes. À la main, qui connaît la stratégie « rangée du haut » résout n’importe quel 8-puzzle bien en moins d’une minute dès qu’il repère le motif.
Pourquoi les informaticiens l’adorent
Le 8-puzzle est le banc d’essai d’introduction standard pour la recherche heuristique. Le plateau est assez petit pour être énuméré, assez grand pour que la force brute soit gaspilleuse, et assez riche pour montrer la différence entre deux heuristiques connues :
- Tuiles mal placées — compter combien ne sont pas à leur place. Bon marché, guide faible.
- Distance de Manhattan — pour chaque tuile, somme des écarts en rangées et en colonnes. Guide plus fort, toujours bon marché.
Une implémentation A* de manuel avec Manhattan résout n’importe quel 8-puzzle en microsecondes. Passez au 15-puzzle et il faut des bases de motifs additifs pour rester rapide — c’est une conversation à part, dans le guide du solveur du 15-puzzle.
Quand jouer au 8-puzzle
Un plateau 3×3 est un plaisir tranquille. Peu de coups à considérer, condition de victoire évidente, partie d’une à deux minutes. C’est la bonne taille pour :
- Un enfant qui apprend à « planifier un coup à l’avance ».
- Un adulte dans le bus qui ne veut pas un long puzzle en main.
- Une manche d’entraînement avant de passer au 15-puzzle.
C’est aussi la taille presque toujours gratuite dans les apps de taquin, la nôtre comprise — les plateaux plus grands se trouvent souvent derrière un paywall parce qu’ils créent des sessions plus longues, mais le 3×3 est l’onboarding de tout le monde.
Ce qui change en 4×4
Rien côté stratégie. Résolvez la rangée du haut, puis la colonne de gauche, puis récursion sur le 3×3 restant. Ce qui change, c’est le temps : un 8-puzzle en 30 secondes devient un 15-puzzle en 5 à 10 minutes. Les nombres empirent après — les tailles 5×5 et 6×6 exigent une vraie patience.
Si les 8-puzzles deviennent ennuyeux au bout d’une semaine, c’est le signal pour monter d’un cran.