XY-Wing: Estrategia para Sudoku difícil

En un sudoku, no basta con "comprender" cómo funciona la estrategia XY-Wing para eliminar candidatos o "saber" cuándo puedes (o debes) buscarla: Hay que localizar el patrón para aplicarla.

Primero hay que estar seguros de que ya no se puede ni anotar otro número, ni eliminar algún candidato. Entonces hay que enfocarse únicamente en las casillas con dos candidatos para poder encontrar, o identificar, tres celdas "pista" (A, B, C) que nos indiquen otra celda (o hasta 5) a la que le podremos eliminar un candidato más. 

Hay dos patrones XY-Wing. 

El más sencillo es cuando las casillas pista (A, B, C) forman tres de las cuatro esquinas de un cuadrilátero. La cuarta esquina será la celda a la que se le eliminará el candidato imposible. Dos celdas pista (A, B) están en la misma fila, y dos (B, C) en la misma columna -o sea, una (B) es el eje para las otras dos-, pero ninguna celda pista comparte la misma caja de 3x3 con ninguna de las otras, ni con la cuarta (D) que comparte fila con C y columna con A: están en 4 cajas distintas; sólo se puede eliminar un candidato.

En el otro patrón, los candidatos a eliminar podrían ser hasta cinco, de cinco celdas distintas; y tanto las casillas pista, (A, B, C) como las celdas con candidatos a eliminar se encuentran dentro de 2 cajas de 3x3, contiguas, vertical u horizontalmente, o con la otra caja entre ellas. 

En este patrón, una casilla pista A estará sola en una caja y estará alineada, en fila o columna, con una de las otras dos casillas pista B (o C), que comparten caja pero que, entre ellas, no pueden estar ni en la misma columna, ni en la misma fila. De este modo las tres casillas pista formarán un ángulo. Uno de los extremos de este ángulo será la casilla pista sola (A) y el otro extremo será la casilla pista C (o B) con la que no comparte fila o columna. El número candidato que las celdas extremo (A y C) tienen en común será el candidato que se buscará para eliminarlo de las casillas que reciban influencia de ambas celdas pista extremo (o sea de A y C). Y que puede estar en hasta cinco celdas dentro de las dos cajas.

A partir de aquí el sudoku se resuelve casi solo. 

CARACTERÍSTICAS DE LAS CELDAS PISTA

Las celdas pista A, B, C deben estar relacionadas entre sí por tres números, y cada una de ellas sólo puede tener dos de ellos. Por ejemplo: 1, 2, 3, serían los números y las combinaciones para las tres casillas serían: A 1-2, B 2-3, y C 3-1 

Si el número que se repite en las celdas extremo es el que debemos eliminar y en el segundo patrón de XY-Wing, A y C son las celdas extremo y los candidatos de A son (1-2) y los de C son (3-1), el número a eliminar en las casillas comunes a ambas celdas pista es el (1). 

Backdoor Sudoku contra XY-Wing

Número nudo, backdoor, picaporte, celda mágica, el número que destraba el sudoku.... o que se interpone entre tú y la solución... Lo presientes cuando estás resolviendo un sudoku difícil y requieres de estrategias avanzadas para continuar. Lo percibes esquivo, retador, burlón. Sabes que lo superaste cuando el sudoku vuelve a ser esa cadena melodiosa de sencillos uno a uno... ¿O todo fue producto de tu exasperada lógica? No es una leyenda urbana, sí existe.

En la actualidad se usa el backdoor para determinar el grado de dificultad de un sudoku. La mayoría de los sudoku de nivel difícil tienen uno, los de nivel superior pueden tener dos, tres en el caso del Easter Monster.  

El backdoor puede ser un número -o un conjunto de números- que al ser acomodados en sus celdas correspondientes, conducen a la solución sin ningún tipo de técnica avanzada. Van descubriendo candidatos únicos en cada una de las celdas restantes.

Parece cosa de magia. ¿Será el alma, la esencia, del sudoku? 

Hay quienes afirman que todos los sudoku, incluso los fáciles, tienen al menos uno. Tal vez, aunque en ésos no se siente diferencia al solucionarlos. La computadora los resuelve sin aplicar ninguna estrategia avanzada de ésas de nombres encriptados, o  de constelación: cometa, rascacielos, bolsa de serpientes, xy-wing... 

Nadie sabe -al menos yo no sé- cómo podríamos descubrirlos lógicamente desde el inicio, como no sea por azar. Y en el azar, ya se sabe, no tienes seguro nada, tendrías que llevar el juego hasta el final para saber que acertaste. ¿Habrá una fórmula, más allá de la adivinanza, que asocie celdas y dígitos de manera que revele dónde se ubica el nudo? Lo que se hace para identificar el backdoor es tomar el dígito de la solución y se prueba. Un programa de computadora lo verifica en segundos. Si ese dígito/celda destrabador estuviera como pista, el sudoku sería nivel facilísimo. Vean el ejemplo que pongo a continuación.

Sudoku difícil

Inicia con 27 números dados y, con estrategias básicas -x wing, entre ellas-, podemos completar 26 celdas más. Es decir 53 celdas. 

