Master Sudoku, de Marcelo Calniquer.

Esta semana recibí un correo electrónico de un amable lector de este blog, Marcelo Calniquer. Es un ingeniero de sistemas que desarrolló un software para jugar sudokus, que sirve también como solucionador de sudokus y generador de sudokus. Su sitio en internet es www.mastersudoku.com.ar, desde donde pueden bajar gratis el software.

Para solucionar los sudokus ocupa las técnicas explicadas en este blog. Tiene una apariencia similar a como si uno estuviera solucionando un sudoku con lápiz y papel, con las ayudas lógicas de un programa computacional como por ejemplo resolver paso a paso o mostrar en forma destacada los dígitos que a uno le interesa explorar. Además es posible ver el registro de los desarrollos que hace el programa cuando resuelve un puzzle. Es muy interesante. Hoy lo he probado con un sudoku extremadamente difícil publicado en un foro de internet por MattM.


El software de Marcelo lo resolvió en un par de segundos. Les copio el registro para que lo examinen paso a paso.

+---+---+---+
|230|005|010|
|010|800|092|
|000|000|000|
+---+---+---+
|390|080|600|
|000|907|000|
|001|060|028|
+---+---+---+
|000|000|000|
|850|002|070|
|060|700|043|
+---+---+---+

<<<>>>
1) Sencillo Descubierto {5} en f4c8
2) Sencillo Descubierto {3} en f5c8
3) Sencillo Oculto {9} en f6c7
4) Sencillo Descubierto {1} en f8c7
5) Sencillo Descubierto {4} en f5c7
6) Sencillo Descubierto {1} en f5c9
7) Sencillo Descubierto {7} en f4c9
8) Pares Descubiertos {4,6} en f1c4 f1c9
-> Se excluyó el candidato 4 de la posición f1c3
-> Se excluyó el candidato 6 de la posición f1c3
-> Se excluyó el candidato 4 de la posición f1c5
9) X-Wing {6} en f1c4 f8c4 f1c9 f8c9
-> Se excluyó el candidato 6 de la posición f3c4
-> Se excluyó el candidato 6 de la posición f7c4
-> Se excluyó el candidato 6 de la posición f3c9
-> Se excluyó el candidato 6 de la posición f7c9
10) XYZ-Wing {4} en f2c6 f1c4 f6c6
-> Se excluyó el candidato 4 de la posición f3c6
11) Cadena XY {1} en f4c6 f4c3 f9c3 f9c1
-> Se excluyó el candidato 1 de la posición f9c6
12) Cadena XY {9} en f1c5 f1c7 f3c8 f1c9 f3c9 f7c9
-> Se excluyó el candidato 9 de la posición f7c5
13) Cadena Inferencia Alterna Débil {2} 2[f5c3]-2[f5c5]=5[f5c5]-5[f9c5]=5[f9c7]-2[f9c7]=2[f9c3]-2[f5c3]
-> Se excluyó el candidato 2 de la posición f5c3
14) Cadena Inferencia Alterna Continua {2} 2[f4c3]-2[f9c3]=2[f9c7]-5[f9c7]=5[f9c5]-5[f5c5]=2[f5c5]-2[f5c2]=2[f4c3]
-> Se excluyó el candidato 2 de la posición f7c3
-> Se excluyó el candidato 8 de la posición f9c7
15) Sencillo Oculto {8} en f9c6
16) Rectángulos Vacios {9} en f1c3 f1c5 f7c3 f7c6 f8c5 f9c5
-> Se excluyó el candidato 9 de la posición f7c3
17) XY-Wing {9} en f9c7 f7c9 f9c3
-> Se excluyó el candidato 9 de la posición f7c1
18) Rectángulos Vacios {9} en f1c5 f1c3 f9c5 f8c3 f9c1 f9c3
-> Se excluyó el candidato 9 de la posición f9c5
19) Candidato Bloqueado {9} en f9c1 f9c3
-> Se excluyó el candidato 9 de la posición f8c3
20) Cadena Inferencia Alterna Débil {1} 1[f7c6]-9[f7c6]=9[f3c6]-9[f3c1]=9[f9c1]-1[f9c1]=1[f9c5]-1[f7c6]
-> Se excluyó el candidato 1 de la posición f7c6
21) Cadena Inferencia Alterna Continua {5} 5[f9c5]-5[f5c5]=2[f5c5]-2[f5c2]=2[f7c2]-2[f7c7]=2[f9c7]-5[f9c7]=5[f9c5]
-> Se excluyó el candidato 5 de la posición f7c5
22) Cadena Inferencia Alterna Continua {6} 6[f7c6]-9[f7c6]=9[f7c9]-9[f8c9]=6[f8c9]-6[f1c9]=6[f1c4]-6[f8c4]=6[f7c6]
-> Se excluyó el candidato 3 de la posición f7c6
-> Se excluyó el candidato 4 de la posición f7c6
23) Cadena Inferencia Alterna Débil {3} 3[f3c6]-9[f3c6]=9[f7c6]-9[f7c9]=5[f7c9]-5[f7c4]=5[f6c4]-3[f6c4]=3[f6c6]-3[f3c6]
-> Se excluyó el candidato 3 de la posición f3c6
24) Cadena Inferencia Alterna Débil {5} 5[f3c1]-9[f3c1]=9[f9c1]-9[f9c3]=2[f9c3]-2[f9c7]=5[f9c7]-5[f7c9]=5[f3c9]-5[f3c1]
-> Se excluyó el candidato 5 de la posición f3c1
25) Cadena Inferencia Alterna Débil {6} 6[f3c1]-9[f3c1]=9[f9c1]-1[f9c1]=1[f9c5]-5[f9c5]=5[f5c5]-5[f5c1]=6[f5c1]-6[f3c1]
-> Se excluyó el candidato 6 de la posición f3c1
26) Cadena Inferencia Alterna Débil {7} 7[f7c2]-2[f7c2]=2[f7c7]-2[f9c7]=2[f9c3]-2[f4c3]=4[f4c3]-4[f6c2]=7[f6c2]-7[f7c2]
-> Se excluyó el candidato 7 de la posición f7c2
27) Cadena Inferencia Alterna Débil {9} 9[f3c3]-9[f3c6]=9[f7c6]-9[f7c9]=5[f7c9]-5[f9c7]=2[f9c7]-2[f9c3]=9[f9c3]-9[f3c3]
-> Se excluyó el candidato 9 de la posición f3c3
28) Cadena Inferencia Alterna Débil {9} 9[f3c5]-2[f3c5]=2[f3c4]-2[f4c4]=2[f4c3]-2[f9c3]=9[f9c3]-9[f9c1]=9[f3c1]-9[f3c5]
-> Se excluyó el candidato 9 de la posición f3c5

