Sommaire

Page d'accueil
Ma thèse
Les pentaminos
Images de pentaminos
Pentaminos en Java
Un papier

Les pentaminos

-= O =-

Introduction

Les pentaminos sont des pièces connexes formées de 5 cubes assemblés dans le plan. Il en existe 12 différents, notés F, I, L, P, N, T, U, V, W, X, Y et Z en raison de leur forme.

Un probleme intéressant est de placer ces pentaminos dans un volume de dimension donnée ; les cas les plus difficiles sont ceux où le volume est un bloc dont le produit hauteur x longueur x largeur est égal à 60 (5 cubes pour chacun des 12 pentaminos, soit 60 cubes à placer).

Un peut aussi essayer de les placer sur le classique échiquier 8x8, en ayant eu soin au préalable de fixer la position des 4 cases qui seront vides.

Le nom "pentaminos" a été créé par Solomon W.Golomb en 1953 dans une présentation qu'il fit au Harvard Mathematics Club, mais le premier problème sur les pentaminos fut publié en 1907 dans les Canterbury Puzzles par Henry Ernest Dudeny.

Programmes

Il est plus facile de faire résoudre un problème de pentaminos par un ordinateur qu'essayer de le faire a la main. Voici un programme prolog qui place très rapidement les douze pentaminos sur un plateau de dimensions 6 x 10. Son fonctionnement est simple : on considère que le plateau est un ensemble de variables libres que l'on unifie avec une des orientations possibles de chacun des pentaminos. Toutes les orientation des pentaminos ont été precodées a la main.

Voici un programme C fonctionnant suivant le même principe mais qui lui calcule les différentes orientation dans l'espace (il existe 24 orientations possibles pour certains pentaminos, les coder manuellement aurait été trop complexe). Ce programme parcours rapidement l'espace des solution de tous les problèmes de placement de pentaminos dans un volume de dimension longueur x largeur x hauteur tels que longueur x largueur x hauteur = 60.

Le probleme de placement des pentaminos peut aussi être résolu par un programme de contraintes. Ces notes de travail décrivent un systeme de contraintes sur les entiers qui résolvent les pentaminos.

Voici les premières solutions pour certains problèmes de placement tridimensionnel :


Le 3 x 4 x 5 : 3940 solutions,


le 2 x 5 x 6 : 264 solutions,


le 2 x 3 x 10 : 12 solutions,

Liens

Guenter Albrecht-Buehler, Logical Art and the Art of Logic, http://pubweb.acns.nwu.edu/~gbuehler/introd.htm.

Gilles Esposito-Farese The Pentomino Dictionary, http://cpt.univ-mrs.fr/~gef/pento.html.

Combinatoric Object Server, http://sue.csc.uvic.ca/~cos/cos.html.

Anna Gardberg, Anna's Pentomino Page, http://www.geom.umn.edu/~summer95/gardberg/pent.html.

Stefan Wolfrum, Mind Puzzles, http://titan.cs.uni-bonn.de/~wolfrum/puzzles.html.

Livio Zucca, Pentamini pentaminos pentomino, http://www.geocities.com/liviozuc/.

Andrew Clarke, The Poly Pages, http://www.geocities.com/alclarke0/.

Références

C. Berge, C. C. Chen, V. Chvatal and C. S. Seow, Combinatorial Properties of Polyominoes, Combinatorica 1, 1981, pages 217-224.

J. H. Conway and J. C. Lagrias, Tiling with Polyominoes and Combinatorial Group Theory Journal of Combinatorial Theory, A53, pages 183-208

G. E. Martin, Polyominoes: A Guide to Puzzles and Problems in Tiling Mathematical Association of America, Spectrum Series, 1991

Solomon W. Golomb, Pentominoes, Princetown University Press, Princetown, New Jersey, 1994, pages 6-10, 148.

Barry Onslow, Pentominoes Revisited, American Teacher, May 1990, v37, n9, pages 5-10.

Dyanne Tracy, Five Good Reasons to Use Pentominoes, School Science and Mathematics, December 1990, v90, n8, pages 665-674.

Martin Gardner, Hexaflexagons and Other Mathematical Diversions, First Scientific American Book of Mathematical Puzzles and Games, 1958, 1988