www.migniot.com

Pentominos

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.

Détermination des Naminos

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

Résultat

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