Qual é o meu problema:
Há um quebra-cabeça de Raymond Smullyan que funciona mais ou menos assim: você está em uma sala com muitas portas. Atrás de algumas daquelas portas, há damas; atrás dos outros, existem tigres. Seu objetivo é escolher uma das portas certas (aquelas com as mulheres). Em toda porta, há uma placa que diz algo como: Há uma senhora atrás desta porta ou Há um leão atrás da porta II e VI e assim por diante. Agora, você também tem algumas informações adicionais, como Apenas um dos sinais diz a verdade ou O sinal na porta é verdadeiro apenas se houver uma mulher atrás dessa porta e assim por diante. Por exemplo, o primeiro quebra-cabeça é assim:
Existem duas portas com um sinal cada. Um dos sinais é verdadeiro, o outro é falso:
--------------------- --------------------- | DOOR I | | DOOR II | | There's a lady in | | In one of those | | this room and a | | rooms, there's a | | a tiger in the | | lady, in the other | | other one | | one there's a tiger | --------------------- ---------------------Atrás de qual porta está uma dama?
Agora, chegando ao tópico desta pergunta: estou procurando maneiras possíveis de gerar automaticamente esses quebra-cabeças. O objetivo (distante) é criar um algoritmo que exija, como parâmetros, o número de portas (e talvez a dificuldade do quebra-cabeça resultante) e crie textos correspondentes para as portas.
O que eu tentei até agora:
Não muito, porque eu realmente não sei por onde começar. É fácil criar um padrão para o texto nos sinais e também é fácil atribuir aleatoriamente declarações verdadeiras e falsas a esses sinais, correspondendo à regra verdadeira-falsa que você usa (por exemplo, apenas um sinal diz a verdade ). Mas essa é a parte em que fica complicado: como criar um quebra-cabeça solucionável e com uma solução única ? Minha primeira idéia foi criar um quebra-cabeça aleatório e usar o backtracking para procurar soluções. Mas, dessa forma, pode demorar muito tempo até que o algoritmo finalmente encontre um conjunto de sinais de trabalho. Além disso, dessa forma, você não pode determinar facilmente o quão difícil é um determinado quebra-cabeça.
Então, resumindo: você tem alguma idéia, algum link útil etc.? Qualquer ajuda é apreciada, não espero que ninguém poste uma solução perfeita e completa para o meu problema.
(Nota: originalmente fiz a seguinte pergunta no stackoverflow, mas me disseram lá que seria mais provável obter uma resposta aqui!)
Respostas:
A geração de texto é uma questão separada, mas para um pequeno número de portas talvez você possa usar um mapa de Karnaugh. Escolha uma célula aleatória que seja verdadeira, todas as outras serão falsas e use um algoritmo apropriado para encontrar a expressão booleana mais eficiente que corresponda a esse mapa, por exemplo
http://www.codeproject.com/Articles/37031/Karnaugh-Map-Minimizer-3-Variables
fonte