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.
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.
15 comentarios
javi -
Zifra -
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 -
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 -
TioPetros -
Si así es, entonces me alegro, porque me siento completamente incapaz de solucionar el problema...
Pedro Gimeno -
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 -
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 -
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 -
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 -
mewt -
mewt -
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 -
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 -
Palimp -
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.