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.

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érentes, 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 :

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.

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.

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.

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.

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.

• Pavage
• Variantes du Sudoku
• Polyomino
• Blokus
• Minecraft
• Reptuile

• Pentominos, site de Gérard Villemin
• (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

• Portail des jeux
• Portail de la géométrie