Forzado
Forzado
Técnicas asociadas
¿Es adivinar? La controversia de Cadenas forzadas
Cadenas forzadas no son adivinanzas cuando se usan como técnica de prueba. Examinas temporalmente cada rama desde un punto de partida elegido, propagas cada rama lógicamente y conservas solo las conclusiones que todas las ramas respaldan o las conclusiones forzadas por una contradicción.
La diferencia clave con adivinar es el compromiso. Una adivinanza elige una rama y continúa como si fuera verdadera. Una cadena de forzado compara todas las ramas relevantes desde el punto de partida y actúa solo cuando la comparación demuestra algo.
Cadenas forzadas son menos elegantes que las técnicas basadas en patrones, pero sus conclusiones son demostrablemente correctas cuando se ha comprobado con precisión cada rama.
Cadena de forzado Celda
Comienza desde una celda bivaluada {A, B}. Propaga las implicaciones de cada rama. Compara los resultados.
Contradicción: una rama no es válida, así que la celda debe ser el otro candidato.
Convergencia en colocación: ambas ramas fuerzan el mismo dígito en la misma celda distante.
Convergencia en eliminación: ambas ramas eliminan el mismo candidato de la misma celda.
Cadena de forzado por región (cadena de forzado por dígito)
Comienza desde las 2-3 posiciones de un dígito en una casa. Explora cada posición como una rama. Los mismos tres tipos de deducción.
El forzado Celda es eficaz cuando las celdas bivaluadas tienen implicaciones de largo alcance. El forzado por región es eficaz cuando la posición de un dígito tiene fuertes efectos en cascada.
Red de forzado: ampliación del número de ramas
Red de forzado Celda: celdas con 3-6 candidatos. Red de forzado por región: casas con 4-6 posiciones para un dígito. Más ramas, más costoso, pero puede encontrar deducciones que Cadenas forzadas no puede.
La lógica es idéntica. Solo difiere el número de ramas.
El motor de propagación
Cada rama se propaga mediante singles desnudos, singles ocultos, candidatos bloqueados y pares desnudos, iterativamente hasta estabilizarse. Una sola suposición puede propagarse por docenas de pasos intermedios en todo el tablero.
Cuando dos ramas llegan a la misma conclusión por caminos completamente distintos, la convergencia demuestra la conclusión con certeza.
Los tres tipos de deducción
Contradicción: Una rama produce un estado inválido. Esa suposición es falsa. La más común.
Convergencia en la colocación: Todas las ramas fuerzan el mismo dígito en la misma celda. Menos común pero decisiva.
Convergencia en la eliminación: Todas las ramas eliminan el mismo candidato de la misma celda. El tipo más sutil.
Cuándo usar las técnicas de forzado
Último recurso lógico. Se aplica después de que fallan las técnicas basadas en patrones y las cadenas más limpias.
Se prueban primero los Cadenas forzadas con 2-3 ramas. Las redes de forzado con 3-6 ramas son más costosas y suelen reservarse para después. Ambas son de nivel 12 (Extremo).
Para los solucionadores informáticos, el forzado acotado es un potente motor de prueba, pero no es automáticamente completo. La completitud solo se logra si se permite que la búsqueda se expanda lo suficiente para cubrir las suposiciones necesarias, lo que se acerca al backtracking exhaustivo. En la práctica, el forzado se describe mejor como una búsqueda lógica controlada que como la garantía de que cualquier solucionador de profundidad fija pueda resolver todo rompecabezas válido.
Una nota filosófica sobre la elegancia y la completitud
Las técnicas basadas en patrones revelan relaciones estructurales y son más elegantes. Pero existen rompecabezas válidos que requieren lógica de nivel de forzado. Las técnicas de forzado son la red de seguridad que atrapa todo rompecabezas que las técnicas basadas en patrones no pueden manejar.
El enfoque más satisfactorio: probar primero todas las técnicas basadas en patrones y recurrir al forzado solo cuando el rompecabezas realmente lo exija.
Resumen
Cadenas forzadas y las redes de forzado están entre las técnicas lógicas más potentes, en el nivel 12 (Extremo). Exploran cada rama desde un punto de partida elegido, propagan las consecuencias y comparan los resultados. Las deducciones surgen por contradicción, convergencia en la colocación o convergencia en la eliminación. Son el último recurso antes del backtracking por fuerza bruta; si se expanden sin límites prácticos, se convierten en una prueba de búsqueda completa, pero el forzado acotado al estilo humano sigue siendo una técnica avanzada y específica.
Técnicas asociadas