Técnica xy-wing

En ese punto Simple Sudoku sugiere eliminar candidatos con XY-Wing (las tres celdas azules y el recuadro), que es una técnica algo avanzada (y, hasta el momento, mi reto insuperable). Una vez aplicada esta estrategia, el sudoku no tiene mayor complicación.

Backdoor 5

Pero ¿qué pasa si al inicio agregamos el número 5 en la celda amarilla (fila 4, columna 9)? El número 9 coloreado en rojo sería el primero en ubicarse y después todos los movimientos son por candidatos únicos. Ese 5 en la celda "f4c9" es el backdoor de este sudoku...
Es posible, sí, encontrar por azar, por error, o diversión los backdoor, pero usarlos para resolver el pasatiempo le quita todo el mérito del esfuerzo y de la aplicación de la lógica. Sí es divertido encontrarlos porque, como pueden ver, no está asociado a la estrategia XY-Wing. (Hay otro número, el 6, que sí lo está, pero ése requiere combinarse con otro).
¿Cuál es la naturaleza y que clase de problemas contienen estos "números nudo"? ¿Cómo la intuición humana logra lo que no pueden los algoritmos matemáticos? Estos y otros puntos siguen siendo investigados por expertos, entre otros motivos, para complicarnos más los niveles de sudoku.

Arto Inkala: Sudokus con nombre propio

Hoy también empecé el día intentando comprender un sudoku. Cómo aplicar la estrategia, de nivel medio, XY-Wing. Y sigo en ésas. 

Era uno sencillo, no el Escargot (2006), el Daily Mirror (2010) o el Everest (2012) diseñados por el finlandés Arto Inkala y considerados por él mismo, en cada momento, como "el sudoku más difícil del mundo" -con su palabra, y su propio ranking, basta-. El Everest, asegura Inkala, es insoluble para todos, excepto para las mentes más brillantes. Debe resolverse, dice, anticipando hasta ocho movimientos, como en el ajedrez...

No son los únicos sudokus que encontré en internet que tienen nombre -y registro-. Están también sus rivales: Golden Nugget, por ejemplo, creado por Tarek, y el Eastern Monster de JPF; hay quienes los consideran de mayor dificultad que los tres primeros. En realidad, muchísima gente. Y debe haber más juegos que compitan por esa categoría.

Y es que, decidir cuál sudoku ofrece mayor dificultad, no es fácil. Se supone que son hechos para ser resueltos lógicamente y a mano, por seres humanos pensantes. Pero Inkala -al igual que los otros competidores, exceptuando a Nikoli en donde los hacen a mano-, los elabora con ayuda de computadora, ya que necesita revisar cerca de un millón de sudokus antes de dar con la opción más difícil con 17 números dados. Esto le ha tomado, en algún caso, alrededor de tres meses. Mi artimaña de intentar resolverlos con Simple Sudoku -u otro programa parecido- parece que no es exclusiva mía. Entonces también cuidan ese aspecto: no hay ningún sencillo descubierto, ni oculto; cada celda tiene al menos dos opciones que la computadora registra como posible solución, y la pobre no da una. Allí ni la paciencia le vale... En menos de un segundo decide que no hay pista a seguir. Y se acabó. ¡Sin anotar ni sugerir absolutamente nada...! Porque todavía no están hechas para hacer conjeturas complejas ¡ni trampas! Con quitar un dígito -de los 17 dados- podría obtener múltiples soluciones... jajaja. También podría anotar, al azar, el número que "desata el nudo", cosa humanamente posible pero, ¿cuál sería la probabilidad de seleccionar el dígito correcto -entre 9- y la casilla -entre 64-, al primer intento? (ya casi me siento matemática...). 

Lo interesante es que cada vez que aparece un sudoku "imposible", de nivel superior a 9 u 11 como el Everest -los difíciles de los diarios son nivel 5-, se mejoran los programas solucionadores de sudokus. El sudoku Eastern Monster, por ejemplo, dio origen a que se descubrieran dos técnicas, lógicas, inimaginables antes por no haberse presentado ese reto: Naked Double Loops y Hidden Double Loops. Esto desencadena que los programas que miden el ranking de dificultad también sufran cambios, principalmente el Sudoku Explainer (SE). Los otros cuatro conocidos son Ravel Minimal Step (RMS), Gfsr, Suexrat 9, y el de Inkala. Los investigadores en Inteligencia Artificial también muestran interés en los sudokus.
Y todo esto ya rebasa, creo, las dimensiones de un simple pasatiempo. Haciendo cada vez más interesante el desarrollo de este juego y poniendo de relieve que la pregunta ha dejado de ser ¿todos podemos solucionar un sudoku incompleto? y la respuesta tampoco se limita a un simple "sí" o "no". Hay que ser doctor en Matemáticas y experto en Computación, mínimo.
Y para crearlos... -o investigarlos- necesitas que te lo encargue una compañía como Efamol (sudoku AI6824 para Efamol) que ofrece productos para evitar el deterioro del cerebro, o que te respalden Universidades importantes como la University of Western Australia o la University College Dublin, en Irlanda.