Introdução
O Zebra Puzzle é um famoso quebra-cabeça de lógica com cinco casas, cada uma pintada de uma cor diferente.
As casas têm moradores diferentes, que têm nacionalidades diferentes, criam animais de estimação diferentes, bebem bebidas diferentes e têm hobbies diferentes.
Para ajudar você a resolver o quebra-cabeça, são dadas 15 afirmações que descrevem a solução.
No entanto, só combinando as informações de todas as afirmações você vai conseguir encontrar a solução do quebra-cabeça.
O Zebra Puzzle é um problema de satisfação de restrições (CSP).
Em um problema assim, você tem um conjunto de valores possíveis e um conjunto de restrições que limitam quais valores são válidos.
Outro CSP bem conhecido é o Sudoku.
Instruções
Sua tarefa é resolver o Enigma da Zebra para encontrar a resposta a estas duas perguntas:
- Qual dos moradores bebe água?
- Quem é o dono da zebra?
O enigma
As 15 afirmações a seguir são todas verdadeiras:
- Existem cinco casas.
- O inglês mora na casa vermelha.
- O espanhol é o dono do cachorro.
- A pessoa que mora na casa verde bebe café.
- O ucraniano bebe chá.
- A casa verde fica imediatamente à direita da casa de marfim.
- Quem tem o caracol gosta de dançar.
- Quem mora na casa amarela é pintor.
- A pessoa que mora na casa do meio bebe leite.
- O norueguês mora na primeira casa.
- Quem gosta de ler mora na casa ao lado da pessoa que tem a raposa.
- A casa do pintor fica ao lado da casa onde está o cavalo.
- Quem joga futebol bebe suco de laranja.
- A pessoa japonesa joga xadrez.
- O norueguês mora ao lado da casa azul.
Além disso, cada uma das cinco casas é pintada de uma cor diferente, e seus moradores têm nacionalidades diferentes, têm animais de estimação diferentes, bebem bebidas diferentes e praticam hobbies diferentes.
Existem 24 bilhões (5!⁵ = 24.883.200.000) de soluções possíveis, então tente descartar o maior número possível de soluções.
Implementação
Defina uma única função, SolvePuzzle, que retorna uma solução contendo duas strings, cujos valores são as respostas às perguntas do quebra-cabeça da zebra: "Quem bebe água?" e "Quem tem a zebra?". Cada resposta será uma das nacionalidades dos moradores: Englishman, Spaniard, Ukrainian, Norwegian ou Japanese.
É claro que você poderia simplesmente escrever uma função de uma linha só se desse uma espiada no programa de testes para ver a solução esperada. Mas o objetivo é desenvolver um algoritmo que use os fatos e as restrições fornecidos pelo quebra-cabeça e determine as duas respostas corretas.
