Blogia
Tio Petros

Contando sudokus

Habrán pensado que este blog ha dejado de actualizarse...

En realidad ocurren dos cosas; una es la falta de pericia de su autor para seguir proponiendo paseos matemáticos, que pasados dos años de actividad regular se va resintiendo, y otra es el periodo veraniego, poco apto para estas cosas. Sabrán perdonarme por ambas cuestiones.

Para paliar un poco este silencio les propongo un reto difícil. Calcular el número de SUDOKUS lícitos.

Como supongo que sabrán, un sudoku es un cuadrado de 9x9 casillas (puede ser de otro tamaño, pero consideraremos este, por ser el más habitual. Las casillas están agrupadas en nueve subcuadrados de 3x3. Pues bien; se deben rellenar las casillas con números del 1 al 9 de manera que no se repitan ni en las filas, ni en las columnas ni en los subcuadrados de 3x3.

Aquí tienen una explicación algo más pormenorizada de lo que es un sudoku, en el hipotético y extraño caso de que no se lo hayan encontrado aún en la sección de pasatiempos de cualquier periódico.

Ya hemos dicho varias veces que la combinatoria, no siendo más (ni menos) que el arte o la técnica de contar elementos de conjuntos), puede ser una disciplina apasionante y muy complicada. Aquí tienen un ejemplo.

Les espero.
¿Y esta publicidad? Puedes eliminarla si quieres
¿Y esta publicidad? Puedes eliminarla si quieres

15 comentarios

javi -

Cual es la solucion matemataica para resolver cualquier sudoku. Me juego la nota de mate en una hora,mandarme la respuesta porfavor

Zifra -

El número de soluciones válidas para el sudoku estándar con tablero de 9×9 ha sido calculado por Bertram Felgenhauer en 2005 y es 6670903752021072936960.

Ese número es 9! × 722 × 27 × 27,704,267,971, cuyo último factor es primo. El resultado fue obtenido usando una mezcla de lógica y computación de "fuerza bruta". El cálculo del resultado fue simplificado considerablemente por el análisis efectuado por Frazer Jarvis confirmado independientemente por Ed Russell. Russell y Jarvis tambié demuestran que si las simetrías son tomadas en cuenta hay 5472730538 soluciones. Para el tablero de 16*16 el resultado no es conocido.

Más (con enlaces) en http://zifra.blogalia.com/historias/34494

suso -

De un sólo sudoku pueden hacerse aproximadamente 13 millones de variaciones, cambiando el valor de los números y moviendo cuadrados de 3x3 por filas y columnas:
9*8*7*6*5*4*3*2 (permut.nº)
*
3*2 filas
*
3*2
columnas
---------------------
Pregunta:
cuál es el número mínimo necesario por debajo del cual un sudoku no tendría una única solución?
Yo he llegado a sólo 22 núms.

Jorge -

¿No quedaban por publicar unos post sobre raíces cuadradas y cúbicas? ;-)

TioPetros -

"También he visto comentar que hasta ahora el análisis combinatorio de los posibles cuadrados latinos (que son como el Sudoku pero sin la restricción de que los subcuadrados de 3×3 sean diferentes) sólo ha podido ser acometido por el método de fuerza bruta. Dudo que la restricción impuesta en el Sudoku sirva para simplificar el problema; más bien para agravarlo, me temo."

Si así es, entonces me alegro, porque me siento completamente incapaz de solucionar el problema...

Pedro Gimeno -

Todavía veo ambigüedad en el planteamiento del problema. ¿Se trata de determinar la cantidad de sudokus posibles, o la cantidad de sudokus fundamentalmente diferentes?

Lo digo porque si giramos 90° un tablero de sudoku obtendremos uno diferente, pero no fundamentalmente. Lo mismo pasa si cambiamos el tablero por su simétrico, y lo mismo si sustituimos los números del 1 al 9 por cualquier permutación de los mismos. Si hacemos eso también con la máscara inicial, el método de resolución no cambiará.

En cualquier caso el tema de los tableros fundamentalmente diferentes abre otros interrogantes de interés, como por ejemplo: ¿qué forma tendría el tablero en versión "canónica"? Gracias a la sustitución podemos por ejemplo escoger tableros cuya primera fila conste de los números del 1 al 9 en ese orden, aunque es obvio que esta restricción no es suficiente para delimitarlos a todos (subespecificación), pues las versiones transformadas son susceptibles de aplicarles la permutación que convierte la primera fila a esta forma.

