Introdução
O enigma da zebra é um famoso problema de lógica no qual existem cinco casas, cada uma pintada com uma cor diferente.
As casas têm habitantes diferentes, que têm nacionalidades diferentes, têm animais de estimação diferentes, bebem bebidas diferentes e têm passatempos diferentes.
Para te ajudar a resolver o enigma, são-te apresentadas 15 afirmações que descrevem a solução.
No entanto, só combinando a informação de todas as afirmações é que conseguirás encontrar a solução do enigma.
O enigma da zebra é um problema de satisfação de restrições (CSP).
Neste tipo de problema, tens um conjunto de valores possíveis e um conjunto de restrições que limitam quais desses valores são válidos.
Outro CSP bem conhecido é o Sudoku.
Instruções
A tua tarefa é resolver o Enigma da Zebra para descobrires as respostas a estas duas perguntas:
- Qual dos residentes bebe água?
- Quem é dono da zebra?
Enigma
As 15 afirmações seguintes são todas verdadeiras:
- Há cinco casas.
- O inglês vive na casa vermelha.
- O espanhol é dono do cão.
- A pessoa que vive na casa verde bebe café.
- O ucraniano bebe chá.
- A casa verde fica imediatamente à direita da casa de marfim.
- O dono do caracol gosta de ir dançar.
- A pessoa que vive na casa amarela é pintor.
- A pessoa que vive na casa do meio bebe leite.
- O norueguês vive na primeira casa.
- Quem gosta de ler vive na casa ao lado da pessoa que tem a raposa.
- A casa do pintor fica ao lado da casa que tem o cavalo.
- Quem joga futebol bebe sumo de laranja.
- O japonês joga xadrez.
- O norueguês vive ao lado da casa azul.
Para além disso, cada uma das cinco casas está pintada de uma cor diferente, e os seus habitantes têm nacionalidades diferentes, têm animais de estimação diferentes, bebem bebidas diferentes e têm passatempos diferentes.
Há 24 mil milhões (5!⁵ = 24 883 200 000) de soluções possíveis, por isso tenta eliminar o maior número possível de soluções.
Implementação
Define uma única função, SolvePuzzle, que devolve uma solução
com duas strings, cujos valores são as respostas às perguntas
do enigma da zebra: «Quem bebe água?» e «Quem é o dono da zebra?».
Cada resposta será uma das nacionalidades dos moradores:
Englishman, Spaniard, Ukrainian, Norwegian ou Japanese.
Obviamente, podias escrever uma função de uma só linha
se espreitasses o programa de testes para ver a solução esperada.
Mas o objetivo é desenvolveres um algoritmo que use
os factos e as restrições fornecidos pelo enigma
e determine as duas respostas corretas.
