Teste do peixe

Resolvendo Desafios mais Complicados com Prolog
Posted on July 16, 2011
No post anterior foi mostrado como resolver desafios de lógica no estilo do Teste de Einstein em Prolog. Entretanto, o processo de geração no esquema de geração e teste era bastante ineficiente para problemas mais complexos. O problema é que muitas possibilidades são geradas e descartadas quando é feita a verificação de diferença. Por que não gerar as possibilidades já todas diferentes, eliminando esse teste extra?

Em Prolog o predicado select(X, L, R) seleciona o elemento X na lista L, e retira X de L formando o resto R. Ou seja, R tem todos os elementos de L, menos o elemento selecionado X. Isso pode ser usado para, dada a lista de possibilidades para cada atributo (por exemplo, cores de casa), retirar uma possibilidade da lista para gerar uma casa, depois usar o resto da lista para gerar as cores para as outras casas. Assim, duas casas nunca serão geradas com a mesma cor.

Como exemplo, vamos usar o próprio teste de Einstein, porque ele tem mais possibilidades e não é possível de resolver eficientemente com o esquema do post anterior. O problema tem cinco casas, cada uma com cinco atributos: a cor da casa, a nacionalidade do morador, a bebida preferida do morador, o cigarro preferido e o animal de estimação. As dicas são:

O Norueguês vive na primeira casa.
O Inglês vive na casa Vermelha.
O Sueco tem Cachorros como animais de estimação.
O Dinamarquês bebe Chá.
A casa Verde fica do lado esquerdo da casa Branca.
O homem que vive na casa Verde bebe Café.
O homem que fuma Pall Mall cria Pássaros.
O homem que vive na casa Amarela fuma Dunhill.
O homem que vive na casa do meio bebe Leite.
O homem que fuma Blends vive ao lado do que tem Gatos.
O homem que cria Cavalos vive ao lado do que fuma Dunhill.
O homem que fuma BlueMaster bebe Cerveja.
O Alemão fuma Prince.
O Norueguês vive ao lado da casa Azul.
O homem que fuma Blends é vizinho do que bebe Água.
Das dicas podemos