Si además colocamos un 4 en la primera casilla de la segunda fila, ¿estamos sobreespecificando lo que sería un tablero canónico? (me refiero a si estamos dejándonos posibles tableros). ¿Lo estaremos subespecificando?

Me temo que en este caso estará subespecificado. He encontrado una maravillosa demostración que este margen, por ser tan pequeño, no puede contener... ;)

Tal vez colocar números en posiciones fijas no sea la forma más adecuada de encontrar la especificación para un tablero canónico. Era tan sólo una idea al azar.

Otra cuestión interesante es cuán diferente sería un sudoku obtenido a partir de otro mediante intercambio de dos filas o columnas, siempre que las dos elegidas no se salgan del mismo cuadrado. Por ejemplo, la primera y la segunda filas, o la quinta y sexta columnas, o la séptima y novena, pero no se cuenta como bueno intercambiar la sexta y la novena filas, por ejemplo.

Parece obvio que esta transformación también da lugar a un sudoku fundamentalmente equivalente al original. Con esto en mente, pues, hay que incluir que por cada grupo de tres filas o columnas consecutivas hay seis permutaciones diferentes que dan lugar al mismo tablero fundamental, y que si se intercambian "filas gordas" (de 3 filas) cada una o "columnas gordas" entre sí, también, lo cual son cinco permutaciones más (seis en total) que son equivalentes a la canónica. He visto por la red que alguien preguntaba si no será que al final hay un único tablero fundamental y todo lo demás son transformaciones triviales de este tipo.

También he visto comentar que hasta ahora el análisis combinatorio de los posibles cuadrados latinos (que son como el Sudoku pero sin la restricción de que los subcuadrados de 3×3 sean diferentes) sólo ha podido ser acometido por el método de fuerza bruta. Dudo que la restricción impuesta en el Sudoku sirva para simplificar el problema; más bien para agravarlo, me temo.

-- Pedro Gimeno

mewt -

En la pagina
http://www.shef.ac.uk/~pm1afj/sudoku/
se encuentra el algoritmo (de fuerza bruta) que se usa para calcular la solución a este problema...

Ranstom -

Pues mal expresado, claro...
Lo que pretendía decir en primer término es que la masa terrestre es del orden de casi 900.000 veces mayor que la suma de las masas de todos los sudokus dintintos (suponiéndoles un gramo de masa a cada uno)

Ranstom -

Discrepo de ese resultado.

Lo diré así:

Si cada sudoku impreso pesara un gramo, se necesitarían casi 900.000 sudokus para igualar la Masa terrestre.
Y es que el número de sudokus es casi exactamante 10 elevado a 32 veces el valor de G (constante de gravitación en el sistema internacional)

Anónimo -

¿ 7.899.107.740.876.800.000 ?

mewt -

Ups! Lo siento... :-P Recargar la pagina mientras se envia un comentario no es una buena idea... recargar la recarga, tampoco ;-)

mewt -

Este problema se lo planteó también hace algún tiempo Lieven Le Bruyn, uno de mis supervisores en Amberes, y publicó algo al respecto en su blog. Por desgracia, lo tiene en obras (el blog) así que no se puede ver el post original con los comentarios, aunque recuperó parte del texto, que puede encontrarse (en inglés) aqui:
http://www.math.ua.ac.be/~lebruyn/nebblog/sudokumania.html
Por los comentarios que hace al final de su entrada, no parece que el problema se resuelva por combinatoria elemental...

TioPetros -

Palimp:

He leído tu comentario. Gracias de verdad.

Ñbrevu:

No me refiero a la segunda de tus posibilidades, sino a las combinaciones de cuadrados de 9x9, sin huecos, para los cuales no hay repetición de cifras ni en las filas ni en las columnas ni en los subcuadrados de 3x3.

Ñbrevu -

No entiendo del todo la pregunta. Puede referirse a dos cosas: 1) Combinaciones de cuadrados de 9x9 (o de n²xn²) que cumplan las condiciones de unicidad o 2) Combinaciones de cuadrados con huecos que tengan una y sólo una solución. Ambas son bastante complejas, pero la segunda además plantea preguntas sobre la distribución que deben tener algunos números colocados de forma razonablemente aleatoria para que no aparezcan soluciones espúreas como resultado de la pérdida de información.

Palimp -

Hombre!! Dichosos los ojos!!!
Hace poco te he puesto como buen ejemplo de divulgar matemáticas en mi bitácora (http://lepisma.liblit.com/?p=168) y hace poco hice un 'resolvedor de sudokus' (http://www.liblit.com/sudoku/).
Saludos a Vailima. Se os echa de menos.
¿Y esta publicidad? Puedes eliminarla si quieres