El puzzle se resolvió por fuerza bruta
-> Sencillo Descubierto: 6
-> Sencillo Oculto: 2
-> Candidatos Bloqueados: 1
-> Pares Descubiertos: 1
-> X-Wing: 1
-> Rectángulos Vacíos: 2
-> XY-Wing: 1
-> XYZ-Wing: 1
-> Cadenas XY: 2
-> Cadena Inferencia Alterna: 11

+---+---+---+
|238|495|716|
|514|876|392|
|976|231|584|
+---+---+---+
|392|184|657|
|685|927|431|
|741|563|928|
+---+---+---+
|427|319|865|
|853|642|179|
|169|758|243|
+---+---+---+

¡Brillante, le bastaron sólo 28 pasos para resolverlo! Excelente programa Marcelo. Felicitaciones. Aún no he probado el generador de sudokus; ya lo comentaré una vez que haya hecho algunas pruebas.

Volviendo un poco al sudoku del ejemplo, podemos resolverlo de una manera sencilla de la siguiente manera. Primero resolvemos todos los singles, como por ejemplo el 5 de la sexta caja. El sudoku queda de la siguiente manera:


Ahora vemos que existen gemelas [4,6] en la primera fila. Resolviendo la fila, el puzzle queda como sigue:


Aquí es donde sacamos nuestro as de la manga de la camisa. El diagrama siguiente muestra una cadena de implicancias al modo mostrado el 25 de noviembre de 2007.


Siguiendo esta cadena en azul, se deduce que si {f5,c3}=8 entonces {f5,c2}=8. Pero no pueden haber dos 8 en la quinta fila, luego {f5,c3} no puede ser 8. Al eliminar el 8 de la celda {f5,c3}, el sudoku se convierte en un sudoku trivial en el que siempre es posible encontrar un único candidato posible para alguna celda, o una única celda para algún candidato. Lo difícil, por no decir lo imposible, era aquí encontrar la dichosa cadena de implicancias mostrada en azul.

Bueno, todo esto me ha animado a buscarme el tiempo para continuar con el plan trazado en este blog el 15 de julio de 2007, y que por escasez de tiempo precisamente me he visto forzado a no continuar. Pero quedan varias técnicas aún por describir.

Hasta la próxima.

El Imperio Digital.

Estoy leyendo un libro muy bueno sobre la evolución de la internet, desde sus inicios hasta hoy. Muy recomendable para todos los interesados en la tecnología de la información. Está escrito en un modo periodístico, así es que su lectura se hace muy fácil a la vez qe amena. Su nombre es El Imperio Digital, escrito por Leandro Zanoni. Lo pueden bajar en formato PDF directamente desde su sitio oficial aquí.

Cadenas de Inferencias Alternas -Parte 6.

