[off] Teste de Einstein

Resolver usando um monte de papel ou uma planilha, com uma certa paciência se resolve.
Mas como esse é um forum de Java, o desafio vai ser criar um programa brute force (em Java, claro) para resolver automaticamente

Tipo…
Uma array para cada categoria (cor/nacionalidade/bebida/cigarro/animal)
Cada posição das arrays é uma casa.
E as regras convertidas de forma que “O homem que fuma Blends é vizinho do que bebe Água” ficaria a posição de Blends é +/- 1 a posição de água.
Claro que o programinha também deve ser parametrizável e de preferência ter uma interface gráfica para inserir os valores possíveis e as regras

Na verdade, esse pode ser traduzido como um problema classico da computacao, conhecido como problema de satisfazibildiade (errei a palavra)? Em Ingles, problemas SAT.

Isto eh, dado um teorema (americano bebe nao sei que e mora nao sei onde, etc…), que eh um conjunto de clausulas, voce acha uma valoracao para suas variaveis, de tal modo que todas suas clausulas sejam valoradas positivamente (true)

O mais legal ainda. Prova-se que, qualquer problema NP (humm, digamos, exponenciais em relacao ao tamanho da entrada) pode ser trocado por um problema SAT.

O algritmo mais classico para resolver isso (um dos SAT solvers) chama-se DPL, que como a Bani falou, eh um brute force. Mas voce pode colocar heuristicas nele, de tal maneira que ele faca a brute force “inteligentemente”, passando primeiro pelos estados que tem mais probabilidade de matar o meu problema.

Implemente isso em java a uns dois meses Vou ver se adapto.

Esse problema pode ser resolvido usando grafos de forma razoavelmente facil.

Caso alguem queira resolver ele na mão, ai vão algumas dicas, eu já tinha resolvido esse problema a mais de um ano:

-Não saia preenchendo logo de cara o resultado.

-Primeiro monte 5 tabelas relacionando cada um dos parametros (nacionalidade, bebida, animal, cor da casa e cigarro) com as várias possibilidades dos demais e então vá aplicando as regras de forma a eliminar combinações, ex: ‘o dinamarquês bebe chá’, logo ele não pode beber outra coisa e os outros não podem beber chá.

Aplique todas regras nas 5 tábelas, isso já vai elucidar boa parte do problema. Passe então a compará-las procurando eliminar mais combinações, ex: na tabela de bebidas, coluna ‘chá’ não consta o alemão, logo apague chá da coluna ‘alemão’ da tabela de pessoas.

O ultimo passo, que exige 1 pouco de sorte é montar o resultado. Com essas 5 tabelas à mão é facil fazer isso, basta tomar 1 pouco de cuidado.

“louds”:

Esse problema pode ser resolvido usando grafos de forma razoavelmente facil.

Esse problema eh NP completo. Pode ser resolvido de maneira razoavelmente dificil. Claro que pode levar segundos, mas computacionalmente foi dificil. Qualquer problema NP, seja em grafos ou onde for, eh redutivel em SAT.

Vcs viram o método “Engenharia de Software”. Eu sugiro um outro método:

• Numere as casas.
• Enquanto vc nao tiver resolvido o problema,
• • leia uma cláusula. Se ela te dá uma certeza, preencha no resultado essa certeza. (Por exemplo, se vc descobriu que o “alemao” está na casa 3, e vc lê “alemao bebe cha”, entao vc tem certeza que “cha” vai na casa 3). Nesse caso, jogue essa cláusula fora.
• • se ela nao te dá uma certeza, marque a tupla numa lista separada. (Por exemplo, (“alemao”, “cha”). Isso vai agilizar as próximas passagens.
• Fim.
• se vc empacar, use a lei máxima de Sherlock Holmes: “quando vc exclui de um caso tudo o que é impossível, sobra apenas a verdade”.

Aquelao!!

estive procurando alguns assuntos sobre o teste de einstein. Achei esse artigo mas tentei abrir a página e fala que não existe. Se você tiver esse site ainda, poderia me enviar?

O post dele é de 2003… acredito que este site não deva existir mais…

Mas, eu tenho este teste no meu notebook em casa… se quiser, me manda uma MP que te envio ele à noite…

Procure por teste de einstein no google, deve ter umas mil páginas com ele.

Se duvidar até tem na Wikipedia.

Edit: Ah, tem mesmo: http://en.wikipedia.org/wiki/Zebra_Puzzle