Tabuleiro mutilado de xadrez

Nesse problema, temos um tabuleiro de jogo de xadrez onde dois quadras em cantos opostos foram cortados.

O problema consiste em cobrir totalmente o tabuleiro com pedras de jogo de dominó, considerando que uma pedra cobre exatamente duas casas contíguas do tabuleiro. A abstração que será feita nesse caso é a de não considerar a cor das casas. Sendo o estado inicial o tabuleiro vazio, tem 108 estados possíveis depois de ter colocado a primeira pedra de dominó. Pode-se verificar que por um tabuleiro de tamanho n o número de possibilidades para colocar a primeira pedra é 2n(n-1)-4. Para colocar a segunda pedra, o número de possibilidade varia entre 101 e 104, dependendo do número de pares de casas contíguas que a pedra impede de usar.