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). 

Sudoku y los Marlins de Miami

Pregunta: ¿Qué tienen en común Kyle Barraclough, Nick Wittgren, Dustin McGowan, Brian Schneider, David Phelps, Mike Dunn, y J. T. Realmuto, además de jugar en las Grandes Ligas de Béisbol para el equipo de Miami Marlins en 2016 y la mayoría ser lanzadores relevistas?

Respuesta: Su afición por el sudoku. Y que formaron un equipo que compite entre sí por resolverlos... ¡durante la temporada de juegos! Al menos por dos meses...

La historia es de septiembre de 2016. 

Tim Healey, reportero del Sun Sentinel, nos lo revela en su publicación "Para los relevistas de los Marlins, hay un juego antes del juego: Sudoku". 

En julio de ese año, los Marlins jugaban en St. Louis contra los Cardenales. El primer día, durante el descanso, Barraclough y Mc Gowan hallaron el sudoku del diario local y lo resolvieron.  Al segundo día se les unió Nick Wittgren y el último día del juego el entrenador Schneider se sumó al grupo demostrando tener más habilidad que los tres lanzadores.

A partir de allí este pasatiempo numérico se integró a las habituales actividades de los relevistas previas a los juegos en los que participaban; con la característica de que se convirtió en un reto que tomaron muy en serio. Recordemos que a los beisbolistas no les gusta perder...

El equipo -dice el reportero- saca copias del juego que aparece en el USA Today -que varía en dificultad- y se sientan juntos, generalmente en el tiempo que queda entre el estiramiento de los lanzadores y la práctica de bateo. David Phelps, Mike Dunn (ahora con Colorado Rockies) y el catcher Realmuto se integraron a esta competencia que, aseguran, es el reto más estimulante del día... cuando no son llamados a jugar béisbol, claro. 

Las declaraciones que los jugadores le hicieron a Healey, su preocupación por solucionar el sudoku primero que los demás, la presión al ver que otros anotan y ellos tienen el cerebro bloqueado, la alegría de ver cuando alguno gana y la sorpresa de que haya quién tenga más habilidad, son creíbles y fácilmente comprensibles aún para los que "no" somos adictos al sudoku, ni deportistas profesionales.

Sudoku Diet: Delgado y sano

¿El Sudoku ayuda a adelgazar? Y si es así, ¿cuántos sudokus hay que contestar para bajar los kilitos que nos sobran? 

No sé. Parece que el cerebro consume 90 calorías por hora mientras los resolvemos, sin necesidad de ejercicio extra: sentaditos en la silla y con lápiz en mano. Claro que si al mismo tiempo comemos una galleta con chips de chocolate -56 cal-, ¡pues ya valió! Y además, ya entrados en eso de comer galletas, de seguro te comes más de una... 

Un texto publicado en Daily Mail por David Wilkes en 2009, menciona la investigación de Tim Forrester junto con un comentario de la British Dietetic Association.  Ambos dejan claro que, para satisfacer la necesidad de energía, el cerebro consume calorías, no grasa. Entonces no hay escapatoria: hay que hacer ejercicio y cuidar la alimentación.  

Por otra parte, Jay H. Green, en su libro "The Sudoku Diet: Creating Your Optimal Health Through Logic" (que incluye menús, consejos y juegos), relaciona la alimentación, la salud y el sudoku. Sin desatender la importancia de una buena dieta, asegura que iniciar un sudoku (o resolver una parte) antes de cada comida permite una mejor digestión, hace perder peso, mejora la salud, la vitalidad, la memoria, la claridad de pensamiento, la capacidad sexual y la conciencia; pues funciona como una técnica de relajación divertida (meditación activa, la llama).

Afirma que la disciplina, atención, conciencia, paciencia, lentitud, intuición, y confianza en sí mismo que aplicamos al resolver este pasatiempo lógico, generan emociones que producen sensación de logro y felicidad y que esa "nueva" inercia es la clave que nos permite llegar relajados y disfrutar de los alimentos, con la consecuencia de una salud óptima. 

Aparentemente sólo necesitas un lápiz, un sudoku y "tu cerebro" antes de cada comida.

