¿Cuántos sudokus hay?

Al poco de popularizarse los sudokus me aficioné a ellos y, a la fecha, he adquirido bastante destreza resolviéndolos. Un amigo, viendo que dedicaba cualquier rato muerto a este pasatiempo, me dijo que pareciera que quería hacer todos los sudokus existentes. Es obvio que esa tarea es inalcanzable y además, aunque lo fuera, uno ni se daría cuenta. Al ser sólo combinaciones de cifras, se puede hacer varias veces el mismo sudoku sin percatarse de la repetición. Pero me intrigó el enigma que titula este post. Porque, evidentemente, hay un número finito de sudokus y dicho número tiene que poder ser calculable. ¿Cómo?

En el sudoku canónico (un cuadrado de 9x9 dividido en nueve "cajas" de 3x3) se usan todos los dígitos a excepción del cero y, una vez resuelto, cada uno de ellos aparece nueve veces. El sudoku más sencillo sería el que solo usa las cuatro primeras cifras, conformado por cuatro cajas de 2x2. Los sudokus "normales" (los que son cuadrados) crecen exponencialmente en tamaño. En términos generales, un sudoku en el que se juegue con n cifras (n tiene que ser el cuadrado de un número natural) tendría n2 casillas, n filas, n columnas y n cajas. En el sudoku canónico, si nos quedamos con una cualquiera de las cajas (o, si se prefiere, una única fila o una única columna del cuadrado completo) es evidente que el número total de "soluciones" distintas es el total de permutaciones de las nueve cifras; o sea, 9! que es 362.880. Como la cantidad es muy grande, vayamos al sudoku n=4. Obviamente, existen 4! (24) posibles cajas; las siguientes:

Identificando con un código cada una de las cajas posibles, un sudoku de n cifras se puede denominar como una sucesión de n códigos. Por tanto, el número total de sudokus posibles sería todas las combinaciones de las n! cajas tomadas de n en n. En el caso de los sudokus de 9 cifras, se trata de C(362.880, 9) que equivale a 362.879 x 362.878 x 362.877 x 362.876 x 362.875 x 362.874 x 362.873 x 362.872, lo que da la astronómica cifra de más de 300 septillones (3,0065E44). Descendiendo al modestísimo sudoku de cuatro cifras resulta un total de 10.626 combinaciones, cantidad que al menos nos es inteligible.

Claro está que de todas esas combinaciones la inmensa mayoría no son sudokus válidos. Para verlo con facilidad volvamos al sudoku más elemental de 4 cifras con 24 posibles cajas. Tomemos la caja 1 para el ángulo superior izquierdo. En el ángulo superior derecho podríamos colocar, en teoría, cualquiera de las restantes 23 cajas, pero (como se ve en el siguiente dibujo) sólo valen 4 de ellas, las coloreadas de verde. Si ponemos cualquiera de las otras 19 cajas a la derecha de la primera en alguna de las dos filas resultantes (o en las dos) se repiten cifras. Así que de todas las posibles combinaciones cuya primera caja es la 1 sólo son válidas aquellas cuya segunda caja es la 17, la 18, la 23 o la 24.

Si ahora ponemos la tercera caja (la que iría en el ángulo inferior izquierda) es fácil comprobar que, para cada combinación válida de las dos primeras cajas, sólo cumplen cuatro cajas. Así pues, tenemos dieciséis combinaciones válidas de tres cajas (que son las que se muestran en la siguiente figuras agrupadas en columnas por cada una de las cuatro combinaciones válidas de las dos primeras cajas). Como sabe quienquiera que sea aficionado a los sudokus, resueltas (n-1) cajas de un sudoku la restante es única; por tanto, la cuarta caja de nuestro sudoku elemental es sólo una posible. Ahora bien, por la misma razón, esas dieciséis combinaciones posibles de tres cajas (recordemos que la primera de momento es siempre fija) no son todas válidas. En el dibujo siguiente se ve que las cuatro combinaciones centrales no permiten una cuarta caja válida. Nos quedan pues, 12 combinaciones de las cajas superior derecha e inferior izquierda para cada caja superior izquierda. Como hay 24 cajas que podemos poner en el ángulo superior izquierda, es inmediato concluir que existen 288 sudokus de cuatro cifras y no las 10.626 combinaciones posibles si no se tuvieran en cuenta las reglas del juego.

