Il y a une seule méthode pour résoudre des taquins à la main. Elle ne dépend pas de la taille. Une fois acquise en 3×3, vous l’avez pour 4×4, 5×5, 6×6 et toute taille plus grande. La voici.
Le plan
Pour un N×N :
- Résoudre la rangée 1 — placer les tuiles 1, 2, …, N dans la rangée du haut.
- Résoudre la colonne 1 — placer N+1, 2N+1, … dans la première colonne sous la rangée 1.
- Vous avez maintenant un puzzle (N−1)×(N−1). Récursion.
- Cas de base — quand on arrive à un 2×2, les tuiles restantes sont en place ou il faut un test de parité.
C’est tout l’algorithme. Trois phrases. Le reste est mécanique.
La mécanique : les coins
Placer les premières tuiles d’une rangée ou colonne est facile. L’astuce, c’est placer la dernière — celle du coin.
Pour le coin haut-droit de la rangée 1 (tuile N en N×N) :
- N’essayez pas d’envoyer N directement dans le coin. Elle n’y reste pas.
- Placez la tuile précédente (N−1) dans le coin.
- Placez N juste sous N−1.
- Faites pivoter la paire : amener le vide dans le coin (déplaçant N−1), glisser N−1 en bas-gauche hors chemin, glisser N en haut dans le coin, glisser N−1 à droite.
Effet : N−1 et N se retrouvent à leurs cibles sans toucher à ce qui est à leur gauche.
C’est la manœuvre d’angle en L. Le même tour, en miroir, marche en bas-gauche d’une colonne.
Si vous ne devez retenir qu’un seul morceau de technique, retenez celui-là. Tout le reste en découle.
La mécanique : le milieu
Pour l’intérieur d’une rangée (tuiles 1 à N−2 en haut), le placement est direct :
- Trouvez la tuile.
- Amenez-la adjacente à sa cible.
- Utilisez le vide pour la glisser en place.
Vous devrez peut-être pousser d’autres tuiles non placées. Pas grave — elles ne le sont pas. Tant que vous ne touchez pas aux tuiles posées à gauche, la rangée se construit proprement.
La règle de sûreté : le vide ne traverse jamais une tuile posée. S’il doit aller de la droite à la gauche d’une tuile posée, il faut le faire transiter autour, par des cases non posées.
Pourquoi « rangée puis colonne »
Deux raisons :
- Symétrie miroir. L’angle de rangée et l’angle de colonne sont exactement le même tour, en miroir. Apprendre l’un enseigne l’autre.
- Le vide a la place de bouger. Après la rangée 1, il dispose des (N−1) rangées du bas. Après la colonne 1, d’une zone (N−1)×(N−1). La zone de travail se rétrécit avec élégance.
Vous pourriez alterner (rangée 1, colonne 1, rangée 2, colonne 2, …) mais le rythme naturel est de les faire par paires en périmètre, puis récursion.
La récursion
Quand rangée 1 et colonne 1 sont faites, le (N−1)×(N−1) restant contient des tuiles qui doivent rejoindre une autre configuration cible — la même suite numérique, à d’autres positions. Bonne nouvelle : la méthode s’en fiche. Résolvez la nouvelle rangée du haut, la nouvelle colonne de gauche, récursion. Vous finirez par un cas de base 2×2 ou 3×3.
Pour le cas de base 3×3, les trois dernières tuiles se cyclent en place par coups isolés répétés. Pour un cas de base 2×2 (qui peut apparaître en toute fin de grands puzzles), pareil.
Pourquoi ça marche à toute taille
La famille des taquins a une propriété récursive utile : résoudre une rangée-et-colonne réduit le puzzle à un puzzle plus petit du même type. La math est directe. Après avoir placé N tuiles en rangée 1 (et ne plus y toucher), le jeu restant vit sur une grille de largeur (N−1) à laquelle il manque une rangée. Après la colonne de gauche, sur un (N−1)×(N−1).
La réduction s’applique à chaque pas. Le 6×6 se réduit au 5×5, qui se réduit au 4×4, qui se réduit à la fin 3×3. Seule la fin 3×3 a une technique spéciale ; tout le reste s’y ramène.
Cette structure récursive est ce qui fait des taquins un exemple courant pour enseigner la méthode diviser pour régner en cours de programmation. La preuve de correction tient en un paragraphe ; l’implémentation est le corps de l’algorithme.
À quelle vitesse vous progressez
Un débutant qui applique cette méthode à la lettre met :
En quelques parties par taille, ces temps sont divisés par deux. La méthode est la même ; c’est juste la mémoire motrice de la manœuvre d’angle.
Pour quoi cette méthode n’est pas adaptée
Solutions optimales. Un ordinateur avec un vrai solveur trouve des suites 30–50 % plus courtes que la rangée-et-colonne. Les humains ne peuvent pas faire tourner ces algos dans leur tête.
Speedsolving compétitif. Les meilleurs humains utilisent la méthode comme base mais coupent agressivement, faisant des placements partiels qu’ils défont plus tard. Plus rapide, plus dur à apprendre.
Pour tout le monde — la méthode rangée-et-colonne est la méthode.