Trump, Jerry Martin y las capacidades para resolver un sudoku

Mi intención original, al iniciar el blog de sudoku, era comprender cómo funciona este reto, este cuadrado numérico. Y, a estas alturas, no sólo no lo he logrado, sino que ni siquiera he avanzado.

Estos casi dos meses y medio que no hice aportaciones a esta página, no significan que abandoné mi inquietud. ¡Para nada! He seguido resolviendo sudokus, aplicando estrategias, buscando comprobar procesos mentales que me llevan en una u otra dirección para decidir qué número poner en una celda o cuál candidato quitar. Y sigo tan alejada de mi objetivo: Todavía no entiendo cómo se enredan los números para ofrecernos el reto, ni cómo podría "ver" las opciones lógicas.

Tengo fe en que, si persevero, llegará el momento de la revelación. Sí. Eso creo. ¿Pero si no es así? ¿Todos podremos, o tendremos la capacidad, de resolver un sudoku? 

En el artículo "Trump vs. Sudoku", Jerry Martin -maestro retirado-, considera que hay al menos tres capacidades mentales indispensables para lograrlo. Además asegura -en otra entrevista- que se pueden enseñar a los niños a través del sudoku, pues les permiten "no sólo aprender a razonar, sino a pensar críticamente, a ser exactos y a trabajar (juntos) para resolver problemas. Habilidades que se traducen en muchas facetas de la vida" -dice él. 

Estas capacidades son:

1° Se debe estar 100% seguro al seleccionar cada número. No hay lugar para la inexactitud, esto nos llevaría a equivocaciones, pérdida de tiempo, desgaste, cansancio y cero resultados. (La calidad de la información es importante).

2° Hay que ser capaz de discernir constantemente entre la información relevante y la irrelevante. En cada celda sin llenar habrá candidatos que podrían excluirse -o ignorarse- y que, al hacerlo, nos permiten "ver" al candidato correcto y, por tanto, seleccionarlo. Cosa que no lograríamos si no descartamos información no relevante.

3° No debemos comprometernos a una acción (anotar un número, eliminar un candidato o emplear una estrategia) antes de tener información adecuada. (Y bastante información).

En cuanto a Donald Trump, Jerry Martin afirma que "si él cree lo que dice" en campaña, donde sus declaraciones son inexactas o falsas, además de irrelevantes y con salto a conclusiones prematuras basado en información inadecuada, seguro es incapaz de resolver un sudoku en privado; pues los procesos mentales que crearon estas declaraciones violan los tres requisitos básicos del Sudoku.

Algoritmos para generar y solucionar Sudokus

Algoritmos. Es lo primero en que se piensa cuando se habla de resolver un Sudoku. O en lo primero que piensan los matemáticos, científicos y expertos en programas de computación.

Para ellos parece inevitable traducir el pensamiento que nos lleva a resolver el juego en una serie de instrucciones que una computadora -o cualquier persona- pueda seguir con el resultado más eficiente posible. Los algoritmos -ahora me doy cuenta-, nos han acompañado siempre ayudando a la humanidad a evolucionar, desde el elemental conocimiento de cómo encender una fogata hasta el complicado análisis de genomas o el desarrollo de inteligencia artificial.

El análisis del problema (en este caso un sudoku), las limitaciones que ofrece, el objetivo, los pasos para ir llenando cada celda, la decisión del orden de cada uno, si se trabaja primero con las celdas o con los números en progresion ascendente o descendente, la colocación de cada dígito, el marcado de candidatos..., cada mínimo detalle que nos permite ir tomando decisiones es tomado en cuenta (y es necesario) si queremos obtener una solución correcta para nuestro sudoku, y para todos los posibles sudokus a partir del algoritmo.

Aparentemente no sólo nuestra vida diaria sería imposible si no nos apoyáramos en los algoritmos. También el universo parece explicarse con ellos. ¿Por qué? O, más bien, ¿cómo? No lo sé, pero desde las mas remotas épocas el hombre se ha valido de los algoritmos, no sólo verbales, también matemáticos.

Tal vez es la mejor forma para que nuestra mente entienda las cosas, las aprenda y las realice.

