Publicado versión 3.0 del Analizador de Sudoku
mie 7 octubre 2020 2:26pmSudoku
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!
0 comentarios:
