Pentaminos
Les pentaminos sont les pièces de puzzle représentées ci-contre.
Ce sont les 12 pièces différentes que l'on peut obtenir en joignant
5 cubes identiques côté par côté.
Le but du jeu (du casse-tête) est de reconstituer une forme donnée, plane
ou volumique. Le plus souvent, il s'agit de les ranger dans une grille
de taille 8 x 8 dont 4 cases données doivent rester vides.
Voici quelques exemples :
mais il y en a beaucoup d'autres.
J'ai entrepris un jour de dénombrer le nombre de solutions possibles,
pour une grille donnée.
J'ai réalisé un petit programme pour cela, d'abord en C, puis en
Objective Caml. C'est un algorithme de backtracking, que l'on stoppe
dès qu'une zone restant à remplir n'a plus une aire multiple de 5.
Quelques solutions données par le programme.
Vous pouvez récupérer :
Variante
Une variante consiste à ranger les 12 pentaminos dans un
rectangle. Voici le nombre de solutions (aux 4 symétries près) :
Le programme en Caml
Jean-Christophe Filliâtre
(formatté avec yamlpp).
