- Pentamino
-
Un pentamino est un polyomino composé de cinq carrés connexes.
Sommaire
Description
Il y a douze pentaminos différents en tout, chacun étant identifié par une lettre de l'alphabet.
Si nous comptons les images miroir comme étant des pentominos différents, alors il y en a 18 en tout. Les pentaminos nommés T, V, I, X, U et W ont la même image miroir. Cette distinction est importante dans certains jeux vidéo qui ne tolèrent pas les images miroirs, tel que des variantes de Tetris. Le pentamino F est souvent nommé R, en référence au jeu de la vie de Conway.
Si les rotations de 90 degrés sont considérées, alors des catégories de symétrie apparaissent :
- 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.
Pour les figures planes en général, il existe une catégorie supplémentaire : les pentaminos pouvant s'orienter de deux façons, chacun est l'image de l'autre (par exemple, le swastika).
Par exemple, les huit tuiles possibles du Y sont :
Pavage de rectangles
Avec les pentaminos, le puzzle classique est de paver une surface rectangulaire sans trou et ni chevauchement. Chaque pentamino, au nombre de 12, contient 5 carrés. En conséquence, le rectangle doit faire 60 carrés de surface ; les 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[1] 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[2] 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[3], 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çon (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 pentamino, ou reproduire (avec seulement 9 pièces) un pentamino à l'échelle 3.
Enfin, on peut passer à la dimension supérieure, avec les pentacubes, pentaminos ayant une épaisseur de 1. On tentera alors de les ranger dans le parallélépipède 3×4×5, ou dans des pentaminos à l'échelle 2×2×3.
Anecdotes
Les pentaminos sont décrits avec maints détails dans la nouvelle Imperial Earth d'Arthur C. Clarke, 1975 (traduction française : Terre, planète impériale par H. Gallet, 1977).
« Pentominoes » était une marque déposée enregistrée au nom de Solomon W. Golomb (brevet USPTO #1008964, 15 avril 1975), mais ce nom n'est plus protégé depuis 1982.
Alexei Pajitnov semble s'en être inspiré pour créer le jeu Tetris.
Jeux de société
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 pentamino chacun son tour de façon à ce 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 un algorithme, si certaines contraintes sont respectées, qui garantit la victoire au joueur qui joue en premier.
Les pentaminos et leurs variantes sont à la base de divers jeux qui demandent de paver une surface ou de résoudre un puzzle.
Voir aussi
Articles connexes
Liens externes
- (fr) Pentaminos et autres polyominos (site de Gérard Villemin)
- (en) Relations entre les pentominos
- (en) Solutionnaire de puzzle avec pentominos (une applet Java qui résout le carré 8*8 avec 4 trous).
- (en) Original Tetris (application Flash)
- (nl) et (en) Pentomino.nl (application Shockwave avec solutions en ligne)
- (en) Pentominoes, un petit jeu de puzzle.
Sources
- John G. Fletcher, A Program to Solve the Pentomino Problem by the Recursive Use of Macros, Communications of the ACM, 8, 1965, p.621–623.
- Dana S. Scott, Programming a Combinatorial Puzzle, Technical Report No. 1, Department of Electrical Engineering, Princeton University.
- Donald E. Knuth, Dancing Links (fichier Postscript de 1,6 Mo. Inclus un résumé des articles de Scott et Fletcher.)
Wikimedia Foundation. 2010.