Continuo hoy, después de este largo período estival, el análisis de las técnicas avanzadas de resolución de sudokus endemoniadamente difíciles. En el sudoku de hoy tenemos una cadena corta y elegante. Se inicia en 9[f2c8], baja al 9[f7c8], el cual tiene una inferencia débil con 3[f7c8]. De éste se enlaza con 3[f7c9], el cual tiene una inferencia débil con 5[f7c9]. Finalmente, vuelve arriba al 5[f2c9]. En este punto se obtiene algo muy interesante. En este caso no es necesario trazar la línea que cierra el loop alterno, porque notamos que el 5[f2c9] comparte caja y fila con el 5[f2c8]. Al comenzar con un enlace fuerte desde 9[f2c8], estamos diciendo que "si el 9 no está en [f2c8], debe estar en [f7c8]. Pero si no está en [f2c8], entonces el 5 debe ser verdad en [f2c8]. Sin embargo, siguiendo el loop, hemos demostrado que si [f2c8]=5, entonces también [f2c9]=5, lo cual es contradictorio. Se puede establecer entonces una nueva regla. Si el final de una cadena de inferencias alternas llega a la misma unidad (fila, columna o caja) del inicio de la cadena, y ambos números son diferentes (en nuestro ejemplo 9 y 5), entonces cada número final de la cadena no puede existir en la punta contraria de la misma. Esto es porque ambas puntas de la cadena con verdad. En nuestro ejemplo, el 5 no puede ser en [f2c8] y el 9 no puede ser en [f2c9], aunque en este caso en esta casilla no existe ningún nueve. En resumen se puede borrar el 5 de [f2c8].

Saludos, y pásenlo bien.

Cadenas de Inferencias Alternas - Parte 5.

Volviendo al sudoku del domingo antes pasado, podemos tratar de examinarlo para ver si podemos hallar alguna posible eliminación de candidatos, utilizando nice loops con implicancias basadas en "bivalue" y "bilocations". El ideal sería encontrar las cadenas que permitan eliminar los mismos candidatos que eliminábamos aquel domingo. No he tenido tiempo de buscarlas con detención -no siempre se hallan-, pero a cambio encontré esta otra:

En la casilla amarilla podemos eliminar el 7, porque podemos deducir -siguiendo la cadena de implicancias azul- que si esa celda fuera 7, entonces también sería 7 la celda [f8c2], o sea, habrían dos 7 en la segunda columna.

Les dejo para su entretención un sudoku publicado en EEUU como "muy difícil", pero en realidad es de los fáciles. Nos falta aún por ver algo más de las Cadenas de Inferencias Alternas. Así es que seguiremos la semana que viene.

Pásenlo bien.

Sudokus de EEUU

Este fin de semana vamos a descansar un rato de las Cadenas de Inferencias Alternas, y voy a compartir con ustedes un par de sudokus publicados en estos dias en los Estados Unidos. Están catalogados en sus publicaciones como muy difíciles, pero conforme a mi clasificación son sudokus fáciles (siempre es posible hallar casillas en que sólo puede ser verdad un único candidato, o una única casilla donde puede ser ubicado un número). ¡Que los disfruten!

Cadenas de Inferencias Alternas - Parte 4.

Veamos hoy día el siguiente sudoku.

(inferencias fuertes en azul, inferencias débiles en rojo)

La notación para este loop es la siguiente:
5[f1c3]=5[f9c3]-9[f9c3]=9[f2c3]-9[f3c1]=9[f3c8]-5[f3c8]=5[f3c2]

Esta es una Cadena de Inferencias Alternas "continua", ya que alterna las inferencias fuertes y débiles a lo largo de todo el loop, sin discontinuidad; no hay enlaces débiles adyacentes. Veamos algunas de sus características en algunas de sus celdas claves:

1. [f9c3] tiene un enlace fuerte entrando al candidato 5. Esto significa que si el 5 no es verdad en [f1c3], debe ser verdad en [f9c3]. Lo anterior elimina como posibles verdaderos a todos los otros candidatos de la celda, de manera que no importa si hay un 4 y un 9 en la celda, además del 5. Para enlazar con el 9 en el interior de la celda, tenemos que ir con un enlace de inferencia débil, pues el 5 ha sido declarado como verdadero, significando que el 9 es falso. La única manera de salir de [f9c3] es usando un enlace fuerte al 9 de [f2c3].
2. Una situación similar ocurre en [f3c8], con la diferencia que aquí es el 9 el candidato que entra con un enlace fuerte, y el 2 es el candidato que está de más, por así decirlo. Salimos con un enlace fuerte al 5 de [f3c2].
3. Los 9 de la primera caja están conectados con una inferencia débil, pero sólo hay dos 9 en la caja. Esto es porque hemos entrado a la caja mediante un enlace fuerte. Estamos diciendo que el 9 de [f2c3]es verdad, así es que no puede ser verdad en [f3c1]. Eso es un enlace de inferencia débil.
4. Lo mismo se puede decir de los 5 de la primera caja. Un enlace de inferencia débil une dos enlaces de inferencia fuerte, y hemos vuelto al comienzo.

¿Qué deducciones se pueden hacer aquí? La Regla número 1 de Nice Loops establece que cualquier valor fuera de la cadena en un enlace débil puede ser eliminado. Ahora, los dos enlaces débiles de la primera caja no contienen ningún candidato extra en la caja, de manera que ahí no hay nada que eliminar. Pero tenemos enlaces débiles dentro de las celdas [f9c3] y [f3c8]. Esta es una de las extensiones interesantes que convierten a las CIA's en una herramienta tan poderosa.

