El otro día me estaba aburriendo (como casi siempre) y se me ocurrió una pregunta que a la mayoría de los mortales les parecerá carente de importancia… la verdad es que yo todavía no he conseguido encontrar ningún motivo para considerarla importante, pero la curiosidad (y sobretodo la dificultad de hallar la respuesta) puede más conmigo que la “importancia” de la cuestión.
La pregunta es:
“¿Como se puede calcular la cantidad de n-sudokus que existen?“
Para intentar responder a ésto lo primero que deberíamos hacer es definir el término n-sudoku. Daré una definición informal que nos servirá para nuestros propósitos.
Definición:
Un n-sudoku es una matriz de números naturales cuadrada con n² filas y columnas que cumple las siguientes restricciones:
- Los únicos números válidos van del 1 al n².
- En una fila no se puede repetir ningún número
- En una columna no se puede repetir ningún número
- Si dividimos la matriz en n² submatrices cuadradas disjuntas (sólo hay una forma de hacerlo), en ninguna de ellas se puede repetir ningún número.
Es claro que el 3-sudoku es el sudoku que todo el mundo conoce.
Antes de continuar tengo que aclarar una cosa: No he conseguido ninguna respuesta satisfactoria, parece que para cada número natural n mayor o igual que 2 tenemos que aplicar cálculos especializados en ese caso concreto. Yo por mi parte he hecho el cálculo para el caso más sencillo, el 2-sudoku, que en breve os presento 
.
Lo que haré para calcular la cantidad de 2-sudokus que existen es ir rellenando cada casilla de un 2-sudoku con la cantidad de números que podría poner si ya hubiera puesto los anteriores números, la primera secuencia os resultará familiar, que es la cantidad de formas en que podemos ordenas 4 números sin repetición en 4 posiciones distintas (Aviso, iré rellenando una matriz, pero no lo confundamos con el hecho de ir resolviendo un sudoku, porque no lo estoy haciendo).
| 4 |
3 |
2 |
1 |
| ? |
? |
? |
? |
| ? |
? |
? |
? |
| ? |
? |
? |
? |
Para rellenar la siguiente fila tendremos que hacer algunas observaciones pero sigue siendo muy sencillo:
| 4 |
3 |
2 |
1 |
| 2 |
1 |
2 |
1 |
| ? |
? |
? |
? |
| ? |
? |
? |
? |
El primer 2 viene dado porque ya se han eliminado dos posibilidades en la primera submatriz, el siguiente 1 viene dado porque sólo se puede rellenar de una sola forma la última casilla de la primera submatriz. En los siguientes números también tenemos 2 y 1 pero tenemos que analizarlo con un poco más de cuidado. Podríamos pensar que ese 2 en realidad es un 1 porque tenemos más restricciones que antes (la fila superior, la submatriz y los elementos de la misma fila que hay en la izquierda). El caso es que tenemos suerte, y los elementos que podemos poner en las casillas (2,3) y (2,4) son los mismos que hay en las casillas (1, 1) y (1, 2) aunque podrían tener otro orden, por lo que sólo tenemos 2 y 1 opciones respectivamente.
| 4 |
3 |
2 |
1 |
| 2 |
1 |
2 |
1 |
| 2 |
2 |
? |
? |
| 1 |
1 |
? |
? |
La casilla (3, 1) la rellenamos con un 2 porque solo tiene las restricciones de la columna a la que pertenece (a la que de momento sólo hemos asignado 2 números), automáticamente vemos que a la casilla (4, 1) sólo le queda 1 opción. La casilla (3,2) también tiene dos opciones disponibles, otra vez podría parecer que tiene más restricciones que las de la columna a la que pertenece, pero si observamos bien, veremos que los elemenos que pertenecen a su misma submatriz son los mismos que la estan restringiendo en su columna, por lo que de 4 opciones seguirá pudiendo escoger 2. Obviamente a la casilla (4,2) sólo le queda una opción (o por las restricciones de la columna, o por las de la submatriz).
Ahora es cuando nos encontramos con el problema que por lo visto aparece más veces en el caso de los 3-sudokus. En el caso de la casilla (3,3) no tenemos una cantidad fija de números que podamos poner habiendo fijado los anteriores… a priori parece que esa cantidad depende de la configuración de los números que hayamos escrito anteriormente (mientras construíamos el sudoku, no lo confundamos con los números que hemos anotado nosotros para contar). Pondré dos ejemplos de 2-sudokus para mostrar lo que estoy diciendo.
| 1 |
2 |
3 |
4 |
| 3 |
4 |
1 |
2 |
| 2 |
1 |
4 |
? |
| 4 |
3 |
? |
? |
2
|
4 |
3 |
1 |
| 1 |
3 |
2 |
4 |
| 3 |
2 |
? |
? |
| 4 |
1 |
? |
? |
En el caso del primer 2-sudoku resuelto vemos que en la casilla (3, 3) solo podemos poner un número, el 4. En el segundo caso tenemos dos posibilidades para la posición (3, 3), podríamos poner o bien un 1 o bien un 4, pero ojo, lo que a priori parecía un sudoku resoluble ahora se muestra como algo sin solución. Como bien podemos ver, si en la casilla (3, 3) ponemos un 1 o un 4, el que no hayamos puesto se tendrá que poner en una de las 3 casillas vacías que nos quedan… ¡pero en ninguna se puede poner porque las restricciones no lo permiten!
No voy a demostrarlo formalmente, pero es facil ver que no se puede dar el caso en que la casilla (3, 3) pueda tener dos opciones, porque siempre nos encotraremos con el mismo problema, que habrá un número imposible de escribir si se quieren seguir las restricciones.
Por lo que la matriz que usabamos para contar nos quedará así (las casillas restantes a parte de las (3, 3) obviamente solo tendran una opción posible dadas las restricciones).
| 4 |
3 |
2 |
1 |
| 2 |
1 |
2 |
1 |
| 2 |
2 |
1 |
1 |
| 1 |
1 |
1 |
1 |
Ahora solo tenemos que multiplicar los números que hemos obtenido y obtendremos la cantidad de 2-sudokus existentes una cota superior de los sudokus existentes (tendríamos que eliminar las configuraciones que no nos permitían encontrar solución, como la que he mostrado para ejemplificar).
4·3·2·1 · 2·1·2·1 · 2·2·1·1 · 1·1·1·1 = 384
Así pues deberíamos calcular cuantas veces puede ocurrir esta situación y restarle ese número a 384. Las submatrices azul y verde determinan los valores de la submatriz naranja, por lo que sólo hace falta contar cuantas configuraciones pueden tener las matrices azules y verdes manteniendo esa configuración que transformaba el sudoku en irresoluble. Para la casilla (1, 3) (submatriz verde, esquina superior izquierda) podemos poner 4 números, para la casilla (2, 3) (esquina inferior izquierda de la submatriz verde) podemos poner 3 números, para lo que queda de verde sólo nos quedan dos opciones. Para la fila superior de la submatriz azul tenemos dos posibles órdenaciones, podría parecer que lo mismo pasa para la fila inferior, pero resulta que no es así, pues una de las dos posibles ordenaciones sería incompatible también con una ordenación correcta para la submatriz naranja.
Lo que nos da una cantidad de 4·3·2·2 = 48 , con lo que tenemos (ahora sí) que el número de 2-sudokus existentes es 384-48 = 336 .
Para acabar, algunos apuntes. El problema que hemos tenido con la casilla (3, 3) ha sido relativamente sencillo de resolver, pero se puede dar el caso en el que realmente no se pueda contar la cantidad de números que se pueden poner en una casilla sabiendo que se han escrito los anteriores, puede que la configuración de los números haga variar dicho número. Y parece que realmente es lo que pasa en los casos en los que n es superior o igual a 3.
Por lo visto la cosa es mas complicada de lo que a primera vista parecía, pues la primera solución encontrada para contar el número de 3-sudokus posibles se halló en 2005 por Bertram Felgenhauer y Frazer Jarvis. Para ello contaron con razonamientos lógicos parecidos a los que yo he hecho para este caso más sencillo (obviamente los suyos debieron ser mucho más sofisticados) pero tambien necesitaron que un ordendor estuviera haciendo cálculos por fuerza bruta unas cuantas horas. La cosa no parece fácil. Así pues la pregunta que me hice sigue sin resolver.
Para los que sientan curiosidad por este tipo de juegos, hay que decir que se pueden llegar a complicar mucho, y de muchas formas distintas. Una es aumentar el tamaño del n-sudoku, es decir, aumentar la n. Otra es hacer que las submatrices no sean cuadradas, sino rectangulares.. para eso podríamos definir el concepto (m,n)-sudoku, habría n·m números diferentes, y n·m submatrices no cuadradas de tamaño n·m. Es claro que los n-sudokus son un caso particular de los (m,n)-sudokus, y si ya es complicada la pregunta para el caso particular… no quiero imaginar como sería en éste.
Pero todavía nos estamos quedando cortos, la cosa se podría complicar más aun si las regiones que hemos usado para las restricciones no fueran submatrices sino conjuntos conexos pero no necesariamente con una distribución tan uniforme y regular como la de los rectángulos o cuadrados. En el artículo de Sudoku de la wikipedia podemos ver un ejemplo, se llaman sudokus nonominos y son la rehostia de complicados.
Ale, si os aburrís tenéis algo más en qué pensar, ahora parece que este juego ya no se reduce solo a intentar rellenar huecos :p .
Enlaces adicionales:
):
.