Le Projet PENTAS

Contexte

Les Pentaminos

Les pentaminos sont les éléments d'un jeu de puzzle, composés de 5 petits carrés contigus, donc de formes géométriques particulières. Au nombre de 12, composés de 5 carrés élémentaires, ils peuvent couvrir une surface de 5 x 12 = 60.

figure extraite de l'article de D. Knuth.

Par exemple, la figure ci-dessus représente un exemple de puzzle terminé, sur lequel on peut repérer les différents pentaminos par leur couleur.

Le puzzle ci-dessus est un carré parfait de 8 x 8 = 64 : il faut noter que le carré central blanc, de surface 2 x 2 = 4 carrés élémentaires, n'est pas un pentamino, mais une zone interdite. La surface couverte par les pentaminos colorés est donc bien de 60.

Le Puzzle

La figure ci-dessous, tirée de wikipédia, représente les différents pentaminos disponibles. On a l'habitude de les repérer par une lettre.

Toute surface de 60 carrés élémentaires peut donc être un puzzle à pentaminos. La page wikipédia représente d'ailleurs les puzzles de taille 3 x 20, 4 x 15, 5 x 12, ou encore 6 x 10.

Le Projet

Présentation

L'objectif du projet est double : résoudre le puzzle pour une taille donnée, et donc trouver l'ensemble des solutions disponibles. Ensuite, trouver une solution électronique pour afficher les solutions trouvées, de façon à réaliser un démonstrateur lors des Journées Portes Ouvertes de l'IUT. Ce démonstrateur repose nécessairement sur l'utilisation de la carte Arduino Uno.

Solution

De très nombreuses solutions existent sur internet pour répondre au problème posé. Mais lors de ce projet, la méthode de résolution ainsi que le langage de programmation sont imposés :

• la résolution doit suivre le principe exposé par Don Knuth dans son article Dancing Links (disponible en pièce jointe),
• le langage de programmation est Python 2.7.x,

Sources documentaires

• la page Python + ensemble de documents Python sur internet,
• article de Don Knuth, Dancing Links, Stanford University, 1999.

Objectifs

Il est donc demandé de :

• mettre en place l'algorithme Dancing Links en POO Python,
• afficher les résultats sous forme graphique,
• prévoir un dispositif électronique permettant de visualiser la recherche du puzzle solution, en utilisant un dispositif de LEDs par exemple.

Évaluation & suivi

Les modalités d'évaluation seront disponibles prochainement.

Le suivi sera assuré :

• par moi-même lors des séances en présenciel,
• à distance via Google+,
• la progression quotidienne du projet sera sauvegardée via des documents partagés Google Documents,