Cambalache 3,14 - La vidriera irrespetuosa


Que el mundo fue y será una porquería, ya lo sé.

¿Cuántos sudokus hay?

Se discute estos días en la lista snark del número de posibles sudokus diferentes.

Mi polifacético amigo gonfer proporciona esta respuesta desde el grupo de USENET es.ciencia.matematicas

Un tablero de sudoku es un tablero de 9x9 casillas de forma que en cada horizontal y en cada vertical hay los numeros del 1 al 9 y en cada uno de los 9 cuadrados 3x3 que no tienen casillas en común hay los numeros del 1 al 9.

Ya se ha comentado por aquí. Según la wikipedia ("traducción" del inglés y enlaces añadidos por 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.
Pero esto se refiere al número de tableros. Cuando tenemos en cuenta el número de datos y la posición de estos, de forma que se obtenga solución única, este número se multiplica de forma aun desconocida.
Un buen ejercicio es calcular el número de soluciones para el tablero de 4*4 (sudok-ito, en lenguaje snarkiano).
Última hora: Sony Computer Entertainment España anuncia hoy la llegada de Go! Sudoku a PSP™ (PlayStation®Portable) en diciembre.

Ultimísima hora: Resolvedor de sudoku killer disponible en español.

2005-11-07 18:08 | Categoría: | 15 han comentado esto | Enlace permanente | Etiquetas: | Y dicen por ahí

Referencias (TrackBacks)

URL de trackback de esta historia http://zifra.blogalia.com//trackbacks/34494

1
De: DeutschBlog Fecha: 2005-11-10 06:57

Hay Sudoku para rato: «En todos lados vemos los mentados Sudokus: revistas, periódicos, en la red, y ahora hasta en el PlayStation Portable. Pero ¿cuántos sudokus puede haber?, bueno pues esta pregunta entretuvo a algunos y, según cuenta La Vidriera Irrespetuosa, en la wik»



Comentarios

1
De: ElPez Fecha: 2005-11-07 20:44

Por cierto, más de una y más de dos veces me he encontrado algún sudoku en la prensa escrita en que la solución no es única: típicamente quedan dos pares de números intercambiables. Por supuesto, para quien está haciéndolo, la cosa es como para fusilar al listillo que lo compuso.

¿es en general cierto que,

- sean dos filas: I, J
- y sean dos columnas, i, j
tales que pertenecen a "regiones diferentes" (esto es, la fila I no está en la misma región que la fila J, ni la columna i coincide en regiones con la columna j)

si denominamos N(I,i) al dígito de la casilla I,i, y consecuentemente N(I,j), N(J,i) y N(J,j)

entonces si se da que N(I,i)=N(J,j) y N(I,j)=N(i,j)

es preciso que alguno de los N(,) esté declarado al comienzo para evitar ese problema de indefinición?



2
De: Zifra Fecha: 2005-11-07 20:59

En general no tiene porqué ser cierto. Pero no me resulta fácil buscar un contraejemplo sencillo con el estómago vacío :-)



3
De: ElPez Fecha: 2005-11-07 21:28

Tienes razón, Zifra... porque planteé mal el problema. En ese caso que yo comento, basta con que si uno de los números del baile posible está ya definido en la región de uno de ellos, la cosa no valga.
De hecho, lo que he escrito es una solemne tontería. El problema se da, precisamente, cuando ese par de números que "bailan" posiciones aparece precisamente en la misma región, y no en diferentes, como impuse de condición. Es en esos casos cuando se podría intercambiar el par de números.

Es decir, la condición sería que: o bien I y J pertenecen a la misma región; o bien lo hacen i y j

Me pasa lo mismo con el estómago, así que olvídalo :-)



4
De: Zifra Fecha: 2005-11-07 21:36

mmmm... veo lo que hay detrás de lo que dices, pero no veo como formularlo bien

la cuestión es, en el fondo, ¿cuales son las condiciones para que un número prefijado haga la solución única o no?

puedo aventurar que es un problema NP,. pero poco más :-)



5
De: ElPez Fecha: 2005-11-07 23:22

bueno, ya es bastante como para que opte por olvidarme de ello :-)



6
De: Harry.c Fecha: 2005-11-08 14:12

Como fan de los sudokus y de las matemáticas, ésta es una cuestión que me he planteado a menudo: Cuántos sudokus hay? Al principio pensé que se trataría de un cálculo de probabilidades. Ya sabéis: combinaciones con repetición y bla, bla, bla... pero veo que es más complicado que eso.
Yo nunca me he encontrado con uno de varias soluciones. Hago los de El País, El Mundo y algunas publicaciones con formato de libro.
También me gustaría saber cómo se crea uno...



7
De: Zifra Fecha: 2005-11-08 14:21

