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.
| rev. 24 nov 2020 8:01pm |
0 comentarios:
