Page d'accueil(allemand)     Choses ordinateur(allemand) [english version]     [deutsche Version]

Le jeu de pentominos

C'est aussi un casse-tête connu: 5 carrés sont mis ensemble dans toutes manières possibles. Ansi ils se forment 12 pièces, les "pentominos". Alors le problème est de couvrir certaines formes, par exemple les rectangles, avec ces pentominos. Bien qu'il y a 2339 solutions pour le 6x10 rectangle (plus solutions dérivées via rotations et réflexions), il est assez difficile de trouver une seule solution manuellement. Le problème semble idéal pour un ordinateur.


+---+---------------+---+-----------+-------+---+-------------------+---+-------+
|   |               |   |           |       |   |                   |   |       |
|   |   +-------+---+   +---+   +---+   +---+   +-------+-------+---+   +---+   |
|   |   |       |           |   |       |   |           |       |           |   |
|   +---+---+   +-------+   |   |   +---+   +-------+   |       +---+   +---+   |
|           |           |   |   |   |               |   |           |   |       |
+-----------------------+---+---+---+---------------+---+-----------+---+-------+

Le programme suivant génère les pentominos (ou si on veut aussi les hexominos, septominos etc.) automatiquement, et puis cherche les solutions sur des formes arbitraires (pas seulement des rectangles).

Il s'agit d'un programme ANSI-C avec une sortie ascii. Alors il courait sur tous les systèmes d'expoitation et compilerait (peut-être avec des adaptations minimaux) avec tous les compilateurs C. Il est bien modularisé et peut être compris simplement même de programmateurs débutants (je pense).

Ici sont les durées d'execution pour les pentominos et les rectangles sur un Pentium1 avec 166MHz:

mesures du rectangledurée d'execution
10x612min 38s
12x54min 7s
15x458s
20x63s

Téléchargement: pentominos.c.gz (5KB).


Page d'accueil(allemand)     Choses ordinateur(allemand) by Michael Becker, 2/2002. Dernière modification 2/2002