algorithm - who - Generar de forma algorítmica un puzzle Zebra/Einstein.
who owns the fish solution la luna hotel (5)
Aquí hay un algoritmo simple que hace uso de su solucionador:
Generar una instancia de rompecabezas al azar.
Construye un conjunto C de todas las pistas posibles que pertenecen a esta instancia de rompecabezas. (Hay un número finito y, de hecho, bastante pequeño de pistas posibles: por ejemplo, si hay 5 casas, hay 5 pistas posibles de la forma "Persona A vive en la casa B", 8 pistas posibles de la forma "Persona A vive al lado de la casa B ", y así sucesivamente.)
Elija una permutación aleatoria c 1 , c 2 , ..., c n de las pistas en C.
Establecer i = 1.
Si i > n , hemos terminado. El conjunto C de pistas es mínimo.
Sea D = C - { c i }. Ejecute su solucionador en el conjunto D de pistas y cuente el número de soluciones posibles.
Si hay exactamente una solución, establezca C = D.
Establezca i = i + 1 y vuelva al paso 5.
(Puede acelerar esto eliminando pistas en lotes en lugar de uno a la vez, pero hace que el algoritmo sea más complicado de describir).
En primer lugar, no necesariamente estoy buscando un algoritmo completo, solo puedo copiar y pegar, y luego llamarlo un día. ¡Cualquier solución de "enfoque general" estaría bien para mí!
Todo este post fue impulsado por un día lento en el trabajo, y tropezamos con este sitio y no pudimos averiguar cómo implementaron su generador.
El problema
Para aquellos de ustedes que no lo saben, el "Zebra Puzzle" o "Einstein''s Puzzle" es un famoso rompecabezas de lógica con el que probablemente se haya topado antes.
El artículo completo de la wiki está here , pero publicaré los bits relevantes.
There are five houses.
The Englishman lives in the red house.
The Spaniard owns the dog.
Coffee is drunk in the green house.
The Ukrainian drinks tea.
The green house is immediately to the right of the ivory house.
The Old Gold smoker owns snails.
Kools are smoked in the yellow house.
Milk is drunk in the middle house.
The Norwegian lives in the first house.
The man who smokes Chesterfields lives in the house next to the man with the fox.
Kools are smoked in the house next to the house where the horse is kept.
The Lucky Strike smoker drinks orange juice.
The Japanese smokes Parliaments.
The Norwegian lives next to the blue house.
Now, who drinks water? Who owns the zebra? In the interest of clarity, it must be
added that each of the five houses is painted a different color, and their inhabitants
are of different national extractions, own different pets, drink different beverages
and smoke different brands of American cigarets [sic]. One other thing: in statement
6, right means your right.
Todo esto está muy bien. He encontrado varias formas concisas y claras en línea para resolver este problema, especialmente utilizando la programación de restricciones. Sin embargo, lo que me interesa es hacer más de estos tipos de rompecabezas.
Haciendo más
Obviamente, una representación matricial es una forma lógica de pensar en esto. Con cada columna que contiene una persona, una casa, lo que beben, qué tipo de automóvil manejan, etc.
Mi idea inicial fue comenzar con una cuadrícula generada al azar que esté completa (es decir, resuelta) y luego (de alguna manera) crear sugerencias de la versión resuelta que la identifiquen de forma única. Cada vez que se puede determinar algo, se elimina de la cuadrícula.
Al copiar el sitio que enumeré al principio, los siguientes "consejos" que pueden usarse para resolver la cuadrícula pueden ser del siguiente tipo:
La persona / animal / planta vive / crece en una casa determinada.
La persona / animal / planta no vive / crece en una casa determinada.
La persona / animal / planta vive en la misma casa que la otra persona / animal / planta.
La persona / animal / planta es un vecino directo de la otra persona / animal / planta.
La persona / animal / planta es el vecino izquierdo o derecho de otra persona / animal / planta.
Hay una casa entre la persona / animal / planta y la otra persona / animal / planta.
Hay una casa entre la persona / animal / plan y la otra persona / animal / planta a la izquierda o la derecha.
Hay dos casas entre la persona / animal / planta y la otra persona / animal / planta.
Hay dos casas entre la persona / animal / plan y la otra persona / animal / planta a la izquierda o la derecha.
La persona / animal / planta vive a la izquierda o derecha de la otra persona / animal / planta.
Puedes ver cómo estos pueden ser generalizados, extendidos, etc .;
La dificultad es que, al utilizar mi enfoque (comenzando con una cuadrícula completa y generando estas sugerencias), no estoy seguro de cómo asegurarme de que el conjunto de sugerencias que creo generará absolutamente la cuadrícula de destino.
Por ejemplo, si dices "El inglés no es dueño de un pino", no puedes combinar dos cosas de manera decisiva en un momento dado del rompecabezas. Sin embargo, si solo quedaran dos árboles por resolver, esto podría de hecho ser una pieza decisiva de evidencia.
¿Estoy pensando en esto de forma totalmente equivocada? ¿Sería un mejor enfoque crear una cuadrícula con algunos elementos conocidos aleatorizados y predefinidos (es decir, la casa roja está en el centro) y luego construir la cuadrícula utilizando estas sugerencias como reglas para la construcción?
¡Cualquier consejo, artículos para leer, técnicas de programación para aprender, etc. serían muy apreciados!
Curiosamente, el rompecabezas "Einstein" (las citas previstas, todo "inteligente" tiende a asignarse a Einstein, tal vez a tener más glamour), está relacionado con el algoritmo de generación de Sudoku (por una traducción correcta de los términos) y también con Rubik Cube (3x3x3) Algoritmo de resolución
En el caso de Sudoku, las pistas corresponden a números ya asignados en la cuadrícula y la información que falta para vaciar las ranuras.
En el caso de Rubik Cube (que me parece más interesante), las pistas corresponden a las simetrías del cubo (por ejemplo, el color verde está al lado del color rojo, algo así) y los datos que faltan se encuentran al alinear (resolver) el cubo
Este es un esquema aproximado, gracias
No estoy completamente seguro de esta solución, pero así es como lo abordaría:
Partiendo de una solución aleatoria (es decir, la casa verde contiene esmalte que fuma LM, la casa roja contiene irlandés que fuma clavos de olor, etc.). Puedes ver esa solución como un gráfico de relaciones entre afirmaciones. donde cada elemento (polaco, casa roja, etc.) está conectado a todos los demás, ya sea por un borde "sí" o por un "no borde" (en nuestro caso, el esmalte está conectado a la casa verde con un borde "sí" y al dientes con un "sin borde" (entre muchos otros bordes, este gráfico inicial es un gráfico direccional completo)).
Ahora, si quita los bordes al azar, hasta que se quede con un gráfico mínimo conectado, debería tener un gráfico que represente un rompecabezas que se pueda resolver. traduce cada borde sí a "el foo es / hace la barra" y cada no borde a "el foo no es / no la barra".
intuitivamente esto me suena bien. pero nuevamente, esta no es de ninguna manera una forma formal o reconocida de hacer esto, y puede ser completamente errónea.
Otra idea: una vez que haya generado su cuadrícula completa, tome una foto de ella en su teléfono (o duplique el diseño) antes de eliminar elementos a medida que brinda pistas. Es posible que termine la mitad de la tarea y se olvide de cómo debe verse el diseño original / final y puede evitar desinformar a sus sujetos / examinados.
Pensando en hacer uno para la Pascua, patrón similar, 5 personas, 5 tipos de chocolate, 5 edades, 5 sombreros de Pascua diferentes, 5 bebidas favoritas diferentes, helados, etc.
También puede hacerlo al revés (lo que también le dará un solucionador):
- Generar S , una lista de todas las soluciones posibles (es decir, tablas).
- Genera un hecho aleatorio f (por ejemplo: el noruego tiene un gato).
- Set T = S
- Filtra de T todas las soluciones que violan f .
- Si | T | = 0 entonces goto 2 (el hecho contradice uno anterior)
- Si | T | <| S | luego establezca S = T y F.append (f) (el hecho no está incorporado a los hechos anteriores)
- IF | S | > 1 luego goto 2
Una vez hecho esto, F será la lista de hechos que llevan a la única tabla que queda en S.
Es cierto que esta es una fuerza bruta, y probablemente no funcionará bien con una tabla que es 5X5 o más.