Combien faut-il de coups au minimum pour résoudre une grille ? Pour la taille de ★1 (4 couleurs, 2 tubes vides) de l’app Sort Puzzle, on peut examiner toutes les donnes. J’ai compté le nombre minimal de coups de toutes les donnes, avec des coups « Verser ».
Méthode
- On n’examine que les « donnes équitables », sans tube où une même couleur se répète 3 fois ou plus (l’app ne distribue que celles-là).
- Deux donnes qui ne diffèrent que par l’ordre des tubes ou par un simple changement de couleurs sont considérées comme identiques. On obtient ainsi 89 675 types (Combien de façons de distribuer ?).
- Pour chaque donne, on déploie toutes les positions atteignables en 1 coup, en 2 coups, etc., pour trouver le nombre de coups où la grille est triée pour la première fois (parcours en largeur).
Répartition du nombre minimal de coups
| Nombre minimal de coups | Types de donnes |
|---|---|
| 5 coups | 3 |
| 6 coups | 8 |
| 7 coups | 124 |
| 8 coups | 741 |
| 9 coups | 3 523 |
| 10 coups | 11 070 |
| 11 coups | 21 321 |
| 12 coups | 26 778 |
| 13 coups | 19 271 |
| 14 coups | 6 635 |
| 15 coups | 197 |
| 16 coups | 4 |
Le plus fréquent est 12 coups, et de 10 à 13 coups on couvre plus de 80 % du total. Il n’y a que 3 types de donnes qui se résolvent en 5 coups, et 4 qui demandent 16 coups.
(Les nombres sont ici des « types ». La probabilité d’être réellement distribué dans l’app varie un peu d’un type à l’autre.)
La grille la plus courte (5 coups)
Dans chaque tube, la même couleur est empilée par deux. Avec les deux tubes vides, la grille est triée en 5 coups.
La grille la plus longue (16 coups)
Les tubes 1 et 2, comme les tubes 3 et 4, sont exactement dans le même ordre. Dans chaque tube, les couleurs voisines sont toutes différentes, et le rouge et le vert citron sont chacun au fond de deux tubes.
Voir la solution en 16 coups
Trouver une borne inférieure
Sans tout examiner, on peut trouver, rien qu’en regardant la grille, une borne inférieure du nombre minimal de coups (un nombre en dessous duquel on ne peut pas descendre).
- Compter, dans les tubes, le nombre de changements de couleur.
- Si une même couleur est au fond de plusieurs tubes, ajouter « ce nombre − 1 ».
Cette somme ne diminue que de 1 au plus à chaque versement, donc elle n’est jamais supérieure au nombre minimal de coups (Résoudre avec un ordinateur).
- Grille en 5 coups : 4 changements de couleur, et le rouge est au fond de 2 tubes, donc on ajoute 1 : borne inférieure de 5. C’est exactement le minimum.
- Grille en 16 coups : 12 changements de couleur, le rouge et le vert citron sont chacun au fond de 2 tubes, donc on ajoute 2 : borne inférieure de 14. En réalité, il faut 16 coups.
Sur les 89 675 types, la borne inférieure et le nombre minimal de coups coïncidaient exactement pour 38 571 types (environ 43 %). Pour les autres, il faut plus de coups que la borne inférieure.
Pour des grilles plus grandes
Avec plus de couleurs, il y a trop de donnes pour tout examiner. Sur 20 grilles générées de la même façon que dans l’app, la moyenne du nombre minimal de coups est de 11,8 coups en ★1 et de 18,1 coups en ★2 (6 couleurs). À partir de ★3, même trouver le nombre minimal de coups d’une seule grille prend du temps.
L’« Indice » de l’app ne montre pas le nombre minimal de coups, mais une solution trouvée rapidement. Si vous voulez viser le nombre minimal, réfléchissez à la suite de coups vous-même, en prenant la borne inférieure comme repère (Utiliser l’indice).
