Sudoku es fácil de entender: un cuadrado 9x9 de 81 celdas, donde cada fila, columna, y 3x3 cuadrado deben contener los dígitos 1 por 9. Bastante sencillo, pero con posibilidades inmensas. Si uno escribiera un programito para generar todos los cuadrados 9x9 con todas las posibilidades posibles de 9 dígitos en cada una de las 81 celdas, tendría que generar 9^81 (9 elevado a 81) cuadrículas (es un número con 78 dígitos). De hecho, escribí tal programa sencillo hace más de 15 años. Pero para completar la tarea dentro de mi vida, incluso en una potente máquina de 5 gHz generando, muy generosamente, una cuadrícula por cada 10 ticks del procesador o 500 millones de cuadrículas por segundo, el programa tendría que haber empezado a andar hace un número de 62 dígitos años. Creo que eso fue mucho antes de que Dios creó la Tierra.

Bien, hay considerablemente menos de 9^81 cuadrículas de Sudoku válidas. Mi programa no necesita probar todos los 9 dígitos para todas las 81 celdas. Si yo haga un poco más compleja la lógica, podría generar sólo Sudokus válidos sin malgastar tiempo del procesador en los inválidos. Mirando, por ejemplo, la primera fila: hay 9^9 o 387,420,489 combinaciones posibles de dígitos 1 - 9 para las 9 celdas. Pero sólo hay 9! (nueve factorial), o 362,880 combinaciones de 9 dígitos donde cada dígito occure exactamente una vez (una fila de Sudoku válida). Así, por ejemplo, para una celda determinada en la fila, si ya hubiera un 2, 3, 5 y 8 en otras celdas en la misma fila, mi programa solo necesitaría probar los dígitos restantes 1, 4, 6, 7 y 9. Por lo tanto, podría resolver la fila en una fracción de repeticiones de procesamiento, o ciclos, o bucles.

Un poco más complejo aplicar esto a la cuadrícula entera, porque cada celda en la cuadrícula 9x9 es miembro de exactamente 3 grupos de 9 celdas: una fila, una columna, y un cuadrado 3x3. La lógica mejorada tendría que tener esto en cuenta. Así lo hice pasando al lenguaje ensemblador y empleando operaciones de los bits AND, OR, y XOR para hacer que la selección de dígitos válidos sea más inteligente y eficiente para cada celda, en relación con cada uno de los 3 grupos a los que pertenece esa celda. Además, el orden en el que mi programa miraba cada celda no necesitaba ser un escaneo fila por fila. Me decidí por esta orden: [a1-a9, b1-b3, c1-c3, b4-b9, c4-c9, d1-i1, d2-i2, d3-i3, d4-d9, e4-e9, f4-f9, g4-g9, h4-h9, i4-i9] como una forma de optimizar la formación inteligente de grupos válidos con un mínimo de bucles.

Además, para cualquier Sudoku válido dado, existen muchas derivaciones que pueden parecer diferentes, pero lógicamente son el mismo Sudoku. Por ejemplo, podría intercambiar las primeras dos filas, colocando la segunda fila encima, y la primera abajo. Cada fila retiene su propio contenido y validez. También, cada columna en el Sudoku retiene su propia validez, ya que ningún dígito se ha movido de una columna a otra. Asimismo, cada cuadrado 3x3 sigue siendo válido. Podría hacer el mismo con la segunda y tercera filas. De hecho, hay 6 ordenes distintos en que se pueden disponer las primeras 3 filas sin alterar ni la validez ni la uniquez del Sudoku. Note que no podría intercambiar una de las primeras 3 filas con una de las 6 filas abajo, ya que conllevaría la transferencia de celdas entre diferentes cuadrados 3x3, alterando sus contenido y validez. Pero podría intercambiar filas 4 por 6 en seis ordenes, y también filas 7 por 9, resultando en 6 x 6 x 6 = 216 ordenes en que se pueden disponer las 9 filas sin alterar ni la validez ni la uniquez del Sudoku. Del mismo modo, podría intercambiar cualquier dos hileras, o grupos de 3 filas. Ya que hay seis ordenes en que se pueden disponer las 3 hileras, ya tenemos 216 x 6 = 1,296 ordenes de filas y hileras que son todos lógicamente el mismo Sudoku. Para cualquier de estos 1,296 ordenes, también se pueden intercambiar columnas y grupos de 3 columnas. Entonces se puede rotar 90° la entera cuadrícula 9x9 para tener una nueva apariencia que es todavía el mismo Sudoku. (Note que rotar 180° la cuadrícula 9x9 nos daría exactamente la misma cuadrícula de una de las variaciones de las filas y columnas, y por eso no será un nuevo arreglo. De manera similar, rotarla 270° sería igual de rotarla 90° junto con una de las variaciones de las filas y columnas.) Finalmente, se pueden intercambiar los nueve dígitos uno con otro, por ejemplo cambiando cada '1' en el Sudoku a un '4', cada '8' a un '3', etc. Hay 9! (nueve factorial) o 362,880 caminos en que se pueden intercambiar los nueve dígitos 1 por 9. Sumando todo esto, hay 1,296 x 1,296 x 2 x 362,880 = 1,218,998,108,160 caminos de arreglar cualquier Sudoku válido dado para aparecer diferente mientras quedando lógicamente el mismo. Esto es principalmente de acuerdo con los matemáticos de Technology Review, que han empleado sus computadoras para determinar que hay 6,670,903,752,021,072,936,960 cuadrículas válidos de sudoku pero sólo 5,472,730,538 Sudokus únicos.

