Vous souvenez-vous de tetris ? Les pièces de tétris sont constituées d'un certain nombre de carrés adjacents. Ces pièces sont des Naminos. Lorsqu'une pièce est composée de 5 carrés adjacents, c'est un pentomino, ou plus exactement un pentamino.

La détermination des Naminos, par exemple avec N=5, est un algorithme itératif. En débutant avec la pièce de 1 carré :

• Pour chaque pièce de n carrés
• Calculer tous les espaces libres à coté d'une case remplie
• Forger ainsi une nouvelle pièce de n+1 carrés, copie de l'ancienne avec l'espace libre rempli
• Puis éliminer les doublons à la fin des pièces de n carrés

L'élimination des doublons est un algorithme qui peut être résolu par la force brute :

• Préparer la liste 'unique', vide au départ
• Pour chaque pièce de la liste obtenue par l'algorithme ci-dessus
• Calculer ses 8 formes dérivées : 4 rotations et leurs symétriques
• Si aucune de ces formes dérivées n'apparait dans la liste des formes déjà vues
  • Ajouter la pièce à la liste 'unique'
• Ajouter les formes dérivées à la liste des formes déjà vues

Le source : Naminos2D.py

Le programme fourni peut être exécuté pour n'importe quel nombre de carrés. Toutefois le résultat pour n=5 est de 12 pièces. Une fois les pièces déterminées on peut tenter de les placer sur un damier 10x6 par un processus récursif classique.

Le source : Pentominos.py

La totalité des solutions pour n=5 ICI