L’app Sort Puzzle ne propose que des grilles dont elle a vérifié qu’elles sont solubles. Cela veut dire qu’il existe des donnes que l’on ne peut jamais résoudre, quoi qu’on fasse dès le départ. J’ai examiné toutes les petites grilles pour voir lesquelles sont insolubles.
2 couleurs, 1 tube vide : la seule donne insoluble
Prenons 4 éléments rouges et 4 éléments orange, répartis dans 2 tubes, plus un tube vide. Si l’on considère comme identiques l’ordre des tubes et un simple changement de couleurs, il y a 23 façons de distribuer. Parmi elles, une seule est insoluble.
Dans les deux tubes, de bas en haut : rouge, orange, orange, rouge. Voici toutes les positions que l’on peut atteindre à partir de cette grille.
- Le rouge du tube 1 va dans le tube vide 3.
- Le rouge du tube 2 va sur le rouge du tube 3.
- On voudrait mettre les deux oranges du tube 2 dans le tube 1… mais il n’y a de la place que pour un.
Dans la dernière position, le seul coup possible est de faire passer l’orange entre les tubes 1 et 2, et cela ramène à la même forme (les deux rouges du tube 3 ne peuvent aller nulle part). Même en choisissant un autre coup depuis une position intermédiaire, on retombe sur l’une de ces 4 positions. Les positions atteignables, en comptant la grille de départ, sont 4 seulement, et aucune n’est triée.
Que ce soit en « Verser » ou en « Empiler », les positions atteignables étaient les mêmes 4.
Pourquoi est-ce insoluble ?
Dans cette grille, le rouge est au fond des deux tubes. Comme on l’a vu dans Par quelle couleur commencer ?, si une même couleur est au fond de deux tubes, il faut vider l’un d’eux au moins une fois.
Pour vider un tube, il faut déplacer ailleurs les deux oranges et le rouge qui sont au-dessus. Mais le dessus des deux tubes est du rouge : au début, on ne peut que mettre du rouge dans le tube vide. Ce tube devient alors un tube de rouge, et il ne reste aucune place qui puisse accueillir les deux oranges d’un bloc (chaque tube n’a qu’une place libre).
3 couleurs, 1 tube vide : environ un quart est insoluble
Avec 3 couleurs (rouge, orange, jaune) et un tube vide, il y a 995 façons de distribuer (sans compter l’ordre des tubes et les changements de couleurs), dont 236 insolubles. Même en se limitant aux donnes équitables, sans tube où une même couleur se répète 3 fois ou plus, 198 sur 736 (environ 27 %) sont insolubles.
Cette donne aussi ne peut être triée quoi qu’on fasse. Le premier coup va forcément dans le tube vide 4, et quel que soit celui des trois choix retenu, on finit dans une impasse.
Avec deux tubes vides
Avec deux tubes vides, tout change.
- Les donnes à 2 couleurs et 2 tubes vides, et à 3 couleurs et 2 tubes vides, étaient toutes solubles.
- Même à 4 couleurs et 2 tubes vides (la taille de ★1), les 111 383 types, y compris les donnes non équitables, étaient tous solubles (Combien de façons de distribuer ?).
Il suffit d’un tube vide de plus pour que les donnes insolubles disparaissent. C’est pourquoi, en ★5, qui n’a qu’un seul tube vide, la plupart des donnes sont insolubles (Comment on crée des grilles toujours solubles).
