Partie 7 : les pentaminos

question 7.1. Il n'existe que 12 pentaminos.

La justification logique rigoureuse est assez délicate. Il y a au moins deux modes logiques possibles : la dichotomie, qui consiste à séparer l'ensemble étudié suivant des critères de plus en plus fins, pour arriver à des objets uniques ou peu nombreux "évidents" ; la récurrence, qui se fonde sur l'engendrement nécessaire des objets à partir d'objets plus simples.

 

Voici une démonstration utilisant une méthode récurrente.

Quant à son principe, il est basé sur la technique de l'épluchage de l'oignon. Pour faciliter l'exposé, nous appellerons mino(p,k) tout assemblage selon les règles de p carrés, tel qu'il y ait au maximum k carrés alignés ; ainsi un mino(p,p) est une barre ; un mino(p,2) n'a jamais plus de 2 carrés alignés; il n'y a évidemment pas de mino(p,1) avec p>1.

* proposition 1.

Pour p>k on peut toujours transformer un mino(p,k) en mino(p-1,k) en enlevant un carré.

On commence par marquer une (ou la) ligne à k éléments du mino(p,k) ; c'est le cœur du mino, noté pelure(0).

Puis on marque le(s) carré(s) qui colle(nt) à pelure(0) ; on appelle l'ensemble de ces carrés pelure(1) ; cette pelure(1) n'est pas vide car la barre a été exclue.

On construit de même la pelure(2) sur la pelure(1) et ainsi de suite.

Le processus s'arrête sur la pelure(n), avec n > 0. Si on enlève un carré quelconque de cette dernière pelure, on ne rompt pas la connexité de l'assemblage car les autre carrés d'ordre n collent à ceux d'ordre (n-1) ; on obtient donc un mino(p-1,k).

 

exemples d'épluchages d'un mino(6,2) :

 

 

 

* proposition 2.

Pour n>p, tous les mino(n,p) s'obtiennent à partir des minos(n-1,p).

Les mino(p,k), c'est une conséquence directe de la proposition précédente,  s'obtiennent à partir des mino(p-1,k) en ajoutant un carré à leur dernière pelure ou une pelure supplémentaire, si c'est possible sans créer de ligne de plus de k éléments (voir par exemple ci-desous les mino(4,2)).

* proposition 3.

Le mino(p,p) s'obtient à partir du seul mino(p-1,p-1).

* la récurence. On part du domino, mino(2,2), qui est unique. On peut alors suivre dans le tableau suivant la génération des triminos, puis des tétraminos, puis des pentaminos :  

 

question 7.2.

* Les 5 pièces qui n'ont aucune symétrie interne engendrent 8 instances distinctes (les mathématiciens appellent "groupe du carré" l'ensemble des 8 transformations qui permettent de reposer un carré sur sa trace initiale).

* La pièce qui a comme seule symétrie une symétrie centrale engendre directement 2 instances et par retournement 2 instances également.

* Les 4 pièces qui ont comme seule symétrie une symétrie axiale engendrent 4 instances par rotation.

* La croix qui a deux symétries axiales et une symétrie de rotation par quart de tour n'a qu'une instance.

* La barre engendre deux instances.

Soit en tout : 5x8 + 4 + 4x4 + 1 + 2 = 63 instances.

La restriction concernant les solutions identiques par rotation et retournement ramène le nombre des instances utiles à 56. Ce sont ces 56 possibilités qui sont présentées dans le logiciel d'accompagnement (onglet "symétrie des pièces").  

question 7.3.

Il était rappelé dans l'énoncé que la calcul brutal ne permet pas de trouver à lui tout seul les solutions. Il faut donc trouver un procédé pour limiter fortement la recherche arborescente des positions.

Le premier principe retenu dans notre solution est de chercher à placer sur la grille les instances dans l'ordre de leur numéros de pièces, chacune des instances d'une pièce étant essayée successivement. C'est un calcul classique d'arbre, où une pile permet de revenir en arrière.

Ce calcul n'a aucune chance d'aboutir, mais il a un intérêt que les expérimentateurs ont certainement remarqué : très rapidement, on voit qu'il est inutile de continuer la recherche ; pour la bonne raison que si au moins un trou sur la grille ne comporte pas un multiple de 5 carrés, l'échec est patent. Il suffit donc de ne poser un pentamino que si son placement produit des îlots comportant un multiple de 5 carrés. La procédure qui a été proposée dans l'exercice d'algorithmique, est assez performante ; elle convient très bien pour compter les carrés d'un trou, au prix d'adaptations mineures. Cette procédure est extrêmement efficace pour limiter les calculs. Il existe d'autres procédés de comptage des carrés des îlots, plus simples et moins rapides, mais qui conviennent parfaitement (nous en avons testé une autre qui dénombre les carrés libres d'un îlot en essayant de remplir les quatre carrés adjacents au carré de départ, et en recomençant le processus avec chaque carré qui a été rempli ; c'est un problème de pile : il suffit d'empiler chaque carré rempli ; court à programmer, pas très élégant, mais ça marche).

Le logiciel, interface mise à part (c'est finalement elle qui est la plus coûteuse en programmation), se déroule ainsi :

* mise en place des structures de données : codage des 56 instances dans un tableau ; chaque instance a la forme d'un "enregistrement" (un tableau est moins adapté, mais tout aussi acceptable) qui comporte par rapport à un carré de base (non codé), les coordonnées des 4 autres carrés, ainsi que les coordonnées de la diagonale principale du rectangle qui enclôt l'instance (ce qui rend plus pratique la recherche des positions possibles sur la grille de fond). Un tableau annexe permet de relier les instances et les numéros de pièces.

* définition des procédures de placement d'une pièce avec ses composantes : recherche de la place disponible ; test de compatibilité des îlots formés avec la nécessité qu'il contiennent un multiple de 5 carrés.

* une machine à pile organisant les essais : déplacement d'une instance en cas d'échec de placement, changement d'instance en cas d'échec de déplacement, retour sur la pièce précédente en cas d'échec de toutes les instances... Le logiciel et ses sources sont intégralement sur le site.

L'écriture en Pascal-Delphi autorise une lecture aisée des algorithmes, un éditeur suffit (le fichier a une extension en .pas) ; le programme est facilement transposable dans tout autre langage structuré (un peu plus lourd si on utilise le tableau comme structure de représentation, mais tout à fait fonctionnel) .

les solutions sur un rectangle de 60 carrés.

10x6 6x10 12x5 5x12 15x4 4x15 20x3 3x20
1426 913 758 252 248 120 0 2

  

téléchargement :