sábado, 31 de octubre de 2009

¿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

15 comentarios:

  1. Buf, este post mejor se lo paso al "husband" que es el matemático de la familia porque yo, tras el primer párrafo, comencé a perderme :D

    Besos

    ResponderEliminar
  2. Recuerdo la primera vez que hice un sudoku. Fue hace algunos años, creo que cinco mas o menos. yo estaba trabajando en Canarias, acompañando a un director de cine y la secretaria del mismo, estaba enganchadísima a los sudokus, asi que se empeñó en explicarme en que consistía, hasta que terminamos las dos haciéndolos juntas.
    Ahora yo los utilizo en mis clases, para enseñar los sinogramas. Cada número lo cambio por un sinograma, y asi mis alumnos pueden practicarlos, para reconocerlos, recordarlos y aprender a escribirlos. nueve sinogramas nuevos por sudoku. claro que no a todos les gusta, por eso es algo optativo.
    En cuanto a tu post, pues me resulta curioso como te centras en las cajas y las encajas como si fueran un puzzle de piezas en el que pruebas cual encaja. Hasta este tipo de post, aparentemente tan matemático puede tener diferentes lecturas según quien lo lea.
    saludos.

    ResponderEliminar
  3. Creo que lo sudokus se manejan (y se crean) con algoritmos topológico-numéricos. Lo de numérico no es una redundancia; es decir, en lugar de posiciones de figuras geométricas o de manzanas, se colocan números del 1 al 9 de la manera sabida.

    Yo empecé a hacer sudokus al ver a P. hacerlos, tenía (y tiene) ese vicio al regresar después de trabajar diez hora seguidas en el CSIC. La empecé a imitar, le encontré su gracia, pero sigo sin ser tan bueno como ella. Así que me limito a ganarla al ajedrez que tiene sólo 64 casillas en vez de 81. En cualquier caso ellas es más lista que yo ( y mucho más guapa)

    ResponderEliminar
  4. El número total de sudokus de nueve cifras es:

    6670903752021072936960

    ni uno más, ni uno menos

    O lo que es lo mismo

    9! x 72^2 x 2^7 x 2774267971

    Estoy seguro que hoy vais a dormir todos mucho más tranquilos, especialmente Miros).

    Si queréis saber más:

    Sudoku; Delahaye, Jean-Paul
    Investigación y Ciencia: 359 - AGOSTO 2006

    Finalmente... sudoku; Parrondo, Juan M. R. Investigación y Ciencia: 351 - DICIEMBRE 2005

    ResponderEliminar
  5. Alucinado me dejas, Números. Pero, claro está, no me basta con el númerito sino que necesitaría la explicación del porqué (desde luego, el producto que acompañas no me ayuda casi nada). Si tienes esos artículos, me encantaría que me los hicieras llegar porque no los encuentro en la red.

    En todo caso, está claro que mi duda no es nada original.

    ResponderEliminar
  6. Números: he encontrado un texto en internet (http://www.scribd.com/doc/6401392/Paenza-Adrian-Matematica-Estas-Ahi-Episodio-2)en el que, efectivamente, da la misma cifra que dices para el número de sudokus totales, pero no explica cómo se calcula. De otra parte, me da la impresión que esa cifra sería el total de los sudokus "completos" posibles, pero no así de todos los sudokus derivados de éstos que caben. Además, resulta que todavía no se sabe cuántas cifras deben estar impresas en un sudoku inicial para que éste sea, a la vez, resoluble y dé una única solución. Por lo tanto, me temo que mi pregunta podría no haber encontrado respuesta todavía (o a lo mejor sí, porque el libro consultado tiene ya algunos añitos).

    ResponderEliminar
  7. Buenos días.

    Te he enviado por correo la dirección de megaupload donde bajarte los artículos.

    ¡Qué los disfrutes!

    ResponderEliminar
  8. Muchas gracias, Números. Ya estoy bajándolo y a ver si esta noche me lo leo. Así da gusto; te debo una.

    ResponderEliminar
  9. Sudoku es un juego popular pero no sé cuantos sudokus hay.
    http://es.domo-sudoku.com

    ResponderEliminar
  10. El número de Sudokus posibles de de 4x4 es 96.

    Para comprender el resultado solo tenéis que dibujar un sudoku de 4x4

    Las posibles combinaciones en la 1ª fila son combinaciones sin repetición de 4 elementos tomados de 4 en 4. Esto es 4!=4x3x2x1=24.

    Para la 1ª celda de la segunda fila nos quedan dos números posibles. Luego tenemos combinaciones sin repetición de dos elementos tomados de 1 en 1. Esto es 2.

    Para las celdas 3ª y 4ª de la 1ª columna nos quedan dos números posibles. Luego tenemos combinaciones de 2 elementos tomados de 2 en 2. Esto es 2!=2*1=2.

    Rellenadas la 1ª fila y la 1ª columna el sudoku es único.

    Por tanto el número máximo de sudokus posibles es 4!x2x2!=96.

    Siguiendo un procedimiento similar descubriréis que el número máximo de sudokus de 9 x 9 es: 9! x 6 x 5 x 6! x 4! x 6 elevado a 8 = 315.964.309.635.072.000

    ResponderEliminar
  11. Perdón, la solución al numero máximo de un sudoku de 4 x 4 es 192.
    Dado que a partir de la 1ª fila y la 1ª columna se pueden dar dos posibilidades.

    ResponderEliminar
  12. Tengo una duda. El sudoku de 4x4 sin restricciones cuantas posibles soluciones tiene? 192? Me gustaría saberlo. Muchas gracias!

    ResponderEliminar
  13. hice un calculo antes de buscar sobre esto en Internet, ni bien se me ocurrió.. y llegue a que hay 288 sudokus posibles en el de 4x4.. en el de 9 intente seguir los mismos pasos pero algunas cosas no me cerraron mucho.. el resultado al que llegue con mi larga formula(solo entendible por mi ja ja) es 530698709892021092352000 (530.698.709.892.021.092.352.000) aunque todavía no lo repasé.. cosa que voy a hacer mañana(no tan desvelado ja ja)

    ResponderEliminar
    Respuestas
    1. Yo tambien he llegado a la misma respuesta, de que hay 288 posibles sudokus de 4X4, no he intentado todavia hacer el de 9X9, ya que queria ver si la solucion de ver cuantos 4x4 se aproximaba a algun otro resultado.
      Ya se que han pasado los años asi que igual no te acuerdas

      Eliminar
  14. Saludos Cordiales,

    " 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 " ... Está premisa me parece incorrecta, creo que hay tan sólo 13.579.392, ya que no tamas en cuenta a los Sudokus con más de una solución o ambiguos.

    Gracias..

    ResponderEliminar