Célèbre casse-tête / puzzle logique constitué des 12 uniques éléments possibles à réaliser avec 5 cubes juxtaposés (en plan). Le but est de reconstituer un rectangle, un parallélépipède ou d'autres formes remarquables avec toutes les pièces. (rectangle 6x10, 5x12, brique 3x4x5...). J'ai fabriqué un set de pentomino en bois et les solutions sont difficiles à trouver à la main malgré leur nombre conséquent (2339 pour le 6x10). J'essaie ici une approche de résolution algorithmique du problème.
temps : -- sec.
ordre : --
avancement : --
Tout d'abord, les 12 pentominos sont créés et pour chacun, on liste toutes les positions, rotations et miroirs possibles. Le "X" n'a qu'une manière d'être tourné, les pièces "T, V, U, W" en ont 4 et les autres 8. Chaque position est un tableau 6x10. Par exemple pour le "T" :
. . . . . . . . . . . . . X . . . . . . . . . X X X . . . . . . . X . . . . . . . . . . . . . . . . . . . . . . . . . .
Une fonction de shuffle réordonne aléatoirement la liste des pentomino. Il y a !12 permutations permises soit 479 001 600 (factorielle de 12) ordres possibles.
Ce genre de processus de recherche de solution est de type "back track" ou algorithme dit de "retour sur trace" :
On répète le processus jusqu'à épuisement des pièces et des positions (le puzzle est alors complet et l'algorithme s'arrête).
Pour tester si une position est autorisée au non, on vérifie d'abord qu'il n'y a aucun chevauchement sur une pièce déjà posée. Ensuite, on vérifie que toutes les zones vides fermées créées contiennent nombre de case divisible par 5 (sinon, aucune(s) pièce(s) ne pourraient combler ce trou et le puzzle ne pourrait plus être terminé, il est donc inutile de poursuivre l'algorithme avec cette configuration).
Pour donner un ordre de grandeur de l'ensemble des combinaisons de positions, on peut lister le nombre de positions possibles pour chaque pièce :
X = 32 I = 56 J = 248 T = 128 Y = 248 N = 248 W = 128 Z = 128 V = 128 P = 304 U = 152 F = 256
En multipliant ces nombres entre-eux, on obtient le nombre astronomique de : 8,6794 e25 soit 86 millions de milliards de milliards ce qui reste très grand, même pour un ordinateur. On comprend l'importance d'éliminer les solutions qui ne mèneront à rien le plus tôt possible dans le déroulement de l'algorithme.
Tel quel, ce solver n'est pas très satisfaisant et très lent. Il parviendra tout de même à une solution dans un temps situé entre 1 secondes et 3 minutes. Il n'est pas garanti que des combinaisons déjà testées ne seront pas testées à nouveau au prochain run du solver. Il se peut que le navigateur se plaigne et que les ventilateurs se mettent à souffler...
Comme d'habitude, les recherches sur le sujet m'ont conduit à trouver divers sites de passionnés qui couvrent assez largement la question. J'ai trouvé des listes exhaustives de solutions et quelques programmes.
Une page de Jean-Christophe Filliatre, chercheur au CNRS et enseignant en computer science, propose un solver en C, pour la résolution du problème au format 8x8 (dont 4 cases vides). J'ai compilé ce code avec succès, l'algorithme est vraiment performant mais vraiment difficile à comprendre (pour moi).
Une autre page intéressante, de Gérard Villemin.
Voir également cette page et celle-ci (cette dernière donne quelques pistes pour écrire un programme).