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
Homepage American
Jean-Christophe Filliâtre (formatté avec yamlpp).