Avant de proposer une grille, l’app Sort Puzzle vérifie par ordinateur qu’elle est soluble. Le prochain coup de l’« Indice » est lui aussi le premier coup d’une suite trouvée par le même solveur. Voici comment il fonctionne.

Suivre les positions et les coups

L’état d’une grille (quelle couleur est dans quel tube) s’appelle une position. Un coup mène à une autre position. En suivant les coups depuis la position de départ, si l’on arrive à une position triée, le chemin suivi est la réponse.

La recherche la plus simple déploie toutes les positions atteignables en 1 coup, puis toutes celles atteignables en 2 coups, etc. C’est le parcours en largeur. Il trouve toujours une réponse au nombre minimal de coups, mais avec beaucoup de couleurs, le nombre de positions à examiner devient énorme.

Une estimation de la « distance » avant le tri

L’app estime donc, pour chaque position, la distance qui reste avant le tri, et examine d’abord les positions qui semblent proches. L’estimation est la somme de ces deux nombres.

  1. Le nombre de changements de couleur dans les tubes : en regardant du bas vers le haut, le nombre d’endroits où la couleur change.
  2. Les fonds en double : si une même couleur est au fond de plusieurs tubes, ce nombre moins 1.
123456

Dans cette grille, il y a 2 changements de couleur dans le tube 1, 2 dans le tube 2, 3 dans le tube 3 et 3 dans le tube 4, soit 10 au total. Le bleu ciel est au fond des tubes 3 et 4, donc les fonds en double comptent 1. L’estimation est de 11. Dans une position triée, il n’y a ni changement de couleur ni fond en double, donc l’estimation est 0.

L’estimation n’est jamais supérieure au nombre minimal de coups

Cette estimation a une bonne propriété : en un coup, elle ne diminue jamais de plus de 1.

  • Dans un versement, le nombre de changements de couleur du tube de départ diminue de 1 au plus. La destination est la même couleur ou un tube vide : le nombre de changements n’y augmente ni ne diminue.
  • Un fond en double disparaît quand un tube se vide, c’est-à-dire seulement quand on verse la dernière suite de ce tube, et dans ce cas le nombre de changements de couleur ne diminue pas.

Autrement dit, une grille dont l’estimation est 11 demande au moins 11 coups. En examinant plus de 120 000 coups dans diverses grilles, aucun coup ne faisait baisser l’estimation de 2 ou plus. Le nombre minimal de coups de la grille ci-dessus est exactement 11.

La recherche A* pondérée

L’app donne à chaque position le score « coups joués jusqu’ici + 3 × estimation » et examine d’abord les positions au plus petit score. C’est ce qu’on appelle la recherche A* pondérée (A étoile).

  • Avec un poids de 1 (la recherche A* ordinaire), l’estimation est une borne inférieure du nombre minimal de coups : on trouve donc toujours une réponse au nombre minimal de coups.
  • Avec un poids de 3, on examine toujours d’abord les positions à petite estimation : la réponse est trouvée bien plus vite. En contrepartie, la réponse peut compter un peu plus de coups que le minimum.

Sur 20 grilles pour chaque niveau, créées de la même façon que dans l’app, j’ai comparé le nombre de positions examinées avant le tri et le nombre de coups de la réponse trouvée (je n’ai pas compté le parcours en largeur pour ★3, car il y a trop de positions).

★1 (4 couleurs · 2 libres)Positions examinéesCoups de la réponse
Parcours en largeur53711,8
A* (poids 1)20311,8
A* (poids 3)3911,9
★2 (6 couleurs · 2 libres)Positions examinéesCoups de la réponse
Parcours en largeur293418,1
A* (poids 1)62218,1
A* (poids 3)6418,8

Ce sont des moyennes sur 20 grilles. Avec un poids de 3, la réponse est trouvée en examinant des dizaines de fois moins de positions que le parcours en largeur, et le nombre de coups n’augmente que très peu.

Des astuces pour examiner moins de coups

Le solveur de l’app réduit aussi le nombre de positions examinées avec ces astuces.

  • Ne pas distinguer l’ordre des tubes : si le contenu des tubes est le même, on traite comme une même position, quel que soit l’ordre.
  • Ne pas examiner les coups inutiles : on écarte le coup d’un tube d’une seule couleur vers un tube vide (la forme ne change pas) et le coup vers le deuxième tube vide ou les suivants (même position que vers le premier).
  • Chercher seulement avec des coups « Verser » : pour une grille « Empiler » aussi, on vérifie si elle est soluble avec des versements (Verser ou empiler : quelle différence ?).
  • Fixer une limite : si l’on n’a rien trouvé après 60 000 positions, la réponse est « on ne sait pas » et la donne n’est pas utilisée.

Ce solveur sert à la fois à la vérification « soluble ou non » lors de la création des grilles (Comment on crée des grilles toujours solubles) et à l’« Indice » (Utiliser l’indice). L’idée des couleurs du fond est aussi présentée dans Par quelle couleur commencer ?.