Está prohibido que un sudoku tenga varias soluciones



8
De: Carlos A. Fecha: 2005-11-08 21:31

Para Harry.c: En los Sudoku Samurai de El País de los domingos ya me he encontrado unos pocos. De hecho, una vez había uno que tenía cuatro soluciones porque se daba el problema que menciona ElPez en dos lugares distintos. Por cierto: el problema no tiene por qué darse en sólo cuatro casillas. También me lo he encontrado en situaciones en las que involucra a 8 casillas. Lástima que los termino y los tiro.

Cuando ocurre es realmente cabreante: (casi) toda la lógica se te va a tomar viento.



9
De: Cluje Fecha: 2005-11-10 11:35

Jeje qué listos, la solución que se propone es la del problema sencillo (entre comillas). Lo interesante es ver cuántos sudokus hay, entendiendo como tal el tablero 9x9 con espacios en blanco y solución única. Yo también soy fanático y no he encontrado ninguno en los periódicos con números intercambiables.

Por otro lado, os dejo aquí unas preguntas que puse hace tiempo en mi blog sobre sudokus, quizá os interesen. Si tenéis algo constructivo que decir sobre ellas me encantaría saberlo. La pregunta d) que falta es la que encabeza esta discusión :DDD

Saludos

a) ¿Cuál es el la mínima cantidad de cifras de un sudoku? (Obsérvese que de forma trivial el cuadrado en blanco o el cuadrado con una cifra, por ejemplo, NO son sudokus)

b) ¿Cuál es el máximo número de cifras compatibles en un cuadrado 9x9 sin que sea sudoku?

c) Dada una cierta solución de un sudoku, ¿cuántos sudokus tienen esa misma solución? ¿Ese número es independiente de la solución?


e) ¿Hay algún algoritmo SENCILLO que permita decidir si una configuración es sudoku o no? Por supuesto, la resolución habitual del sudoku es una prueba de que ocurre lo primero, pero la negación parece más difícil



10
De: Zifra Fecha: 2005-11-10 11:42

Enhorabuena, Cluje. ese es un planteamiento como de Matemática Discreta

¿Cual es la direccion de tu blog?



11
De: Cluje Fecha: 2005-11-10 12:11

Ah, lo siento, pensaba que habría salido. Es blogia.com/musolari , y la entrada de los sudokus es http://musolari.blogia.com/temas/mates.php

Chao y enhorabuena por el blog. Te he visto comentando a veces por el de Lola :D



12
De: Zifra Fecha: 2005-11-10 12:38

interesantísimo. yo también te recuerdo del blog de lola.

mientras pienso lo del sudoku, te fusilo los párrafos de Eckmann para el blog Madisc



13
De: Zifra Fecha: 2005-11-10 12:52

interesantísmo tu blog, quería decir



14
De: Cluje Fecha: 2005-11-11 10:59

Anda!!! Le he echado un vistazo a tu CV y estamos más cerca de lo que pensamos... He visto que te dirigió la tesis Alberto Márquez, y yo me tuve que empollar su tesina para la mía; era de cuando aún hacía topología antes de pasarse a la matemática discreta. Yo me quedé en la topo, y me dirigió la tesina Antonio Quintero, así que somos primos cuartos matemáticos o así :-DDD

Venga, un saludo



15
De: {´poiuygf Fecha: 2009-03-21 19:17

xdfghjk



Nombre
Correo-e
URL
Dirección IP: 54.197.180.64 (31fa8f66c5)
Comentario

Busca en Cambalache


Blogalia


Se comenta en Cambalache

  • Anónimo en ¿Quienes somos, de dónde venimos, a dónde vamos?
  • Anónima en 10 de Marzo de 1991
  • Anónima en Ya nunca juego al ajedrez Años de plomo (la película)
  • Anónima en No, no es la Diada ni son las torres gemelas de Manhattan...
  • Zifra en Olvido
  • Anónimo en Olvido
  • Zifra en Quantum State-Independent Contextuality Requires 13 Rays
  • Anónima en Álgido
  • nfernefer en Álgido
  • Zifra en Álgido
  • Categorías:

    Archivos:

    <Marzo 2017
    Lu Ma Mi Ju Vi Sa Do
        1 2 3 4 5
    6 7 8 9 10 11 12
    13 14 15 16 17 18 19
    20 21 22 23 24 25 26
    27 28 29 30 31    


    Lista de Enlaces

    De interés

    E-góticos

    Mis otros

    FotoFlickr


    Blogalia



    Versión para la columna lateral


    zifra. Get yours at bighugelabs.com/flickr
    2003-2006 Zifra – Powered by Blogalia – Estadísticas: Nedstat Basic - Web site estadísticas gratuito El contador para sitios web particulares