Pentomino
Un pentomino ou pentamino[Note 1] est une figure géométrique constituée de 5 carrés accolés par un de leurs côtés, c'est un cas particulier de polyomino.
Les problèmes concernant les pentominos consistent à déterminer comment paver une surface donnée avec des objets de cette forme. On trouve un des premiers problèmes de ce genre[1] dans le livre de Henry Dudeney de 1907[2], The Canterbury Puzzles. L'étude des pavages est entreprise par Solomon W. Golomb autour des années 1960. Golomb invente les noms de polyomino et de pentomino ; il est également le créateur d'un jeu de société « Pentominoes » et en a fait une marque déposée[Note 2], mais ce nom n'est plus protégé depuis 1982.
Description
Il y a douze formes « libres » de pentominos, chacune étant identifiée par une lettre : L, T, V, Z, N, F[Note 3], X, W, P, I, Y et U.
Si on distingues les images miroir comme étant des formes différents, on dénombre 18 formes « unilatérales ». Ce nombre n'est pas 24 car six pentominos (T, V, I, X, U et W) possèdent une symétrie les rendant identiques à leur images miroir. Cette distinction est importante lorsque les seules manipulations autorisées sont le déplacement (translation) et la rotation, comme par exemple dans Tetris.
Lorsqu'on applique des rotations de 90 degrés, on obtient de nouvelles formes appelées « configurations »[3]. On remarque alors de nouvelles propriétés de symétrie :
- L, N, P, F et Y peuvent donner naissance à 8 formes : 4 par rotation et 4 par image miroir.
- Z donne naissance à 4 formes : 2 par rotation et 2 par image miroir.
- T, V, U et W donnent naissance à 4 formes par rotation.
- I donne naissance à 2 formes par rotation.
- X ne peut donner naissance qu'à une seule forme.
Par exemple, les huit configurations possibles du Y sont :
Pavage de rectangles
Avec les pentominos, le puzzle classique est de paver une surface rectangulaire sans trou et ni chevauchement. Chaque pentomino, au nombre de 12, contient 5 carrés. En conséquence, le rectangle doit faire 60 carrés de surface ; les seules dimensions possibles sont donc 6×10, 5×12, 4×15 et 3×20. Les joueurs les plus motivés parviennent à les compléter en quelques heures à la main.
Un défi plus exigeant est de dénombrer le nombre total de solutions possibles. C'est habituellement résolu à l'aide d'un algorithme d'énumération.
John G. Fletcher[4] a le premier résolu le cas 6×10 en 1965 : il y a exactement 2 339 solutions, en excluant les variantes triviales (rotations et réflexions du rectangle), mais en incluant les rotations et les réflexions d'un sous-ensemble du rectangle. Le rectangle 5×12 possède 1 010 solutions, le rectangle 4×15 a 368 solutions, et le rectangle 3×20 a seulement 2 solutions.
Un puzzle nettement plus facile, car plus symétrique, est le carré 8×8 qui contient un trou 2×2 en son centre. Dana S. Scott[5] l'a résolu en 1958 en dénombrant 65 solutions. Son algorithme est l'un des premiers à appliquer le retour sur trace.
D'autres algorithmes sont apparus avec les années. Donald Knuth[6], figure emblématique de l'informatique, en a mis un au point qui est particulièrement efficace. Grâce à lui, un ordinateur moderne ne prend que quelques secondes pour trouver toutes les solutions.
Autres problèmes
Outre l'échiquier avec trou central cité dans le paragraphe précédent, de nombreux autres problèmes existent.
Dans l'échiquier, on peut répartir les quatre trous de diverses façons (aux quatre coins par exemple).
La cour de ferme consiste à faire un rectangle contenant un trou rectangulaire. Il s'agit donc d'un rectangle de surface (60+n), n étant la surface de la cour. La plus petite est le rectangle 7×9, avec une cour 3×1. Il semblerait que la plus grande soit le rectangle 8×11, avec une cour 4×7.
On peut aussi réaliser un rectangle contenant un trou ayant la forme d'un pentomino.
La triplication : reproduire (avec seulement 9 pièces) un pentomino à l'échelle 3 sans utiliser la pièce agrandie.
| Pentomino | F | I | L | N | P | T | U | V | W | X | Y | Z |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Solution | 125 | 19 | 113 | 68 | 497 | 106 | 48 | 63 | 91 | 15 | 86 | 131 |
Enfin, on peut passer à la dimension supérieure, avec les pentacubes, pentominos ayant une épaisseur de 1. On tentera alors de les ranger dans le parallélépipède 3×4×5 (3940 possibilités), dans le parallélépipède 2×3×10 (12 possibilités), dans le parallélépipède 2x5x6 (264 possibilités), ou dans des pentominos à l'échelle 2×2×3.
Jeux
Le jeu de société Pentominoes se joue à l'aide d'une grille 8×8. Les joueurs, au nombre de deux ou trois, placent un pentomino chacun son tour de façon qu'il n'y ait pas de chevauchement, et que chaque tuile soit utilisée une seule fois. Le gagnant est le dernier joueur à placer une tuile sur la grille. Il existe des stratégies qui garantissent la victoire au joueur qui joue en premier[8].
Une variante, Blokus, se joue sur une grille 20×20, avec de deux à quatre joueurs. Pour déposer un pentamino, il doit toucher un pentamino de même couleur par un coin et ne chevaucher aucun autre pentamino.
Les pentominos sont à la base de divers jeux à un seul joueur qui demandent de paver une surface ou de résoudre un puzzle (par exemple KATAMINO). Les pièces peuvent être en bois ou dans d'autres matières, ou dématérialisées dans différents programmes informatiques et jeux en ligne.
Anecdotes
Les pentominos sont décrits avec maints détails dans le roman Terre, planète impériale d'Arthur C. Clarke, 1975 (titre original : Imperial Earth par H. Gallet, 1977).
Alexei Pajitnov semble s'en être inspiré pour créer le jeu Tetris.
Notes et références
Notes
- Concernant le nom :
- le nom originellement choisi par Solomon W. Golomb est pentomino ;
- on trouve les deux versions de ce néologisme pentamino et pentomino dans les études en français ;
- le jeu est commercialisé en France sous le nom pentamino chez Arteludes et Jeandel ;
- le nom pentamino est bien formé en français, par accolage de penta- (du grec πέντε, pente, cinq) qui a donné par exemple pentagone et pentagramme et de -mino (du latin dominus, -i, maître) ;
- les articles en français emploient un pluriel francisé pentaminos ou pentominos, tandis que les articles en anglais se tiennent à pentominoes.
- Marque de commerce enregistrée auprès de l'USPTO sous le numéro 1008964 le 15 avril 1975
- Le pentomino F est également nommé R dans le contexte du jeu de la vie de Conway
Références
- (en) Henry Ernest Dudeney, The Canterbury Puzzles, 1907, chapitre 74 - The Broken Chessboard.
- (en) Pentominoes"" sur le site ma.utexas.edu.
- « Images des mathématiques », sur images.math.cnrs.fr (consulté le )
- (en) John G. Fletcher, A Program to Solve the Pentomino Problem by the Recursive Use of Macros, Communications of the ACM, 8, 1965, pages 621 à 623.
- (en) Dana S. Scott, Programming a Combinatorial Puzzle, Technical Report No. 1, Department of Electrical Engineering, Princeton University.
- (en) Donald E. Knuth, Dancing Links (fichier Postscript de 1,6 Mo, comprend un résumé des articles de Scott et Fletcher).
- (fr)Pentomino 2D et 3D. [1]
- Orman, Hilarie K. “Pentominoes: A First Player Win”. Games of No Chance, MSRI publications, Vol. 29, 1996, pp. 339-344.L'article indique deux « premiers coups » susceptibles de mener à la victoire.
Voir aussi
Articles connexes
Liens externes
- Pentominos, site de Gérard Villemin
- Boîte de pentaminos, jeu en bois chez Arteludes
- Pentamino, jeu en bois chez Jeandel
- Pentamino, iOS jeu dans iTunes par Pentamino, Inc.
- (en) Pentominos Puzzle Solver, une applet Java qui résout le carré 8*8 avec 4 trous
- (en) Pentominoes Solver and Game, logiciel libre sous Windows 32
- (en) Logic, numbers, and pictures puzzle games, jeux en ligne, dont les pentaminos
- (en) Pentominoes, jeu en ligne
