Les grilles de l’app Sort Puzzle ne sont pas préparées à l’avance : elles sont créées sur le moment, à chaque partie. Pourtant, chaque grille est proposée après vérification qu’elle est soluble. Voici comment.

Les étapes

  1. Choisir les couleurs : parmi les 10 couleurs, en prendre autant que la difficulté l’indique (4 couleurs pour ★1).
  2. Mélanger et distribuer : rassembler 4 éléments de chaque couleur choisie, mélanger, puis remplir les tubes colorés à 4. Les tubes vides sont placés à droite.
  3. Écarter les tubes presque triés : si un tube contient 3 éléments de même couleur ou plus à la suite, on n’utilise pas cette donne. Un tube presque trié dès le départ est ennuyeux.
  4. Vérifier que c’est soluble : le solveur cherche la suite de coups jusqu’au tri. S’il n’en trouve pas, la donne n’est pas utilisée.
  5. Regarder la condition de piège : à partir de ★3, on cherche s’il y a un « piège » où l’on est bloqué si l’on choisit toujours le coup qui semble bon sur le moment, et on redistribue jusqu’à remplir la condition de la difficulté (Les grilles à pièges).
123456
Un exemple de grille ★1 créée ainsi

À chaque création, l’app répète ces étapes jusqu’à trouver une donne qui remplit les conditions. Même en ★5, créer une grille prend au plus quelques dizaines de millisecondes.

Combien de donnes tirées au hasard sont solubles ?

Combien de donnes l’étape 4 écarte-t-elle ? J’ai distribué de la même façon que l’app et, pour les « donnes équitables » (sans tube où une même couleur se répète 3 fois ou plus), vérifié en examinant tous les cas si elles sont solubles.

DifficultéDonnes équitablesDonnes solubles
★1 (4 couleurs · 2 libres)416416
★2 (6 couleurs · 2 libres)431431
★3 (8 couleurs · 2 libres)453453
★4 (10 couleurs · 2 libres)460460
★5 (9 couleurs · 1 libre)453929

De ★1 à ★4, avec deux tubes vides, toutes les donnes équitables comptées étaient solubles. En revanche, en ★5, avec un seul tube vide, seulement 29 sur 4539 (0,64 %) étaient solubles. Les autres sont des donnes qu’aucune suite de coups ne permet de trier.

Avec un seul tube vide, c’est vite insoluble

J’ai aussi compté, avec un seul tube vide, comment la part de donnes solubles change selon le nombre de couleurs.

Nombre de couleurs (1 libre)Part de donnes solubles
3 couleurs72,7 %
4 couleurs44,9 %
5 couleurs26,3 %
6 couleurs14,0 %
7 couleurs6,0 %
8 couleurs2,3 %
9 couleurs0,64 %

À chaque couleur de plus, la part de donnes solubles est à peu près divisée par deux, et au-delà quand il y a beaucoup de couleurs. Avec un seul tube vide, le premier coup va forcément dans le tube vide et il reste peu de chemins ensuite : voilà sans doute l’explication (Résoudre ★5 (1 tube libre)).

L’astuce pour fabriquer ★5

En ★5, les donnes solubles sont rares : l’app redistribue donc jusqu’à 400 fois. Si elle n’en trouve toujours pas, elle passe à une autre méthode.

  • Défaire une grille triée : on part d’une grille triée et on la défait au hasard avec des coups en sens inverse. En rejouant à l’envers les coups faits, on retrouve forcément la grille triée : c’est donc garanti soluble.

En créant 500 grilles ★5 de la même façon que l’app, 18 étaient de ces grilles « défaites ». Dans une grille défaite, les tubes ne sont pas toujours remplis à 4.

Une même graine donne la même grille

Le générateur de nombres aléatoires utilisé pour créer les grilles (SplitMix64) produit toujours la même suite quand on fixe un nombre, la « graine ». Avec la même graine, on obtient la même grille. La grille de Jouer en ligne de ce site crée aussi ses grilles avec les mêmes étapes que l’app.

Le fonctionnement du solveur qui vérifie qu’une grille est soluble est présenté dans Résoudre avec un ordinateur.