algorithm - Cómo resolver este rompecabezas lógicamente sin prueba y error
graph logic (2)
"Lógicamente" es un término muy amplio. Como se menciona en los comentarios de Orbling, retroceder puede considerarse lógico. También se puede entender que "lógicamente" significa cómo resolverlo traduciéndolo a una fórmula lógica. De los comentarios que reúno, intentas implementar un solucionador, similar a quizás un solucionador de Sudoku común.
Una forma simple de implementar un solucionador, similar a uno para Sudokus, es encontrar ciertos patrones. Para los acertijos generados por el programa al que se refiere, puedo decir con razonable confianza que esto debería ser suficiente para resolverlos sin adivinar ni retroceder.
Algunos ejemplos de patrones obvios son <11> y >33< . Especialmente 2 tiene algunas buenas propiedades "transitivas". Por ejemplo: <12...23 -> <12...23< (con 2 ... 2 una cantidad arbitraria de 2s). Pruebe su solución en varios ejemplos y cuando se quede atascado, estoy seguro de que ha encontrado un ejemplo que puede enseñarle otro patrón.
Encontré el sesgo de los rompecabezas en Ubuntu. Quiero resolver el rompecabezas lógicamente y no por prueba y error, etc.
Las reglas son simples:
- Tenemos que llenar todas las casillas con inclinación derecha o izquierda.
- La cantidad de inclinados que tocan un número debe ser igual a ese número.
- No se permiten bucles en el tablero. es decir, los sesgos no deben formar bucles.
Rompecabezas:
Respuesta resuelta automáticamente:
¿Dónde empiezo?
En lugar de inclinación izquierda y derecha, usaré barra inclinada (/) y barra invertida (/).
Tomemos un cuadrado con las esquinas (x1) (11), donde x es todo menos 1. Hay uno en la esquina superior izquierda. Supongamos que la inclinación en ese cuadrado es barra inclinada, que conecta dos 1''s. Esos 1 están "agotados" y todos los cuadrados que los tocan deben tener líneas que no toquen los números. Pero eso lleva a una situación imposible porque tendríamos un corte a la izquierda y debajo de nuestro cuadrado, lo que significa que el 1 restante toca dos inclinaciones. La conclusión: si tienes un cuadrado con tres 1''s, entonces la línea en ese cuadrado debe tocar la esquina que no es 1 . Esta regla puede no aplicarse en los bordes y esquinas, pero si tiene un 1 en la esquina debe dibujar la línea tocando esa esquina.
Los números 1 y 3 son simétricos y usando una lógica similar obtenemos otra regla: si tienes un cuadrado con tres 3, entonces la línea en ese cuadrado debe tocar dos de esos tres 3 .
Hay reglas más generales, pero no se aplican en las esquinas. Debe haber cuadrados alrededor del cuadrado en cuestión. Tomemos un cuadrado de dos oponentes (x1) (1y), donde xey son cualquier cosa, incluido un no-number. Hay uno de esos dos cuadrados desde la esquina inferior izquierda. Supongamos que la inclinación en ese cuadrado es barra inclinada, que conecta dos 1''s. Esos 1 están "agotados" y todos los cuadrados que los tocan deben tener líneas que no toquen los números. Pero eso lleva a un bucle alrededor de los 1''s. La conclusión: si tienes un cuadrado con dos 1 oponentes, entonces la línea en ese cuadrado no debe tocar esos dos 1''s . Esta regla puede no aplicarse en los bordes de la placa.
Los números 1 y 3 son simétricos, pero la regla anterior emplea la regla de "no bucles", y no hay regla simétrica de "no bucles de líneas laterales", y por lo tanto no hay regla que tenga dos 3 opuestos.
Ahora que sabes qué línea toca el 1, puedes concluir que ninguna otra línea puede tocarlo. Podemos generalizar este razonamiento para seguir las siguientes reglas de llenado: si un número x toca x líneas, todos los demás cuadrados vecinos tienen líneas que no tocan el número . Y simétricamente: si un número x es una esquina de (4-x) cuadrados con líneas que no tocan el número, entonces todos los demás cuadrados vecinos deben tener líneas que toquen el número .
Buscando en Google el término " Gokigen Naname " encontré más reglas. Uno es aproximadamente dos 1 adyacentes (11), pero Mweerden ya lo cubrió.
Estas reglas no son suficientes para resolver el tablero. Hay otras reglas probablemente. Pero eventualmente el algoritmo puede tener que adivinar.