Ya hemos usado la Regla 1 de Nice Loops para eliminar dígitos del mismo número porque el enlace era entre dos candidatos del mismo valor en diferentes celdas -un caso de "bilocation". La alternativa y estrategia opuesta es la eliminación por "bivalue". [f9c3] y [f3c8] contienen enlaces dentro de la celda, de diferentes valores; en consecuencia, todos los candidatos extras pueden ser eliminados. Esto significa dar un giro a la Regla 1 en su cabeza: en vez de "mismo valor en otras ubicaciones", estamos asumiendo "otros valores en la misma ubicación". Este espejismo es un aspecto muy interesante de las CIAs.

Otra forma de mirar esto es como sigue: uno u otro de los candidatos unidos por aquel enlace débil es verdadero. No sabemos cual, pero uno de ellos es. No hay espacio para otros candidatos. Por lo tanto podemos eliminar el 4 de [f9c3] y el 2 de [f3c8].

Pásenlo bien.

Graduación de Sudokus

Algo que no es fácil a la hora de construir sudokus es cómo graduarlos. Todas las personas tenemos diferentes maneras de resolverlos, por lo tanto cada persona encuentra caminos diversos para llegar hasta el último número. Hay veces que un mismo sudoku, difícil de resolver, si se gira en 90° queda más fácil, porque por la nueva visión que se tiene de los números, a uno le cuesta menos encontrar los que están como incógnitas. En mi caso, trato de aplicar una norma más objetiva, y le indico al computador que lo resuelva, y la graduación queda hecha en base a los pasos y técnicas que él debe ocupar para resolverlos. Como los resuelve siempre de una misma forma (el pobre es un computador no más), entonces se puede comparar el grado de dificultad de un sudoku respecto de otro.

Más abajo les dejo dos sudokus para que ustedes hagan la prueba y me lo comenten después (sus comentarios me permiten ajustar la puntería). El primero es un clásico sudoku de 17 números iniciales, hecho por un profesor australiano de matemáticas. Es bastante sencillo, pues siempre queda alguna celda en que sólo es es posible un único candidato. El segundo es uno que hice yo, a partir del primero. Es un poco más difícil porque el computador llega a un punto en que ninguna casilla tiene un único candidato posible y es necesario empezar a ocupar algunas de las técnicas avanzadas que hemos visto en este blog.

Los invito pues a resolverlos, con el único cuidado de no ocupar los números que ya tienen en uno para ayudarse a resolver el otro, pues les repito, ambos tienen la misma la solución. Y después me gustaría que me comentaran cuál les costó más.

Pásenlo bien.

CIA's - Parte 3.

Démosle hoy una nueva mirada al sudoku de la semana pasada. Hay un autor de sudokus y programador, me parece holandés, Henk Westhuis, a quien le debo su particular visión de encontrar una manera más intuitiva de hallar las Cadenas de Inferencia Alternas. Él hace uso de los mismos conceptos BIVALUE (celda con dos candidatos distintos) y BILOCATION (un candidato sólo dos veces en una caja, fila o columna), pero en vez de buscar alternancias de inferencias, busca cadenas de implicancias al modo como veíamos en las cadenas forzadas dobles y cadenas forzadas triple. A diferencia de las cadenas forzadas de implicancias, que no terminan en el mismo candidato en que comienzan, acá se trata de formar un loop de implicancias y por lo tanto, debe terminar en la misma celda y candidato en que comienzan.

En el sudoku de la semana pasada, el 1[f9c9] implica que [f1c9] = 3. El 3[f1c9] implica que [f1c7] = 6. Este 6 implica que [f9c7] = 3 (porque de lo contrario la séptima columna se quedaría sin 3). Este 3 implica que [f9c3] = 1. Este loop de implicancias está diciendo que si [f9c9] = 1 entonces [f9c3] = 1, lo cual es una contradicción porque la fila 9 quedaría con dos 1. Por lo tanto [f9c9] no puede ser 1. La misma conclusión a la que llegamos la semana pasada mediante la explicación más ortodoxa de las Cadenas de Inferencias Alternas. En el loop que muestro en el diagrama anterior, intencionalmente no cerré con una línea discontinua desde 1[f9c3] al 1[f9c9], para no enredar el dibujo, pero en rigor debe ir.

Este método de encontrar las Cadenas de Inferencias Alternas es mucho más intuitivo y fácil de hallar para el ojo humano, en la sopa de candidatos que suelen haber en un sudoku a medio terminar, que encontrar las alternancias de inferencias. Y es, a mi juicio, el modo en que hay que acostumbrar el ojo. En las próximas semanas continuaré con más de...Cadenas de Inferencias Alternas (porque aún no lo hemos visto todo). ¡Que lo pasen bien!

CIAs - Segunda Parte.

Hemos visto que las cadenas se forman básicamente de dos formas:

