« Famille des taquins » est le nom parapluie. En dessous, une demi-douzaine de puzzles nommés partagent une règle — une tuile ne peut bouger que dans une case vide adjacente — et font varier tout le reste : forme du plateau, nombre de tuiles, nombre de cases vides, rotation possible. Cet article parcourt l’arbre généalogique.
La branche à grille carrée : les N-puzzles
La ligne principale. Plateau carré avec N² − 1 tuiles numérotées (ou en images) et une case vide.
| Nom | Plateau | Tuiles | Solution optimale la pire |
|---|---|---|---|
| 8-puzzle | 3×3 | 8 | 31 coups |
| 15-puzzle | 4×4 | 15 | 80 coups |
| 24-puzzle | 5×5 | 24 | 152 coups |
| 35-puzzle | 6×6 | 35 | ~245 coups |
| 48-puzzle | 7×7 | 48 | inconnue (recherche) |
| 80-puzzle | 9×9 | 80 | inconnue |
La même stratégie — rangée du haut, colonne de gauche, récursion — fonctionne à toutes les tailles. Plus grand = plus long, pas un autre puzzle.
Ce sont les puzzles auxquels la plupart pensent quand on dit « taquin ». Ce sont aussi ceux sur lesquels les informaticiens font leurs benchmarks.
Grilles non carrées
Moins courantes mais intéressantes :
Rectangulaires — 3×4, 4×5, 5×6. Certaines versions commerciales, y compris en bois au XIXᵉ, étaient rectangulaires. La stratégie marche ; la manœuvre en L du bord asymétrique change un peu.
Hexagonales — tuiles sur grille hexagonale, six voisins possibles au lieu de quatre. Mathématiquement plus permissif (plus d’options par état), psychologiquement plus déroutant. Une niche.
Triangulaires — sur grille triangulaire. Encore plus rare. La math passe, la jouabilité est inconfortable.
Plus d’une case vide
La version à une seule case vide est la norme. Il existe des puzzles commerciaux à deux ou plusieurs vides — le plus célèbre, Klotski et ses cousins, où des tuiles de tailles différentes (1×1, 1×2, 2×2) glissent sur un plateau avec quelques cases vides. Klotski est stratégiquement un autre jeu : il ne s’agit pas d’ordonner mais d’amener une pièce particulière à une sortie.
Klotski est parfois rangé dans les « taquins ». En fait il n’est pas tout à fait de la famille — autre but, autre stratégie, autre structure mathématique.
Glissement plus rotation
Combinez la règle de glissement avec une mécanique de rotation et vous obtenez de nombreux puzzles physiques : les anneaux hongrois, certains produits proches du Rubik’s Cube, et les « loopover ». Ils croisent la famille du taquin mais sont, là encore, stratégiquement différents.
Pour qui vient du 15-puzzle, le cousin le plus proche est Rubik’s 15 — un petit jouet physique avec la disposition du 15-puzzle, mais aussi capable d’échanger des paires adjacentes.
Ce qui unit la famille
Deux faits mathématiques rendent la famille cohérente :
-
Structure de graphe d’états. Chaque variante se modélise en graphe : nœuds = états du plateau, arêtes = coups légaux. Résoudre optimalement = plus court chemin. Le graphe est énorme mais sage, et c’est pour ça que la recherche heuristique marche si bien.
-
Invariants de parité. La plupart des variantes — y compris tous les N-puzzles standard — ont une règle de parité qui scinde les états atteignables en deux moitiés. Une moitié est atteignable depuis le but ; l’autre non. Les apps qui génèrent des positions de départ aléatoires soit filtrent avec le test de parité, soit construisent à reculons depuis le but.
Que jouer, selon l’humeur
Si vous n’en avez essayé aucun :
- Commencez par le 8-puzzle dix minutes. Assez rapide pour absorber la règle et tester la stratégie.
- Passez au 15-puzzle quand le 8 paraît trivial. C’est l’expérience canonique.
- Essayez le 24-puzzle quand vous voulez une longue session.
- Essayez Klotski si vous voulez un taquin différent — même mécanique, autre but.
- Essayez les grilles hexagonales pour vous sentir à nouveau débutant. Ça remet en place.
Les apps modernes, la nôtre comprise, livrent ensemble les 8, 15, 24, 35. C’est le tronc central de la famille, et c’est là que joue presque tout le monde.