Doble Cadena Forzada.

A partir de este domingo, entraremos a revisar las técnicas más avanzadas, que permiten resolver los sudokus más extremos y endemoniados. Comenzaremos con las Cadenas Forzadas, continuaremos con los Ciclos X, Nice Loops, para terminar con las Cadenas de Inferencias Alternas. Posteriormente nos queda un gran capítulo de técnicas basadas en la cualidad de que un sudoku debe tener siempre una única solución. A estas técnicas, les denominan en inglés Uniqueness. Finalmente, revisaré algunas técnicas que al menos yo las uso poco, porque son un poco rebuscadas y porque, con las técnicas anteriores se puede resolver cualquier sudoku de todas maneras. Sin embargo es bueno conocerlas.

Una Cadena Forzada permite deducir que una casilla o bien tiene que tener un valor específico, o bien, que en ella, un candidato no puede estar. Es decir, permite asignarle un valor a una casilla, o permite descartar definitivamente un candidato de una casilla. Los dos tipos de Cadenas Forzadas más comunes son la Doble Cadena Forzada y la Triple Cadena Forzada. Hoy revisaremos la Doble Cadena Forzada y dejaremos para la próxima semana la Triple.

La Doble Cadena Forzada comienza en una casilla de dos candidatos, a partir de la cual se puede demostrar que cuando esta casilla toma cualquiera de los dos candidatos, "fuerza" a que en otra casilla del sudoku puede existir solamente un candidato (y en consecuencia esa casilla debe tomar ese valor) o bien, a que un candidato en particular no puede existir en esa otra casilla.

En el ejemplo anterior la casilla clave es la que está en la octava fila – séptima columna, que tiene como cadidatos posibles al 1 y al 9. Se puede verificar que cualquiera sea el valor que tome esta casilla ( 1 o 9) la casilla amarilla no puede tomar el valor 4. Eso significa que este candidato se puede borrar de la casilla amarilla. Sigamos primero la línea rosada: cuando la casilla clave toma el valor 1, ya no vale 9, por lo tanto la casilla de la cuarta columna – octava fila debe tomar el valor nueve; de lo contrario la octava fila se quedaría sin 9. Bueno, si esta casilla es 9 ya no es 4, entonces la casilla de la cuarta columna – quinta fila debe tomar el valor 4, de lo contrario la cuarta columna se quedaría sin 4. Es decir, que cuando la casilla clave es 1, en la quinta fila el 4 está en la celda de la cuarta columna (y no está en la celda amarilla). Veamos ahora que pasa cuando la celda clave toma el valor 9 (líneas azules). En este caso la celda que está inmediatamente más arriba debe tomar el valor 2. Si es así, la celda de la séptima columna – primera fila no puede tomar el valor 2 (porque o sino la séptima fila quedaría con dos 2). En consecuencia, la casilla de la primera fila – octava columna tiene que ser 2 (porque o sino la primera fila se quedaría sin 2). Esto obliga a que la celda de la octava columna – novena fila valga 5, porque o sino esa columna se quedaría sin 5. Esto obliga a que la celda de esa misma columna, ubicada en la quinta fila tome el valor 6, o sino esa columna se quedaría sin 6. Y si esa casilla es 6, entonces la casilla de la quinta fila – segunda columna tiene que ser 4. Es decir, que cuando la casilla clave toma el valor 9, en la quinta fila el 4 está en la casilla de la segunda columna (y no en la celda amarilla). Y como la celda clave puede tomar sólo estos dos valores, 1 o 9, y en ninguno de esos casos la celda amarilla toma el valor 4, entonces la celda amarilla no puede ser 4. Este candidato se puede borrar de esta casilla. Este es un ejemplo en que una cadena forzada permite eliminar un candidato de una casilla.

Quisiera que noten dos cosas importantes. La primera se aprecia muy bien siguiendo la línea rosada. Aquí ocurre lo que en inglés se llama "bilocation", es decir: en un grupo (ya sea en una fila, en una columna o una caja) un candidato está sólo en dos casillas. En este ejemplo, en la octava fila, el 9 está sólo en dos casillas: en la casilla clave y en la de la cuarta columna. Eso permite inferir que si la casilla clave es 1, entonces necesariamente la casilla de la octava fila – cuarta columna "tiene" que ser 9, o sino esa fila se queda sin 9. Lo mismo ocurre con el 4 en la cuarta columna.

La segunda nota importante es lo que en inglés llaman "bivalue", es decir cuando una casilla tiene sólo dos candidatos. Se aprecia siguiendo la línea azul: cuando la casilla clave vale 9, entonces la casilla que está inmediatamente más arriba (y que tiene sólo dos candidatos: el 2 y el 9) ya no puede tomar el valor nueve. La única posibilidad que le queda a esta casilla es tomar el otro valor: 2.

Más adelante hablaremos más en detalle de inferencias fuertes e inferencias débiles, en las cuales se ocupan estos dos conceptos "bivalue" y "bilocation", que resultan fundamentales. Estos dos conceptos son los pilares de cualquier cadena.

El ejemplo que sigue es muy interesante porque permite descartar un candidato de tres casillas simltáneamente. La casilla clave está en la novena fila – cuarta columna. Siguiendo las cadenas azul y rosada, se puede demostrar que cualquiera sea el valor de la casilla clave (4 o 7), ninguna de las casillas amarillas puede tomar el valor 7. Les dejo la demostración como ejercicio.