Junto con unos otros mejoras, después de unas semanas mi programa era un poco más complejo mas mucho más eficiente. Estaba generando casi un millon de Sudokus válidos por segundo en mi vieja máquina de 500 mHz. Todavía generaba unas derivaciones duplicadas, pero ya era bastante rápido para generar todos los Sudokus posibles en dos o tres semanas de andar sin pararse. Que importa más, esta misma lógica mejorada podía operar en una cuadrícula con unas celdas vacías, es decir, un rompecabezas Sudoku. Como notado en el artículo previo, un Sudoku con 60 o menos celdas vacías se analiza exponencialmente más rapido.

Pero, esto introduce una capa nueva de complejidad, en que para cada Sudoku completo, existen una gran cantidad de cuadrículas parcialmente completas, compuesto de celdas rellenas y vacías. Algunas de estas cuadrículas parcialmente completas pueden ser verdaderos rompecabezas Sudoku de una sola solución, que se pueden resolver a un Sudoku completo único. Otros pueden pertenecer a más de uno Sudoku completo, es decir, pueden tener varias soluciones. Aún otros pueden tener ningúna solución; no se puede rellener las celdas vacías para obtener un Sudoku completo válido.

Limitandonos a la primera categoría: para cualquier Sudoku de una sola solución, pueden existir muchísimos caminos para resolverlo. En cualquier paso en la vía, se podría resolver muchas celdas diferentes, usando una variedad de estrategias. Resuelva una de esas celdas, y ahora tiene un rompecabezas diferente, probablemente más fácil a resolver. Resuelva una celda diferente, y ahora tiene un rompecabezas un poco diferente, tal vez no más fácil, sino ¡más difícil a resolver!

No sé calcular esta complejidad adicional: cuántas cuadrículas incompletas existen, cuántas de estas son Sudokus de una sola solución, y cuántos caminos diferentes hay para resolverlos. Sospecho que la cantidad total sea una magnitud similar o mayor como en el primer párrafo arriba, casi imposible de computar exhaustivamente todas las posibilidades.

Muy bien. Usted puede preguntar por qué un carca jubilado gastaría tanto tiempo persiguiendo tal meta no alcanzable. Pues, estoy contento de haber desarollado mi programa al punto donde según parece puede analizar, si no todas, por lo menos casi todas de la gran cantidad de posibilidades mencionado arriba. Me repito: si usted no está de acuerdo con mi jactancia, o si encuentre un problema, o si encuentre otro analizador que realice como mi Analizador de Sudoku, favor de informarme.

Cuando se hace clic en los botones 'Analizar', 'Sugerencia', 'Vistazo', o 'Resolver', el Analizador de Sudoku envia un paquetito de Ajax al servidor. La 'X' en A.J.A.X. en este caso significa 'executable' (ejecutable), un programa que anda en el servidor de hospedaje de cyberjerry.info como nativo ejecutable o binario de BSD. El binario ejecuta la tarea pedido y devuelve a su computadora otro paquetito, para acabar el trámite de Ajax. Este programa se escrito en C y ensamblaje, compilado en el servidor usando gcc, para ejecución muy rápido. (El análisis de Sudoku correría muy despacio en un lenguaje de escritura.) El parte original y central del programa, escrito en el código ensamblaje, resuelve el Sudoku por instrucciones simples y rápidas de AND, OR, y XOR en bucles repetitivos y apretados. Su mandado es resolver la cuadrícula del Sudoku, o agotar todas las posibilidades en tratar de resolverlo. Al encontrar una solución, sigue en bucles repetitivos buscando más soluciones. Así puede informar el programa de C si la cuadrícula tiene una solución, varias soluciones, o ninguna. Su tarea secundaria es construir la tabla empleada en hacer la Cuadrícula de eliminación.