Una vez que podemos señalar las partes que componen el todo, podemos recomponerlo, y posteriormente repetirlo con éxito.

Aún sin saberlo usamos algoritmos. Y cada vez son más empleados, principalmente en los programas de computadora. Lo interesante es que el sudoku, con sus condiciones restrictivas para crearse y solucionarse, plantea un problema análogo a varias importantes inquietudes científicas, por lo que tanto por su condición de cuadrado latino, como por sus potenciales algoritmos, es cada vez más y más estudiado.

Trillones y trillones de Sudokus diferentes y sudokus equivalentes

¿Cuántos sudokus diferentes existen? 

Es una pregunta aparentemente simple que interesa a científicos, matemáticos, lógicos, y a expertos en informática y computación, tal vez por el reto que implica definir este problema. Y parece que la teoría combinatoria puede aportar alguna respuesta. Pues es precisamente lo que intenta: contar el número de maneras en que unos objetos dados pueden organizarse de una determinada forma. (Ian Anderson).

En el caso del sudoku, cuántas combinaciones diferentes se obtienen de acomodar los números del 1 al 9 en una rejilla de 9X9 (cuadrado de 9 filas y 9 columnas) sin que se repitan los dígitos ni en fila, columna o región.

Antes de responder: ¡trillones! o ¡miles de trillones! o cualquier cantidad que se nos ocurra, hay que hacer varias aclaraciones:

Primero, el sudoku incompleto -el pasatiempo que parte de una rejilla resuelta, con un mínimo de 17 pistas, simetría, rotación y una solución única-, no forma parte del cálculo. Se estiman únicamente las rejillas completas, los posibles sudokus terminados.

Segundo, los "sudokus equivalentes" deben descontarse del total obtenido, según algunos investigadores. No son iguales, no exactamente. Pero tampoco son diferentes.

Recordando que el sudoku es un subconjunto del cuadrado latino, encontramos relación de equivalencia entre dos "sudokus" si uno de ellos puede ser obtenido permutando las filas (1 a 3; 4 a 6; 7 a 9), o las columnas (1 a 3; 4 a 6; 7 a 9) o permutando los dígitos (1, 2, 3..., 9).

Tercero, también se deben descontar los sudokus equivalentes que se forman por operaciones de simetría como rotación (0°, 90°, 180°, 270°) y reflexión (la imagen reflejada en el espejo).

   

Sudoku conjugado con rotación de 90°

Si giráramos el sudoku 90° (o 180°, o 270°) en el sentido de las manecillas del reloj, veríamos que las filas pasan a ser columnas y viceversa, pero la relación entre los números se mantiene, igual que las diagonales ¡Aunque paremos el sudoku de cabeza! Lo mismo ocurriría en la imagen del espejo. La estructura, en este caso, no el aparente acomodo, es la misma. 

Sudoku para permutar columnas 

En este caso, en que las tres columnas dentro de cada caja pueden cambiar de lugar, vemos que hay 6 posibles acomodos por región de 3X9, pero, al igual que en el sudoku para filas, las relaciones de equivalencia se mantienen incluso las opciones de candidatos ¡siguen igual en las casillas vacías!

Sudoku para permutar filas

Estos sudokus equivalentes también podemos rotarlos y reflejarlos y, por tanto, también descartarlos.

Las estimaciones hechas por Bertram Felgenhauer (Technical University of Dresden, Germany) y Frazer Jarvis (University of Sheffield, England) dan alrededor de 6,670 trillones de sudokus. De allí debemos descontar las restricciones de equivalencia por permutaciones, rotación y reflexión y nos quedarían alrededor de 5,472 millones de posibles juegos, según Jean-Paul Delahaye (University of Sciences and Technologies of Lille in France) The Science behind Sudoku.
No creo que conocer la cantidad de sudokus posibles sea tan importante como profundizar en la esencia del sudoku, Si cambio un número, por decir el 9 y lo pongo en el lugar del 3, y el 3 lo permuto por un 5, y el 5 por un 9... ¡Este nuevo sudoku también es equivalente! Porque tiene la misma "naturaleza" -estructura- del que se deriva.
¡Sorprendente!

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.