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 coupsTypes de donnes
5 coups3
6 coups8
7 coups124
8 coups741
9 coups3 523
10 coups11 070
11 coups21 321
12 coups26 778
13 coups19 271
14 coups6 635
15 coups197
16 coups4

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)

123456
Coup 1 : 3→5 (2)
123456
Coup 2 : 1→3 (2)
123456
Coup 3 : 4→5 (2)
123456
Coup 4 : 2→4 (2)
123456
Coup 5 : 1→2 (2)
123456
Trié

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)

123456

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
123456
Coup 1 : 1→5
123456
Coup 2 : 1→6
123456
Coup 3 : 2→5
123456
Coup 4 : 2→6
123456
Coup 5 : 1→2
123456
Coup 6 : 1→5
123456
Coup 7 : 2→1 (2)
123456
Coup 8 : 2→5
123456
Coup 9 : 3→2
123456
Coup 10 : 3→6
123456
Coup 11 : 3→1
123456
Coup 12 : 2→3
123456
Coup 13 : 4→3
123456
Coup 14 : 4→6
123456
Coup 15 : 4→1
123456
Coup 16 : 3→4 (3)
123456
Trié

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).

  1. Compter, dans les tubes, le nombre de changements de couleur.
  2. 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).