Este módulo de ensamblaje sencillo mas eficaz podía (casi siempre) hacer su tarea bien rápido. Dado una cuadrícula vacía o casi vacía, aún el programa más rápido gastaría mucho tiempo en intentar todas las posibilidades, pero podría seguir en generar muchas soluciones (tanto como un millón o más por segundo) hasta que el programa de C dice "¡Basta!". Dado una cuadrícula con varias celdas ya rellenas, y por lo tanto menos celdas a resolver, podía agotar todas las posibilidades en exponencialmente menos tiempo. Donde gastaría varios días para generar todas las soluciones para una cuadrícula vacía, podría hacerlo en dos segundos - menos que un segundo en el servidor rápido - para una cuadrícula con 60 o menos celdas vacías. Entonces podía informar el programa de C definitivamente que la cuadrícula tiene una solución, varias soluciones, o ninguna. Entonces el programa de C podía usar esta información para empezar a analizar la cuadrícula y, en el caso de un Sudoku de una sola solución, podía ayudar el operador humano con paso a paso sugerencias. Así se nació el Analizador de Sudoku.

El campo mediano era un poco problemático, donde la cuadrícula tenía entre 8 y 20 celdas rellenas. Depende de su configuración, las 8 a 20 celdas podrían en unos casos prevenir el módulo de ensamblaje de generar soluciones rápidamente. Al mismo tiempo, tantas celdas vacías significaría que el código de ensamblaje haría exponencialmente más bucles repetitivos en tratar de agotar todas las posibilidades, y el servidor probablemente mataría el programa por gastar mucho tiempo. Ninguna de las cuadrículas problemáticas eran válidos Sudokus de una sola solución; o tenía no solución o varias soluciones. O, yo pensaba así. Por eso, hace pocos años, para evitar el error del servidor, añadí un contador de bucles, diciendo el código de ensamblaje parar si no encuentre una solución después de 120 millones de bucles, y el programa de C diría al operador que la cuadrícula "no tiene solución o demasiadas para analizar."

Este código de ensamblaje ya ha sido al centro de mi atención por varias semanas. Escrito hace más o menos 15 años, era el primer parte de lo que con tiempo llegó a ser el Analizador de Sudoku. En el interín, yo seguía mejorar y corregir problemas en la página interactiva y en la lógica de análisis y sugerencia, pero el módulo de ensamblaje se quedía mayormente sin cambio. Entonces, como notado en el artículo de blog previo, Señor Manuel Navarro De La Hoz de Colombia me mandó una cosa que yo nunca hube encontrado: un Sudoku de una sola solución con solamente 17 celdas rellenas. Por las razones ya mencionadas arriba, mi módulo de ensamblaje no pudo resolverlo ni agotar todas las posibilidades entre los límites de bucles. Supe lo que tuve que hacer: tuve que volver al comienzo y hacer más inteligente y más rápido el código central de ensamblaje.

El código nuevo es más complejo y más analítico que el viejo. En lugar de tratar de resolver cada cuadrícula en la misma manera sencilla, ya examina la cuadrícula para ordenar sus celdas vacías según sus dígitos posibles. De manera similar, más que siempre tratar los dígitos 1 por 9 por orden numérico, los pone por un orden más probable a dar rápidamente resultas válidas. Por último, al probar la nueva lógica, fue obvio que agrandar el límite más de pocos millones de bucles logra casi nada. Por eso, mi nueva lógica trata de cumplir su trabajo en menos de 8 millones de bucles. Si falla, podría intentar otra vez con otro orden de dígitos y celdas, entonces otro orden, y otro. Ahora, en 99.77% de los casos, hace todo con menos de 20,000 bucles, y debe nunca hacer más de 20 millones de bucles, incluso en el peor de los casos, así el servidor no debe quejarse que está consumiendo demasiado tiempo del processor.

