De vuelta a los sudokus

Advertencia previa: Este post, coda del publicado el pasado 31 de octubre, es todavía más aburrido que aquél. Pero es una deuda de gratitud que cumplo con Números quien, imagino, será el único que lo lea.

En un comentario a mi post del pasado sábado (sí, ése que era un tostón de cifras), Números aportó la solución a la primera de mis preguntas. La solución es 6.670.903.752.021.072.936.960 (o sea, más de 6.670 trillones) de sudokus completos distintos y esta cifra es el resultado de un producto un poco esotérico (9! x 72˄2 x 2˄7 x 27.704.267.971). Claro que, como le dije, ese dato no me explicaba demasiado, así que Números, muy gentilmente, me hizo llegar dos artículos de sendas revistas en las que es explicaba el procedimiento por el cuál se había llegado a la solución. Haré un brevísimo resumen del mismo y a continuación anotaré algunas reflexiones al respecto.

El razonamiento se basa en calcular sucesivamente las combinaciones válidas de las cajas (cuadrados de 3x3 con las nueve cifras). Empezando por la caja del ángulo superior izquierdo, es fácil ver que el número de combinaciones equivale a las permutaciones de nueve elementos (9!). A cada una de las 362.880 posibles primeras cajas ya no le corresponden otras tantas segundas (la situada arriba en el centro); combinando primero todas las formas posibles de disponer las filas (sin importar el orden de las tres cifras) de la segunda caja para que no repitan cifras de las filas correspondientes de la primera, se comprueba enseguida que hay 56 opciones de colocar las cifras sin atender a su orden horizontal. En cada una de esas 56 posibilidades se pueden permutar las tres cifras de cada fila. Como cada fila da 3! permutaciones (6), hay 6˄3 combinaciones para cada una de las 56 opciones; o sea, 12.096 posibles segundas cajas para cada una de las 362.880 primeras. A continuación se pasa a la tercera caja (la del ángulo superior derecha) cuyas posibilidades son muchas menos y más sencillas de ver. Dada cualquier combinación de las dos primeras cajas, las filas correspondientes de la tercera son obligadas, con lo cual sólo se trata de permutar las tres cifras de cada una de ellas y hacer el producto. Resulta pues que hay 216 (3!˄3) terceras cajas por cada una de las 4.389.396.480 combinaciones posibles de cajas 1 y 2. De esta forma, mediante el razonamiento sabemos con certeza que hay 948.109.639.680 distintas combinaciones (casi un billón) de las tres cajas superiores para los sudokus de 9x9.

Y llegados a este punto, según cuenta la revista, se acabó la razón y se pasó a la "fuerza bruta." Fuerza bruta significa poner a los ordenadores a hacer todas las combinaciones posibles para cada una de las tres cajas anteriores. El proceso de cálculo es tan descomunal que parece que no es viable y había que reducirlo a partir de agrupaciones de los posibles sudokus en "clases" (sudokus que son equivalentes a estos efectos). Este asunto fue desarrollado durante 2005 por unos cuantos frikis matemáticos que discutían apasionadamente en un foro de internet y finalmente dos de ellos, Bertram Felgenhauer, un alemán de Dresde, y Frazer Jarvis, un británico de Sheffield, obtuvieron la solución final.

Hasta aquí un resumen del artículo de Juan MR Parrondo en la revista Investigación y Ciencia de diciembre de 2005. Lo primero que me llamó la atención es que la explicación sobre cómo calcular el número de combinaciones distintas de las tres primeras cajas no cuadra con el producto "mágico" que es la solución del número total de sudokus completos. El primer factor de la revista (9!) sí es, en efecto, el total de primeras cajas, pero el segundo (72˄2) y el tercero (2˄7) no coinciden con los respectivos de las siguientes cajas según el método descrito (216 y 6˄2). Como tampoco los productos son iguales (663.352 y 12.096), hay que concluir que el último factor (27.704.267.971) tampoco es el número de combinaciones válidas de las seis últimas cajas. Lo curioso es que Parrondo dice que cada uno de los tres primeros factores "puede explicarse razonablemente, salvo el último de ellos, un número primo de tamaño considerable obtenido por Felgenhauer el 23 de mayo de 2005 tras seis horas de computación en dos ordenadores personales"; y como inmediatamente cuenta lo que he resumido, el lector supone que que los tres primeros factores corresponderían a los resultados de las sucesivas tres primeras cajas del sudoku y el último al de las restantes (al obtenido tras proceso de computación) y no es así. No digo que la solución esté mal, pero sí que la explicación, muy didáctica, no está del todo lograda.

