Pentomino

Un article de Wikipédia, l'encyclopédie libre.
Ceci est une version archivée de cette page, en date du 16 mai 2014 à 14:20 et modifiée en dernier par 86.65.208.134 (discuter). Elle peut contenir des erreurs, des inexactitudes ou des contenus vandalisés non présents dans la version actuelle.
Les 18 formes possibles d'un pentomino - si l'on tient compte de l'orientation

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 pentominos 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 pentominos 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 pentomino 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 pentominos pouvant s'orienter de deux façons, chacun est l'image de l'autre (par exemple, le svastika).[pas clair]

Par exemple, les huit tuiles possibles du Y sont :

Pavage de rectangles

Exemple de pavage
Exemple de pavage

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 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[3] 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[4] 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[5], 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.

Nombre de solutions[6]
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 à 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 des stratégies qui garantissent la victoire au joueur qui joue en premier[7].

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. 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 la nouvelle Imperial Earth d'Arthur C. Clarke, 1975 (traduction française : Terre, planète impériale par H. Gallet, 1977).

Alexei Pajitnov semble s'en être inspiré pour créer le jeu Tetris.

Notes et références

Notes

  1. ↑ 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.
  2. ↑ Marque de commerce enregistrée auprès de l'USPTO sous le numéro 1008964 le 15 avril 1975

Références

  1. ↑ (en) Henry Ernest Dudeney, The Canterbury Puzzles, 1907, chapitre 74 - The Broken Chessboard.
  2. ↑ (en) Pentominoes"" sur le site ma.utexas.edu.
  3. ↑ (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.
  4. ↑ (en) Dana S. Scott, Programming a Combinatorial Puzzle, Technical Report No. 1, Department of Electrical Engineering, Princeton University.
  5. ↑ (en) Donald E. Knuth, Dancing Links (fichier Postscript de 1,6 Mo, comprend un résumé des articles de Scott et Fletcher).
  6. ↑ (fr)Pentomino 2D et 3D. [1]
  7. ↑ 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

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Pentomino&oldid=103858869 ».