Jerry's Blog  1.4.310
mi propio
Defecto compuesto
Error vergonzoso de larga data está corregido
sab 27 noviembre 2021  9:14pmSudoku

La cosa vergonzosa es que este defecto existía para más de un año, y acabo de encontrarlo y corregirlo. Desde Octubre de 2020, si uno navege al Analizador de Sudoku, y toque el botón 'Nuevo' o 'Usar Libro', el intérprete de javascript de su navegador se queja que la variable 'StartTime' no existe, o simplemente se para sin cargar un nuevo rompecabezas.

Este defecto ya está compuesto. Lamento la confusión y la pérdida de visitantes que ha causado.

 
Oda a Sudoku
Relato del desarollo del Analizador de Sudoku
mar 24 noviembre 2020  1:55pmSudoku

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.

  0 comentarios
rev. 24 nov 2020  8:15pm
 
Versión 3
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, (leer artículo)

 
El Retador Exitoso
El primer respuesto exitoso al Reto de Sudoku
dom 23 agosto 2020  10:06amSudoku

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
(leer artículo)

  3 comentarios
rev. 29 ago 2020  8:30am
 
Reto Respondido (2)
El primero respuesto exitoso al Reto de Sudoku
mie 19 agosto 2020  7:34pmSudoku

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.

 
4 Retos de Sudoku
Para vencer, resolver uno
lun 6 julio 2020  12:42pmSudoku

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)

  0 comentarios
rev. 17 jul 2020  7:56pm
 
Rectángulo Inevitable
Cuando la técnica Rectángulo Único está inevitable
vie 19 junio 2020  9:29pmSudoku

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)

  0 comentarios
rev. 25 jun 2020  7:43pm
Nunca te van a cambiar por algo mejor, sólo por algo más fácil

Artículos
Todos  
Fe/Filosofía
Sudoku
Computadora
Misc.
Copyright (c) 2017-2022 Gerald DePyper - Jinotega, Nicaragua, C.A.
rev. 2022.01.26