El número total de sudokus completos, además, no es divisible por el número total de combinaciones distintas de las tres primeras cajas, lo cual quiere decir que cada una de estas combinaciones distintas no se repite el mismo número de veces en el catálogo de sudokus posibles. Eso implica que no todas las combinaciones de las tres cajas superiores son compatibles con todas las combinaciones de las seis inferiores o, dicho de otra forma, que si juntamos cada combinación válida de las tres cajas de arriba con cada combinación válida de las seis de abajo obtendremos unos cuantos sudokus incorrectos (con cifras repetidas en alguna columna). Este hecho "estropea" algo más la explicación que aparece en la revista.

Tras leer el artículo se me vino la ocurrencia obvia de que por el mismo método se podría calcular el número total de combinaciones válidas no sólo de las tres primeras cajas, sino también con la cuarta y séptima (completando las cinco cajas que forman los bordes superior e izquierdo). Nótese que estas dos cajas sólo dependen de la primera, así que debe haber el mismo número de combinaciones para la cuarta que de para segunda (12.096) y el mismo número para la séptima que para la tercera (216). De esta forma, la cifra derivada del razonamiento (sin fuerza bruta) subiría de 948.109.639.680 hasta casi dos millones y medio de trillones. Ciertamente, no todas estas combinaciones de las cinco cajas son compatibles con todas las combinaciones de las cuatro restantes y hasta podría ser, conjeturo, que alguna de las primeras no tenga ninguna combinación válida entre las segundas. Pero, puestos a explicar un método que no cuadra con la fórmula, también podría el autor haber dado a entender que el proceso de computación se aplicó "sólo" a cuatro cajas restantes, en vez de a seis.

La segunda reflexión que me vino a la cabeza es que es una pena que la solución no derive de un proceso deductivo y haya que haber recurrido a la "fuerza bruta". Me gusta cómo se razona el número posible de tres (o cinco) primeras cajas y me habría encantado que, con similares armas, se hubiera llegado hasta el final. Poner al ordenador a hacer combinaciones para las seis cajas inferiores me parece una rendición intelectual y, desde luego, muy poco elegante. Digamos que aunque el ordenador nos pueda dar la solución, no nos descubre el "secreto", no nos informa de la lógica que subyace en la generación de sudokus válidos. Por eso, estamos muy lejos todavía de poder determinar, como ingenuamente me planteaba en mi post anterior, el número de sudokus válidos para cualquier rejilla de nxn celdas.

En tercer lugar, me hizo sonreír (una vez más) el comprobar que cualquier duda que a uno se le ocurra ya se le ha ocurrido antes a muchísimas más personas y que cualquier tanteo de solución que uno haya pensado ha sido más que dado la vuelta y ampliado por otras tantas. Me considero bien servido de curiosidad pero hay muchos otros que tienen tanta o más que yo y, desde luego, bastante más tenacidad y conocimientos (amén de medios). Pretender ser originales, aparte de ser un mal enfoque, está condenado al fracaso.

También me ha admirado el empleo de internet en esta aventura colectiva de indagación intelectual. He pasado algunos ratos ojeando los debates en distintos "forums" sobre el tema y, aunque muchas veces me pierdo, llama la atención el grado de entusiasmo y colaboración de los participantes. Todo para calcular el número de soluciones de un simple juego, algo que parecería irrelevante. No lo es, sin embargo, porque refleja una de las potencias más nobles de nuestra especie, la de enfrentarse a los retos intelectuales, la de buscar respuestas que hagan inteligible la realidad. Esa constante del ser humano (en la que la curiosidad es factor imprescindible) encuentra hoy en internet un instrumento valiosísimo para fomentar la colaboración. Frente a tantas otras "cualidades" nuestras que no son precisamente loables y en las que siempre tendemos a fijarnos, alegra ver que el espíritu de colaboración y la curiosidad intelectual siguen vigentes. No siempre hemos de fustigarnos con críticas pesimistas.

Por último, la lectura de estas revistas me ha permitido ver mi duda inicial en un marco mucho más general, atisbar al menos otros temas relacionados que, si tuviera tiempo, son un terreno feracísimo para el entretenimiento intelectual. También (y con esto ya acabo) para comprobar que hay muchas dudas aún no resueltas y, entre ellas, la que motivó mi post: ¿cuántos sudokus hay? Me refería a cuántos sudokus incompletos válidos, con una única solución, podían plantearse. Evidentemente, tienen que ser muchos más que los 6.670.903.752.021.072.936.960 sudokus completos posibles, pero no he encontrado, ni en las revistas ni en las webs consultadas, ya no la solución (que seguro que no se sabe) sino ni siquiera la enunciación del problema. Al fin y al cabo, ello no es más que una muestra de otra constante de la inquietud intelectual humana: cada duda que se resuelve genera nuevas dudas a resolver. Como ya dije en un antiguo post, cuesta entender que podamos aburrirnos.

CATEGORÍA: Curiosidades dispersas