1. Podemos enlazar dos candidatos del mismo valor en un grupo (fila, columna o caja). A esto se le llama, en inglés BILOCATION. O sea, cuando el candidato se encuentra sólo dos veces en ese grupo.
2. Podemos enlazar dos candidatos diferentes en una misma celda. A esto se le llama , en inglés BIVALUE. O sea, cuando en una celda sólo existen dos candidatos.

Existe una tercera manera, que la veremos en otra técnica avanzada (que yo la uso muy poco), denominada ALS, de Almost Locked Sets. Pero ya volveré a ella más adelante. Por ahora nos quedaremos con esos dos tipos de enlaces, BILOCATION y BIVALUE.

El caso del BILOCATION ya ha sido ampliamente explicado a través de los ciclos X, y hemos visto cómo podemos hallar inferencias débiles e inferencias fuertes, y utilizarlas alternadamente para formar las cadenas de ciclos X.

El caso del BIVALUE tiene una lógica similar, pero me detendré en un pequeño análisis lógico. Cuando en una celda existen sólo dos candidatos, estamos en presencia de un enlace fuerte: si el candidato A no es verdadero, entonces es verdadero el B. Cuando en una celda hay más de dos candidatos, estamos en presencia de un enlace débil: si A es verdadero, entonces no es verdadero B (ni C, ni D, etc).

Me parece que quedará más claro analizando un sudoku real.

La celda [f1c9] = 1/3 (esto significa que la celda de la fila 1 columna 9 tiene los candidatos 1 y 3). Puede observarse que si no es 1 entonces es 3 (también se puede pensar que si no es 3, entonces es 1). Es decir es un enlace fuerte. Para efectos de construir una cadena de enlaces alternos (fuertes y débiles) vamos a considerar en este caso el sentido de las flechas, esto es, si [f1c9] no es 1, entonces es 3. En seguida observamos que en la primera fila hay varios 3. Entonces consideremos el 3 de [f1c7]. Como hay varios 3 en la fila 1, entonces tenemos un enlace débil desde el 3[f1c9] hasta el 3[f1c7], esto es, si el 3[f1c9] es verdad, entonces no es verdad el 3[f1c7]. En seguida vemos que a lo largo de la columna 7 hay sólo dos 3, el otro está en [f9c7]. Luego se trata de un enlace fuerte. Podemos decir que si no es verdad el 3[f1c7] entonces es verdad el 3[f9c7]. Ahora observamos que hay varios 3 en la fila 9. Podemos hacer entonces un enlace débil con el 3 ubicado en [f9c3]; o sea, si es verdad el 3[f9c7], entonces no es verdad el 3[f9c3]. Ahora vemos que [f9c3] = 1/3. Entonces podemos ocupar el enlace fuerte que se produce entre el 3 y el 1 de [f9c3], esto es, si no es verdad el 3[f9c3] entonces es verdad el 1[f9c3]. También hay varios 1 en la novena fila, así es que podemos hacer un enlace débil con el 1 de [f9c9]. O sea, si es verdad el 1[f9c3] entonces no es verdad el 1[f9c9]. Y aprovechando que existen varios 1 en la novena columna, entonces podemos cerrar el loop con un nuevo enlace débil que vaya desde el 1[f9c9] hasta el 1[f1c9]. Vemos entonces que en la celda [f9c9] se tienen dos enlaces débiles adyacentes en una cadena de enlaces alternados. Hay una discontinuidad de dos enlaces débiles adyacentes en el 1[f9c9], así es que aplicando la Regla 3 de Nice Loops, podemos eliminar el candidato 1 de [f9c9].

La notación de esta cadena es: 1[f1c9]=3[f1c9]-3[f1c7]=3[f9c7]-3[f9c3]=1[f9c3]-1[f9c9]

Seguiremos con más Cadenas de Inferencias Alternas la próxima semana. ¡Que lo pasen bien!

Cadenas de Inferencias Alternantes (CIAs) - Introducción.

Continuando con el plan bosquejado el domingo 15 de julio, comienzo hoy a explicar las Cadenas de Inferencias Alternantes, que en los foros de internet pueden hallarlas bajo la sigla AICs. Si existe una superteoría de sudoku, o una técnica que encapsule prácticamente todas las técnicas vistas hasta aquí, esa corresponde a las CIAs. Es muy práctico separar las técnicas de cadenas en categorías de X wings, Cadenas XY, Cadenas forzadas, XYZ Wings, Nice loops, etc., dado que todas ellas tienen rasgos que permiten identificarlas más fácilmente. Sin embargo todas ellas son parte de una familia más extendida.

La característica principal de toda cadena es que comienzan en un candidato que tiene una inferencia fuerte a otro candidato, que luego tiene una inferencia débil al siguiente candidato, y así sucesivamente, alternando hasta volver al punto de inicio. Esto puede no haber sido aparente en las Cadenas XY, por ejemplo, las cuales no fueron descritas de esta manera, debido a sus características propias que permiten identificarlas fácilmente. En el futuro re-miraremos esos ejemplos como CIAs. Sin embargo, las CIAs pueden a menudo hacer trucos que ninguna de las otras técnicas pueden replicar.