Desde lo anterior consiste en cambios radicales a la rutina central de ensamblaje, señala nueva publicación mayor del Analizador de Sudoku, la versión número 3.0.000. En esta misma publicación, hay otros pocos cambios menores del parte del binario escrito en C y de la interfaz al lado del cliente. Un nuevo rasgo que puede observar es que, arriba de la cuadrícula de eliminación, ya puede hacer clic en 'Estads' para ver cuantos bucles y cuanto tiempo usa el binario cada vez está llamado. El tiempo total de Ajax está allí para referencia; los nuevos cambios afectan solamente la velocidad y eficiencia del binario al lado del servidor. No tengo control sobre el proceso Ajax, que depende en la velocidad de su conexión y de todos los servidores que pasan el paquetito de Ajax de acá para allá entre su computadora y el servidor de cyberjerry.info.

Bueno, reconozco con agradecimiento la inteligencia de Señor Navarro, y su respuesta exitosa de mi Reto, pero de ninguna manera estoy renunciando la declaración que mi Analizador de Sudoku es lo mejor del internet. Ya era lo mejor, y ahora, gracias a Señor Navarro, es aún mejor. El sitio donde él encontró el Sudoku que dejó (temporalmente) perplejo mi Analizador de Sudoku fue nada más que una colección de Sudokus y sus soluciones predeterminados. No ayuda ni sugerencias paso a paso, ni análisis, nada.

Mientras estoy escribiendo este artículo, también estoy andando un programa en mi computadora del hogar para generar Sudokus de varias configuraciones de celdas rellenas y vacías, para seguir probando mi nueva lógica. En este momento, este programa ha generado más o menos 90 millones de cuadrículas; la nueva lógica está analizando toditos sin fallar, y sin gastar mucho tiempo. No digo que el Analizador de Sudoku ya está sin defectos, ni que 3.0.000 será su versión final. Pero, si usted encuentre un problema, o si nunca encuentre otro analizador que realice como mi Analizador de Sudoku, ¡favor de informarme!

Hace pocos días, un visitante* astuto a mi página de Sudoku respondió exitosamente al Reto de Sudoku, el primero visitante de hacerlo. Halló el Sudoku mostrado que el Analizador no pudo resolver, y me dijo como resolverlo:

este sudoku lo saque de la pagina https://www.sudoku-online.org de categoria sudoku extremo #717, y su analizar dice que no tiene una solución, sin embargo por metodo analitico encuentro que F6 = 4 debido al 4 de E3 y el 4 de G5, tambien encuentro que I9 = 5 debido al 5 de D8 y al 5 de H4, al colocar estos dos números, ahora si dice que tiene solución única lo anterior esta pasando por que

Lo he confirmado: Alguien ha contestado con buen éxito el gran Reto de Sudoku. Es decir, un visitante ha resuelto paso a paso un Sudoku que el CyberJerry Analizador de Sudoku (el 'Analizador') no podía analizar. Espero publicar más detalles pronto.

Ya que está más y más difícil a encontrar cuadrículas de Sudoku que el CyberJerry Analizador de Sudoku (el 'Analizador') no puede analizar paso a paso, el gran Reto de Sudoku también llega a ser más difícil. Para ayudarle un poco, abajo están cuatro cuadrículas de Sudoku que el Analizador no puede analizar paso a paso. Solamente tiene que resolver uno de estos deductivamente (sin adivinaciones) para clasificarse como retador exitoso. Haga clic en cualquier cuadrícula abajo para verla en el Analizador. Ambos el y usted deben poder a resolver varias celdas. Pero, después de unos pasos, el Analizador ya (leer artículo)

Varios recientes mejoramientos y arreglos pequeños en el Analizador de Sudoku de CyberJerry lo hacen capaz de analizar Sudokus más y más avanzados. Dos resultas: el control "Nuevo" ya ofrece rompecabezas del nivel "Experto", y el botón "Sugerencia" puede ofrecer unos sugerencias muy complejos, con varios sub-pasos de una variedad de estrategias avanzadas. Concentrando en Sudokus avanzados ha producido otro resulta, imprevisto: la posibilidad de encontrar el "Rectángulo Evitable Inevitable". (No pude hallar este fenómeno en ningún otro sitio, por eso clamo el (leer artículo)

Este artículo sirve como otro informe de error y como otro aviso del Reto de Sudoku .

Esta vez, el Analizador de Sudoku no puede resolver el Sudoku paso a paso. Debe poder. Es un bug, recien encontrado, que estoy estudiando, y que espero corregir pronto.

Mientras tanto, si usted puede resolver este Sudoku de una forma deductiva (sin adivinanzas), aquí es otra oportunidad (leer artículo)