Forzado

Forzado

Maestro

Técnicas asociadas

¿Es adivinación? La controversia de Cadenas forzadas

Cadenas forzadas no son adivinanzas cuando se utilizan como técnica de prueba. Temporalmente examinas cada rama a partir de un punto de partida elegido, propagas cada rama lógicamente y solo conservas las conclusiones que todas las ramas respaldan o las conclusiones forzadas por una contradicción.

La diferencia clave con respecto a adivinar es el compromiso. Una adivinanza elige una rama y continúa como si fuera verdadera. Una cadena forzada compara todas las ramas relevantes desde el punto de partida y actúa solo cuando la comparación prueba algo.

Cadenas forzadas son menos elegantes que las técnicas basadas en patrones, pero sus conclusiones son provablemente correctas cuando se ha comprobado con precisión cada rama.

Celda Cadena de fuerza

Comience desde un Celda bivaluado {A, B}. Propague las implicaciones para cada rama. Compare los resultados.

Contradicción: una rama es inválida, por lo tanto, el Celda debe ser el otro candidato.

Convergencia en colocación: ambas ramas obligan al mismo dígito en el mismo Celda distante.

Convergencia en eliminación: ambas ramas eliminan el mismo candidato del mismo Celda.

Cadena de forzamiento de región (Cadena de forzamiento de dígito)

Comience desde las 2-3 posiciones de un dígito en una casa. Explore cada posición como una rama. Mismas tres tipos de deducción.

Celda forzado es eficaz cuando las celdas bivaluadas tienen implicaciones de amplio alcance. El forzado de región es eficaz cuando la posición de un dígito tiene efectos en cadena fuertes.

Red de fuerza: Ampliando el recuento de ramas

Celda Red de forzamiento: celdas con 3-6 candidatos. Red de forzamiento de región: casillas con 4-6 posiciones para un dígito. Más ramas, más costoso, pero puede encontrar deducciones 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 a través de singles desnudos, singles ocultos, Candidatos bloqueados, y pares desnudos, iterativamente hasta alcanzar un estado estable. Una única suposición puede propagarse a través de docenas de pasos intermedios en todo el tablero.

Cuando dos ramas llegan a la misma conclusión mediante caminos completamente diferentes, la convergencia demuestra con certeza la conclusión.

Los tres tipos de deducción

Contradicción: Una rama produce un estado inválido. Esa suposición es falsa. Más común.

Convergencia en colocación: Todas las ramas obligan al mismo dígito en la misma Celda. Menos común pero decisiva.

Convergencia en eliminación: Todas las ramas eliminan el mismo candidato de la misma Celda. Tipo más sutil.

Cuándo usar las técnicas de forzamiento

Último recurso lógico. Se aplica después de que fallen las técnicas basadas en patrones y las cadenas más limpias.

Se intentan primero los Cadenas forzadas con 2-3 ramas. Las redes forzadas con 3-6 ramas son más costosas y generalmente se reservan para más adelante. Ambas son de Nivel 12 (Extremo).

Para los solucionadores por computadora, el forzado acotado es un motor de prueba potente, pero no es automáticamente completo. La completitud solo se alcanza si la búsqueda se permite expandirse lo suficiente como para cubrir los supuestos necesarios, lo que se aproxima al retroceso exhaustivo. En la práctica, el forzado se describe mejor como una búsqueda lógica controlada, más que una garantía de que cualquier solucionador de profundidad fija pueda resolver cada 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 puzles válidos que requieren lógica de nivel de forzamiento. Las técnicas de forzamiento son la red de seguridad que atrapa cada puzle que las técnicas basadas en patrones no pueden manejar.

La aproximación más satisfactoria: intentar primero todas las técnicas basadas en patrones, y recurrir al forzamiento solo cuando el puzle lo exija verdaderamente.

Resumen

Cadenas forzadas y las redes de fuerza son algunas de las técnicas lógicas más potentes, al nivel 12 (Extremo). Exploran cada rama desde un punto de partida elegido, propagan las consecuencias y comparan los resultados. Las deducciones surgen mediante contradicción, convergencia en una colocación o convergencia en una eliminación. Son el último recurso antes del retroceso forzado; si se expanden sin límites prácticos, se convierten en una prueba de búsqueda completa, pero la red de fuerza acotada de estilo humano sigue siendo una técnica avanzada dirigida.

Técnicas asociadas