Como hemos visto en semanas anteriores, los ciclos X tratan de "alternancias". Sin embargo, los ciclos X se aplican exclusivamente a un único candidato (parten en un candidato x con una inferencia fuerte hasta otro x, desde donde siguen con una inferencia débil hasta otro candidato x -donde el candidato x es siempre el mismo- y así sucesivamente hasta completar el loop, pudiendo haber o no discontinuidades). Las CIAs en cambio, toman todo lo que ya hemos aprendido de los ciclos x, y extienden la lógica a tantos números candidatos diferentes como sea necesario. Por decirlo de alguna manera, las CIAs responden a la pregunta "¿cuántas formas existen para hacer una inferencia fuerte o una inferencia débil? Si hay más de una, podemos unirlas en un modo alternante y hacer deducciones que nos conduzcan a efectuar eliminaciones.

Hasta aquí dejo la introducción. El concepto que es necesario retener, es que con las CIAs, los Nice Loops ya no están restringidos a un único número candidato, sino que desde un enlace al siguiente, pueden cambiar de número de candidato. Continuaré la siguiente semana.

Les dejo un sudoku de 17 números iniciales, para que se entretengan un rato.

Ciclos X Agrupados - Ejemplo 3.

Este es un muy buen ejemplo de Ciclo X Agrupado, en el que se puede aplicar la Regla de Nice Loop N° 3, aquella en la que se excluye el candidato que se encuentra en medio de dos enlaces débiles adyacentes. El loop en el candidato 8 se inicia en el nodo de tres celdas azules y baja por la séptima columna con una inferencia débil hasta la celda roja. De ahí sigue por la novena fila con una inferencia fuerte hasta el 8 de la quinta columna novena fila. Desde ahí sube con una inferencia débil hasta la celda amarilla, desde la cual continúa con otra inferencia débil hasta la celda roja de la tercera fila. Finalmente se cierra el loop volviendo al nodo de tres celdas azules, mediante una inferencia fuerte. La discontinuidad se encuentra en las inferencias adyacentes a la celda amarilla, y como se trata de dos inferencias débiles, entonces el candidato 8 de la celda amarilla puede borrarse.

Este otro ejemplo, es el mismo sudoku anterior, en el cual ya hemos borrado el 8 de la tercera fila quinta columna. El loop en el candidato 8 nace en el nodo de dos celdas azules y se dirige hasta la celda amarilla con una inferencia débil. Desde ahí baja mediante otra inferencia débil hasta la celda roja de la séptima columna. Continúa por la novena fila con un enlace fuerte hasta la celda roja de la novena fila quinta columna, y desde ahí sube por la quinta columna con una inferencia débil hasta la otra celda roja. Se cierra el loop volviendo al nodo de celdas azules mediante un enlace fuerte. Nuevamente la discontinuidad está en la celda amarilla, con dos enlaces débiles adyacentes, luego se puede borrar el 8 de la celda amarilla.

Les dejo el siguiente sudoku como ejercicio. Es un sudoku de Andrew C. Stuart, propuesto como ejemplo para resolver empleando varios ciclos X agrupados discontinuos y un ciclo X normal, basados en los candidatos 2 y 4. Sin embargo también puede resolverse empleando sólo técnicas más básicas como Pointing Pair, Rectángulos Vacíos y Wing XY.

Pásenlo bien.

Ciclos X Agrupados - Ejemplo 2.

Les muestro ahora un ejemplo de Ciclos X Agrupados, en que se puede aplicar la Regla 2 de Nice Loops (dos inferencias fuertes adyacentes). En este sudoku, las celdas azules corresponden a un nodo de la cadena.

En la celda amarilla se unen las dos inferencias fuertes, por lo tanto esa celda sólo puede valer 3. Pásenlo bien.

Ciclos X Agrupados - Ejemplo 1

Este es un ejemplo de un sudoku real, en el cual se puede aplicar la regla 1 de Nice Loops, con un nodo de dos celdas agrupadas (en azul), y que permite eliminar el 3 de la celda amarilla. En las próximas semanas les mostraré un ejemplo aplicando la regla 2 y la regla 3 de Nice Loops, con Ciclos X Agrupados.

Ciclos X Agrupados.

En esta entrada comenzaré a explicar los Ciclos X Agrupados, que afortunadamente, no tiene nada que ver con "grupos" de ciclos X. El concepto "agrupado" se refiere a nodos en un ciclo X individual, los cuales contienen dos o tres celdas en vez de una.

En la figura, todas las celdas con letras contienen al candidato 3. Hay un ciclo continuo (enlaces fuertes y débiles alternando) comenzando en A. Hay un enlace débil en BC y otro en DE. Sin saber aún cuál de las celdas X, Y o Z es la solución (vale 3), si es que una de ellas es la solución, lo cierto es que cualquiera de ellas eliminará a A o a E (si por ejemplo X=3, A y E ya no pueden valer 3). De igual modo, si E es verdad, entonces no lo son ni X, ni Y, ni Z, y A es verdad.