Si ahora ponemos la tercera caja (la que iría en el ángulo inferior izquierda) es fácil comprobar que, para cada combinación válida de las dos primeras cajas, sólo cumplen cuatro cajas. Así pues, tenemos dieciséis combinaciones válidas de tres cajas (que son las que se muestran en la siguiente figuras agrupadas en columnas por cada una de las cuatro combinaciones válidas de las dos primeras cajas). Como sabe quienquiera que sea aficionado a los sudokus, resueltas (n-1) cajas de un sudoku la restante es única; por tanto, la cuarta caja de nuestro sudoku elemental es sólo una posible. Ahora bien, por la misma razón, esas dieciséis combinaciones posibles de tres cajas (recordemos que la primera de momento es siempre fija) no son todas válidas. En el dibujo siguiente se ve que las cuatro combinaciones centrales no permiten una cuarta caja válida. Nos quedan pues, 12 combinaciones de las cajas superior derecha e inferior izquierda para cada caja superior izquierda. Como hay 24 cajas que podemos poner en el ángulo superior izquierda, es inmediato concluir que existen 288 sudokus de cuatro cifras y no las 10.626 combinaciones posibles si no se tuvieran en cuenta las reglas del juego.
Naturalmente, con lo expuesto hasta aquí no he hecho más que tantear el terreno sin avanzar apenas nada en el problema. Sólo he "contado" las combinaciones válidas entre muy pocas posibles pero sin llegar a entender todavía los mecanismos que subyacen en la selección de aquéllas, paso indispensable para poder establecer la fórmula de la que resultara el número de sudokus de n cifras. Como el número de cajas posibles si es conocido (n!) y, en el caso n=4, resultan 12 combinaciones válidas por caja y 12 es (¿casualmente?) 4!/2, podría aventurar que la solución sería n! x n!/2. De ser cierto, habría 65.840.947.200 sudokus canónicos válidos. Pero no es más que una conjetura con escasísima base que intuyo errónea.

Así que seguiré dándole vueltas al asunto en algún otro rato libre. Pero la respuesta que busco no es la que he descrito. Hasta ahora he elucubrado sobre el número total de sudokus posibles completos. Pero un sudoku es un cuadrado de nxn casillas en las que en algunas aparece una cifra y otras están vacías. ¿Cuántos sudokus incompletos existen? Esta es la pregunta que de verdad me intriga. Naturalmente para que cualquiera de esos cuadrados incompletos sea válido ha de cumplir la condición de que en cada una de sus casillas vacías sólo pueda ponerse una de las n cifras disponibles. Es decir, que pueda solucionarse llegando a uno de los sudokus completos válidos y sólo a uno. Está claro que para cada uno de todos los posibles sudokus completos hay un número determinado de sudokus incompletos cuya solución nos lleva a él.

Generar todos los sudokus incompletos posibles de un sudoku dado es, en teoría, bastante sencillo: basta con ir borrando de forma ordenada cifras de las casillas. Así, en un sudoku de cifras (y n2 celdas) generamos primero todos los sudokus incompletos con una casilla en blanco (salen obviamente n2 sudokus cuyas soluciones son evidentes); luego pondremos dos casillas en blanco en todas las combinaciones posibles; después tres, también en todas las combinaciones; y así sucesivamente hasta tener de nuevo n2 sudokus en los que sólo hay una celda con cifra (éstos son irresolubles, claro está). Generalizar esta mecánica en una fórmula también es simple: se trata de la sumatoria de todas las combinaciones de n2 elementos tomadas de k en k, donde k varía desde 0 hasta n2 (están incluyéndose el sudoku completo y el sudoku vacío). Ahora bien, esta sumatoria es igual a 2 elevado a n2 (a lo que habría que restar 2 si no queremos incluir ni el sudoku completo ni el vacío). Así que, para cada sudoku completo de 4 cifras, resulta que hay un total de 65.534 sudokus incompletos (no cuento los dos singulares). Como ya calculé que había 288 sudokus válidos de 4 cifras, en teoría podría haber 18.873.792 sudokus incompletos de 4x4. En el caso del sudoku canónico las cantidades, lógicamente, se nos disparan. Por cada sudoku válido habría 2,417 cuatrillones de sudokus incompletos y, suponiendo que mi anterior conjetura es válida (que seguro que no) tendríamos un total de 159.193,642 quintillones de sudokus incompletos de 9x9.

Por supuesto, las cifras anteriores son erróneas porque muchísimos de esos sudokus incompletos derivados de uno completo se repiten entre los derivados de otro también completo. Justamente los sudokus incompletos repetidos son aquéllos no válidos ya que pueden tener más de una solución; es decir, son derivados de más de un sudoku completo. Nótese que, con el método propuesto, no se pueden generar sudokus sin solución (los que a veces me he encontrado cuando en una casilla no va ninguna de las nueve cifras disponibles) ya que todos derivan de sudokus completos válidos. Por tanto, calculando el número de repeticiones y restándoselo al total de sudokus completos se llegaría a la respuesta de mi enigma. ¿Cómo se calculan las repeticiones? Pues de momento no lo sé y ya es la hora de almorzar.

PS: Supongo que este post bate el record entre los tantos aburridos que he escrito. En consecuencia, quien haya llegado hasta aquí sepa que cuenta con mi rendida admiración.

CATEGORÍA: Curiosidades dispersas