SOLO-030 · Placement de pentominos

Le rectangle récalcitrant

Paver entièrement le rectangle 5 × 10 avec les 10 pentominos donnés, sans chevauchement.

Corrigé — cette page contient la réponse.

La réponse exacte

Le pavage ci-dessous est unique pour les pièces et les indices indiqués. Une lettre identifie un pentomino entier.

Le raisonnement

1. Les silhouettes sont définies par les cases portant leur lettre. Les points ne font pas partie de la pièce. Construire les orientations possibles : quatre rotations, puis leur miroir, en supprimant les doublons.
2. Commencer par les cases portant un indice. Pour chaque orientation de la pièce concernée, vérifier qu’elle couvre tous les indices de sa lettre et aucun indice d’une autre lettre. Choisir ensuite une case encore vide présentant le moins de placements possibles.
3. Placer T sur L3C7, L4C7, L5C6, L5C7, L5C8. Vérifier que ces cinq cases forment une rotation ou un miroir de sa silhouette et ne recouvrent aucune pièce déjà posée.
4. Placer I sur L1C10, L2C10, L3C10, L4C10, L5C10. Vérifier que ces cinq cases forment une rotation ou un miroir de sa silhouette et ne recouvrent aucune pièce déjà posée.
5. Placer N sur L2C8, L3C8, L4C8, L4C9, L5C9. Vérifier que ces cinq cases forment une rotation ou un miroir de sa silhouette et ne recouvrent aucune pièce déjà posée.
6. Placer V sur L1C7, L1C8, L1C9, L2C9, L3C9. Vérifier que ces cinq cases forment une rotation ou un miroir de sa silhouette et ne recouvrent aucune pièce déjà posée.
7. Placer P sur L1C5, L1C6, L2C5, L2C6, L2C7. Vérifier que ces cinq cases forment une rotation ou un miroir de sa silhouette et ne recouvrent aucune pièce déjà posée.
8. Placer F sur L1C1, L1C2, L2C2, L2C3, L3C2. Vérifier que ces cinq cases forment une rotation ou un miroir de sa silhouette et ne recouvrent aucune pièce déjà posée.
9. Placer L sur L2C1, L3C1, L4C1, L5C1, L5C2. Vérifier que ces cinq cases forment une rotation ou un miroir de sa silhouette et ne recouvrent aucune pièce déjà posée.
10. Placer Z sur L1C3, L1C4, L2C4, L3C4, L3C5. Vérifier que ces cinq cases forment une rotation ou un miroir de sa silhouette et ne recouvrent aucune pièce déjà posée.
11. Placer W sur L3C6, L4C5, L4C6, L5C4, L5C5. Vérifier que ces cinq cases forment une rotation ou un miroir de sa silhouette et ne recouvrent aucune pièce déjà posée.
12. Placer X sur L3C3, L4C2, L4C3, L4C4, L5C3. Vérifier que ces cinq cases forment une rotation ou un miroir de sa silhouette et ne recouvrent aucune pièce déjà posée.
13. La preuve d’unicité explore 13455 sous-pavages et élimine 8821 impasses où une case libre n’accepte plus aucune pièce restante. Une seule couverture complète subsiste.
14. Pour vérifier indépendamment la réponse, compter cinq cases par lettre, comparer chaque groupe à sa silhouette à rotation/retournement près, puis vérifier les indices. Pour prouver l’unicité sur papier, reprendre l’arbre de placements par la case la plus contrainte et barrer chaque branche qui laisse une case isolée ou impossible à couvrir. Le script de validation effectue cette exploration exhaustive ; les groupes affichés donnent le chemin gagnant.

Fausses pistes et erreurs

• Un miroir est permis, mais pas un déplacement partiel d’une seule case.
• Deux groupes de même aire ne sont pas nécessairement de même forme.
• Une cavité de cinq cases peut rester impossible à remplir si sa forme ne correspond à aucune pièce restante.

{
  "nodes": 13455,
  "dead_ends": 8821,
  "max_depth": 10
}

← Revenir à l’énoncé SOLO-030