Podemos pensar en XYZ como un nodo para los propósitos de nuestra lógica. Esto promueve los enlaces desde A y E (hasta XYZ) a enlaces fuertes, y la notación para esta parte del loop queda entonces:

3[E]=3[X][Y][Z]=3[A]=

La característica importante es que las celdas (XYZ) estén todas en la misma caja. Una punta de la cadena (en este caso A) está siendo apuntada por las celdas del nodo; la otra (en este caso E) está generalmente dentro de la misma caja del nodo. Podemos tener tantos nodos en un loop o cadena como queramos. En la figura, el enlace A-XYZ ha sido dibujado como un enlace de inferencia débil, como ya sabemos podemos hacer con los enlaces fuertes. El resultado es un ciclo X continuo en 3. esto nos permite eliminar el 3 de la celda amarilla (regla número 1 de Nice Loops).

La próxima semana les mostraré algunos ejemplos con sudokus reales. Les dejo, para que se entretengan, un sudoku aparecido en uno de los foros de internet, en el que se puede practicar ciclos X.

También puede resolverse con técnicas más simples: 2 pointing pairs, 1 gemela, 1 trilliza y 1 rectángulo vacío.

Que lo pasen bien.

Ejemplos de Ciclos X - (2)

Encontré rápidamente otro ejemplo de Ciclo X, y se los dejo de inmediato, porque es muy instructivo. He marcado como siempre, los enlaces fuertes en línea continua y el débil en línea segmentada.

Tal como está no podemos hacer deducciones. Sin embargo, la semana pasada les mostré que es posible convertir las inferencias fuertes en inferencias débiles. Y aquí lo podemos hacer de dos formas, y en ambos casos podemos descartar algunos candidatos. Veamos el primer caso:

Con la línea segmentada roja muestro el enlace fuerte convertido en inferencia débil. Con esto logro hacer un Nice Loop discontinuo, de dos inferencias fuertes adyacentes en la celda rosada. La regla 2 de Nice Loops indica que en la celda rosada el candidato verdadero es el 7, en consecuencia podemos borrar el 5 de la celda rosada. Y como está determinado el 7 en esa caja, podemos borrar todos los demás 7 que hayan en esa caja, en este caso el que se encuentra en la celda amarilla. En este caso, esta celda toma el valor 5.

Veamos ahora el segundo caso:

Al igual que en el primer caso, muestro con la línea segmentada roja el enlace fuerte convertido en inferencia débil. Con esto logro hacer otro Nice Loop discontinuo, de dos inferencias fuertes adyacentes en la celda rosada. Conforme a la Regla 2 de Nice Loops, la celda rosada debe tomar el valor 7, y en consecuencia podemos borrar el 4 de esta celda. De igual modo, como ya está determinado el 7 en esta caja, ya podemos borrar también el 7 de todas las otras celdas en que se encuentre en esta caja, en este caso las celdas amarillas. El sudoku nos queda entonces de una manera bastante fácil de seguir avanzando:

Lo notable de todo esto, es que aplicando la técnica COLORES, podemos llegar a las mismas conclusiones:

La caja superior derecha queda con dos celdas azules (lo mismo la segunda fila). Eso significa que las celdas azules no pueden tomar el valor 7, luego las rojas son las que toman el valor 7. En consecuencia se pueden borrar los 7 de las celdas azules, y por extensión, también en las amarillas. Llegamos así a la misma conclusión que habíamos llegado por el análisis de los ciclos X. Encontré tan bueno el ejemplo, que no seguiré buscando otros por el momento. Me concentraré en cómo explicar los Ciclos X Agrupados, que es la siguiente técnica que les mostraré.

Ejemplos de Ciclos X

Les dejo un ejemplo de Ciclo X. Tengo el propósito de darles más ejemplos, así es que los iré colocando en los próximos días, pues he estado un poco corto de tiempo para el sudoku en la última semana. El de hoy es un tipo clásico de Turbot Fish; configuración de cinco lados, del cual les hablaba la semana pasada. Aplicando la Regla 2 de Nice Loops, se puede deducir que la celda amarilla debe tomar el valor 9.

Que lo pasen bien.

Enlaces fuertes pueden ser inferencias débiles.

Hasta aquí hemos ocupado sólo el concepto de enlaces con inferencias fuertes y débiles, cuando existen respectivamente enlaces fuertes y débiles. Ya sabemos que los enlaces tienen que ver con el número de veces que un candidato se repite en un grupo (fila, columna o caja): cuando se repite sólo dos veces hablamos de enlace fuerte; cuando el candidato se repite más de dos veces hablamos de enlace débil. En un enlace fuerte, se definió una inferencia fuerte del modo siguiente:

• si no A, entonces B; que significa que en dicho grupo, cuando el candidato no es verdadero en A, entonces es verdadero en B.

Y en un enlace débil, se definió una inferencia débil del modo siguiente:

