Cual es mi problema:
Hay un rompecabezas de Raymond Smullyan que funciona de la siguiente manera: estás en una habitación con muchas puertas. Detrás de algunas de esas puertas, hay damas; detrás de los demás, hay tigres. Su objetivo es elegir una de las puertas correctas (las que tienen las damas). En cada puerta, hay un letrero que dice algo así como: Hay una dama detrás de esta puerta o Hay un león detrás de las puertas II y VI, etc. Ahora, también tiene información adicional, como Solo uno de los letreros dice la verdad o El letrero en una puerta es verdadero solo si hay una dama detrás de esa puerta, etc. Por ejemplo, el primer rompecabezas es así:
Hay dos puertas con un letrero cada una. Uno de los signos es verdadero, el otro es 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 | --------------------- ---------------------¿Detrás de qué puerta hay una dama?
Ahora, llegando al tema de esta pregunta: estoy buscando posibles formas de autogenerar tales rompecabezas. El objetivo (lejano) es construir un algoritmo que requiera, como parámetros, el número de puertas (y tal vez la dificultad del rompecabezas resultante) y cree los textos correspondientes para las puertas.
Lo que he probado hasta ahora:
No mucho, ya que no sé por dónde empezar. Es fácil crear un patrón para el texto en los signos y también es fácil asignar aleatoriamente declaraciones verdaderas y falsas a esos signos, correspondientes a la regla verdadero-falso que usa (por ejemplo, solo un signo dice la verdad ). Pero esa es la parte donde se pone difícil: ¿cómo crear un rompecabezas que sea solucionable y tenga una solución única ? Mi primera idea fue crear un rompecabezas aleatorio y usar el retroceso para buscar soluciones. Pero de esa manera, podría pasar mucho tiempo hasta que el algoritmo finalmente haya encontrado un conjunto de signos que funcione. Además, de esa manera no puedes determinar fácilmente qué tan difícil es un rompecabezas dado.
Entonces, resumiendo: ¿Tienes alguna idea, algún enlace útil, etc.? Cualquier ayuda es apreciada, no espero que nadie publique una solución perfecta y completa para mi problema.
(Nota: ¡Originalmente hice la siguiente pregunta sobre stackoverflow pero me dijeron que sería más probable que obtuviera una respuesta aquí!)
Respuestas:
La generación de texto es un tema aparte, pero para una pequeña cantidad de puertas quizás podría usar un mapa de Karnaugh. Elija una celda aleatoria que sea verdadera, todas las demás serán falsas, luego use un algoritmo apropiado para encontrar la expresión booleana más eficiente que coincida con ese mapa, por ejemplo
http://www.codeproject.com/Articles/37031/Karnaugh-Map-Minimizer-3-Variables
fuente