Le problème de l’échiquier mutilé, bien que comportant des éléments très anciens comme un plateau d’échec et des dominos, est relativement récent. Publié pour la première fois en 1946 par Max Black dans son livre Critical Thinking, cette énigme est connue pour être très difficile à résoudre pour un programme informatique, mais parfaitement accessible pour un humain.

Énoncé

Vous avez devant vous un échiquier auquel nous avons retiré 2 cases, deux coins opposés. Vous avez à votre disposition 31 dominos de dimension 1 × 2.

Est-il possible de couvrir les 62 cases de l’échiquier avec les dominos ? Si oui, comment ? Si non, pourquoi ?