• si A, entonces no B, no C, no D, etc; que significa que en dicho grupo, cuando el candidato es verdadero en A, entonces ya no lo es ni en B, ni en C ni en D, ni en ninguna otra casilla en que se repita el candidato en dicho grupo.

De estas definiciones es fácil darse cuenta que en un enlace fuerte también es verdadero que:

• si A, entonces no B; que significa que en dicho grupo, cuando el candidato es verdadero en A, entonces no es verdadero en B. Lo cual significa que un enlace fuerte puede ser convertido en una inferencia débil.

Este es un recurso muy útil para obtener cadenas de ciclos alternos, necesarias para aplicar las reglas de Nice Loops, cuando en un loop en que hay enlaces fuertes, éstos no se pueden alternar. Como sabemos ahora que los enlaces fuertes pueden ser inferencias débiles, y en los loops lo que importa son la alternancia de inferencias fuertes y débiles, es posible encontrar entonces loops donde no existen los suficientes enlaces débiles.

Veamos como ejemplo una formación de candidato que los expertos han llamado Turbot Fish, que es una formación de 5 lados como en la figura siguiente:

Esta formación nunca puede tener cinco inferencias fuertes, porque entraría en contradicción. Dados cuatro inferencias fuertes, podemos decir que si la solución está en A, también debe estar en C, y en consecuencia también en E. A y E están en la misma caja, lo cual significa que la solución es ilegal. Por lo tanto, los números deben estar en B y D.

Para eliminar C usando la lógica de los ciclos X, simplemente asumimos que los enlaces fuertes BC y CD son inferencias débiles, y aplicamos la regla 3 de Nice Loops.

Para establecer B como solución, ocupamos la regla 2 de Nice Loops, dejando como inferencia débil el enlace fuerte CD. Como quedan adyacentes las inferencias fuertes AB y BC, entonces B debe ser verdad.

Para establecer D como solución, ocupamos la regla 2 de Nice Loops, dejando como inferencia débil el enlace fuerte BC. Como quedan adyacentes las inferecnias fuertes CD y DE, entonces D debe ser verdad.

No es necesario ir por todos estos pasos para hacer las eliminaciones. El propósito de esta demostración es mostrar que la lógica descrita funciona en todos los puntos de la cadena. Las próxima semana les mostraré algunos ejemplos con sudokus reales.

Pásenlo bien.

Sudokus

Este fin de semana haré un recreo en la descripción de técnicas para resolver sudokus avanzados, pero a cambio les dejo unos sudokus medianamente difíciles para que se entretengan. Pásenlo bien.

Nice Loop - Regla 3.

La tercera regla indica qué pasa cuando dos inferencias débiles son los que forman la discontinuidad del loop. Si los enlaces adyacentes son enlaces con inferencia débil (línea discontinua), se puede eliminar un candidato de la celda en que ocurre la discontinuidad. El siguiente ejemplo fue propuesto por Andrew Stuart:

La discontinuidad está marcada con el círculo rojo, y está basada en dos enlaces débiles adyacentes en el loop. Podemos eliminar con absoluta seguridad el 8 de este nodo. Podría parecer no muy significativa una sola eliminación, considerando el poder de las dos reglas anteriores, pero este tipo de configuración de Nice Loop -de dos inferencias débiles adyacentes- es la más común.

Les dejo como ejercicio un sudoku, también creado por Andrew Stuart:

Que lo pasen bien.

Nice Loop - Regla 2.

Hoy voy a mostrar la regla que se aplica cuando estamos en presencia de dos inferencias fuertes adyacentes. Si las inferencias adyacentes son fuertes (líneas continuas), se puede decidir un candidato en la celda de la discontinuidad. Esta regla nos permite conocer la solución de una cierta celda absolutamente, sin importar cuantos otros candidatos puedan existir en esa celda. A diferencia del caso de la primera regla, no estamos mirando una masa de eliminaciones fuera del loop; a cambio, esta regla nos dice algo del loop en sí mismo. Veamos la lógica de esta regla.

Veamos en la figura anterior el enlace fuerte marcado en azul. Ese enlace significa que en la segunda fila, si uno de esos dos 7 no es, entonces es el otro. O sea, uno de los dos vale 7. Si vale 7 el que está en la segunda fila segunda columna, entonces no es siete el que está en la fila octava segunda columna y en consecuencia (a causa del enlace fuerte de la octava fila) debe valer 7 el que está en la octava fila novena columna (la celda de la discontinuidad del loop). Si, por el contrario, vale 7 el que está en la segunda fila séptima columna, entonces no es 7 el que está en la tercera fila novena columna y en consecuencia (a causa del enlace fuerte de la novena columna) debe valer 7 el que está en la octava fila novena columna (la celda de la discontinuidad del loop). Es decir, que para cualquiera sea el 7 verdadero del enlace fuerte de la segunda fila (en azul), en ambos casos, la celda de la discontinuidad del loop debe tomar el valor 7. Con lo cual se comprueba la regla.

En el siguiente ejercicio es posible deducir el valor de la celda amarilla.

Pásenlo bien.