Devoir maison 1

Pentomino

Le but de ce devoir maison est d’utiliser le solveur de programmation par contrainte que nous avons écrit en cours pour résoudre un problème de pavage.

Vous pouvez utiliser votre code ou ce code pour votre devoir.

Le problème

Pour les définitions du problème de pavage d’une grille par des pentominos nous référons à la page wikipédia.

En gros vous disposez de 12 formes appelés pentominos, composées chacune de 5 cases unitaires, que vous devez placer sur une grille composée de 60 cases. Les formes ne doivent pas se superposer, mais peuvent être tournées ou retournées.

Votre programme prendra en argument de ligne de commande une chaîne de la forme [m]x[n], indiquant les dimensions de la grille à paver. Les seules entrées possibles sont 6x10, 5x12, 4x15, 3x20. Puis votre programme devra afficher un pavage possible, sous forme d’un tableau de lettres, puis un entier indiquant le nombre de pavages au total, à symmétrie près.

Affichage attendu par votre programme.

./pentomino.py 6x10
IPPYYYYVVV
IPPXYLLLLV
IPXXXFZZLV
ITWXFFFZUU
ITWWNNFZZU
TTTWWNNNUU
2339

Le pavage fourni est une sélection arbitraire de toutes les solutions, et dans cet exemple il correspond au pavage suivant.

Votre travail

Comme il n’y a que 4 entrées possibles à votre code vous pourriez être tenté de les stocker dans le code et d’afficher la réponse demandée. Mais pour ce devoir maison on vous demande de calculer la solution à l’aide de notre solveur de programmation par contrainte.

Pour cela vous devez modéliser le problème de pavage. Décrivez votre modèle précisément dans un document qui accompagnera le code. Indiquez également comment vous avez éliminé les solutions symmétriques.

Par préférence faites ce travail par binôme.

Rendre avant le 18 décembre

Simplement par courrier éléctronique à votre enseignant, Christoph Dürr.