Si vous avez déjà passé trente minutes sur un 15-puzzle qui ne finit pas — chaque coup amène deux tuiles inversées à la fin —, il y a une chance que le puzzle soit mathématiquement insoluble. Exactement la moitié l’est. Une app mal écrite peut en générer un par accident.
Cet article est la vérification pratique. La justification mathématique complète est dans le théorème de parité ; ici, on reste simple.
La vérification en 30 secondes
Regardez les tuiles dans l’ordre de lecture — gauche à droite par rangée, du haut vers le bas — en ignorant le vide.
Pour chaque paire de tuiles, comptez combien de fois un nombre plus grand apparaît avant un plus petit. Ce compte est le nombre d’inversions.
Puis notez dans quelle rangée est le vide, comptée depuis le bas (rangée du bas = 1, au-dessus = 2, puis 3, puis 4 en haut).
Ajoutez le nombre d’inversions et la rangée depuis le bas. Si la somme est impaire, c’est résoluble. Si paire, non.
C’est tout. Toute la vérification.
Exemple déroulé
Supposons :
1 2 3 4
5 6 7 8
9 10 11 12
13 15 14 _
Ordre de lecture : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14.
Inversions : 15 apparaît avant 14, c’est la seule. Inversions = 1.
Vide en rangée du bas → rangée 1 depuis le bas.
Somme : 1 + 1 = 2. Paire. Plateau insoluble.
C’est le puzzle du prix de Sam Loyd de 1880. 1000 $ offerts ; insoluble ; il a gardé son argent.
Autre exemple
5 1 3 4
2 6 7 8
9 10 11 12
13 14 15 _
Lecture : 5, 1, 3, 4, 2, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.
Inversions :
- 5 avant 1 → 1
- 5 avant 3 → 1
- 5 avant 4 → 1
- 5 avant 2 → 1
- 3 avant 2 → 1
- 4 avant 2 → 1
Total : 6.
Vide en rangée du bas → rangée 1.
Somme : 6 + 1 = 7. Impair. Soluble.
Pourquoi ça marche (bref)
Un coup légal déplace une tuile soit horizontalement (sans changer inversions ni rangée du vide), soit verticalement (change inversions d’une quantité impaire, change la rangée du vide de 1).
Dans les deux cas, la somme inversions + rangée du vide reste avec la même parité de départ. La somme est invariante.
Le but a 0 inversion et le vide en rangée 1 depuis le bas. Somme : 1, impaire. Tout plateau soluble a somme impaire. Pair = ne peut atteindre le but.
Démonstration complète : la page du théorème.
Et les 8-puzzles (3×3) ?
Pour 3×3, plus simple :
- Compter les inversions en ordre de lecture.
- Pair = soluble.
- Impair = insoluble.
Pas besoin de suivre la rangée du vide pour le 3×3 — la symétrie rend la dépendance redondante.
(Pour 5×5 — comme 3×3. Pour 6×6 — comme 4×4. Règle : « la rangée du vide compte quand N est pair ».)
Quoi faire si votre app génère des insolubles
Ça ne devrait pas arriver. Une bonne app utilise l’une de deux méthodes :
Générer par marche arrière depuis le but. Partir du but, appliquer des coups valides aléatoires. Solvabilité garantie par construction.
Générer aléatoire puis tester par parité. Mélanger uniformément ; calculer la parité ; si paire, échanger deux tuiles. Position résultante garantie soluble.
Si vous tombez sur un puzzle insoluble en app, l’app est cassée. Signalez le bug, changez d’app. Slide Puzzle utilise la marche arrière et ne peut pas produire de positions insolubles.
Quoi faire si vous soupçonnez un puzzle physique
Deux choses :
- Faire la vérification. Inversions + rangée du vide. Si pair, les pièces physiques sont mal montées. Sortir une tuile, échanger avec une voisine, et le puzzle redevient soluble.
- Si après échange ça résiste encore — c’est votre stratégie, pas le puzzle.
La vérification prend trente secondes. Avant de plonger une heure de plus dans un plateau coincé, c’est un usage raisonnable de ces secondes.