Un sudoku no puede resolverse sin al menos 17 cifras-pista en su inicio

Un matemático utiliza un algoritmo complejo y "muchas horas de trabajo ante un superordenador" para determinar este resultado

EUROPA PRESS MADRID 10/01/2012 13:48 Actualizado: 10/01/2012 19:32

Un sudoku no puede resolverse sin al menos 17 cifras-pista en su inicio. EP

El matemático de la Universidad de Dublín Gary McGuire, ha utilizado un algoritmo complejo y "muchas horas de trabajo ante un superordenador" para determinar que un sudoku no se puede resolver si no hay un mínimo de 17 cifras-pista en su inicio, ya que con menos "no existe una solución única".

Este juego, que se hizo popular en Japón y es habitual en el espacio de pasatiempos, cuenta en su mayoría con unas 25 cifras-pista, según ha apuntado el científico. A medida que bajan las pistas, más difícil es su resolución.

La complejidad del sudoku ha llevado a los matemáticos a estudiarlo. Ahora, McGuire ha llegado a esta conclusión tras trabajar durante dos años en el algoritmo complejo que le ha llevado a la solución. Para ello ha utilizado unos siete millones de horas buscando a través de las redes. "La única manera realista de conseguir resultados era el método de la fuerza bruta", ha apuntado McGuire, quien ha añadido que "su investigación ha inspirado para impulsar las técnicas de computación y matemáticas hasta el límite".

McGuire ha simplificado el trabajo de algunos de sus compañeros, que le han precedido en esta investigación, mediante el diseño de un algoritmo que evitara lo que el científico ha denominado "series inevitables" o "lo que podría dar lugar a múltiples soluciones".

Según ha señalado la revista Nature, el anuncio de este hallazgo se ha producido en un cogreso matemático celebrado en Boston el pasado 7 de enero y en donde recibió la aprobación de sus compañeros. "El enfoque es razonable y es plausible", ha apuntado el matemático de la Universidad James Madison (EEUU).

31 Comentarios

#1 Vota Vota

0 i Don Quixote 10-01-2012 14:46

Esto lo hubieran resuelto los matermáticos del XVIII a mediados del XX con las manos atadas a la espalda y mientras charlaban con la familia. Si no tienen ordenadores y el método de la fuerza bruta es muy difícil, verdad hijitos? Ay Agnesi, Agnesi, lo que hay que leer.
#2 Vota Vota

-8 i MartynJones 10-01-2012 14:49

No es cierto. Se puede resolver un sudoku incluso sin ningún numero.

"La única manera realista de conseguir resultados era el método de la fuerza bruta"

Tampoco es cierto.
#3 Vota Vota

1 i Asleepkam 10-01-2012 15:14

"La complejidad del sudoku ha llevado a los matemáticos ha estudiarlo" toma patada
#4 Vota Vota

9 i jorgeviejo 10-01-2012 15:32

MartynJones, resolver un sudoku no significa solo rellenar todas las casillas, sino que esta solución sea única dados los números iniciales. Tampoco vale con poner 17 números sin más; por ejemplo, imagina que no hay ningún ocho o nueve. Entonces por cada solución válida hay otra solución igualmente válida cambiando los ochos por los nueves.
#5 Vota Vota

3 i jorgeviejo 10-01-2012 15:35

Asleepkam, ya no un sudoku, sino la generalización de un sudoku (con 9, 10 o n casillas, con reglas especiales...) no es una trivialidad matemática.
#6 Vota Vota

6 i Lanyel 10-01-2012 15:42

Martyn lo que se busca es una solución única y es lo que revela la investigación, por debajo de 17 cifras-pista los sudokus comienzan a tener múltiples soluciones por lo tanto no puedes saber cual es la que te pide el pasatiempo.
#7 Vota Vota

8 i Brikinhos 10-01-2012 16:15

#2

Siempre tiene que haber un listillo...
#8 Vota Vota

0 i guanchu 10-01-2012 16:16

Me pregunto si realmente estaba escrito así en la nota de prensa de Europa Press.

jorgeviejo, me temo que no te has enterado de lo que Asleepkam pretendía decir. O quizás deba decir que no te "as" enterado...
#9 Vota Vota

-1 i b 10-01-2012 16:20

#5 creo que lo de la patada no va por ahí, si no por temas de redacción usando el sistema "becario en prácticas" y los riesgos que eso conlleva para los ojos del lector
#10 Vota Vota

-1 i Brikinhos 10-01-2012 16:34

A que no hay huevos de resolver el sudoku en muy difícil del diario El Mundo!

PD: regalan el periódico en la politécnica, no es que lo compre, sería un sacrilegio dar un sólo céntimo a esos fascistoides
#11 Vota Vota

0 i SuperConnard 10-01-2012 16:54

A mí me parece un sistema de ecuaciones bastante sencillo. El sistema y por supuesto el número de datos que se deben dar seguramente los conocía ya el tipo que creó los sudokus.

Desde luegooo, tanto paro y tanta gente pagada por tocarse los sudokus (mejor, mejor, ¿eh? prefiero más pagados por la patilla, mientras no sea con dinero público, y menos parados).
#12 Vota Vota

3 i kilroywashere 10-01-2012 17:06

# 8

aunque sea becario, como mínimo le deberían exigir que sepa escribir correctamente en español.
#13 Vota Vota

1 i hayquejoderse 10-01-2012 17:20

¡¡¡¡¡Ay mamá!!!!!

Ese "ha estudiarlo" con toda su h ahí puesta me ha hecho perder el hilo de la noticia.
#14 Vota Vota

1 i Luisjooo 10-01-2012 17:25

Joder, vaya puntapie al castellano. Y en un diario de la talla de público. Supongo que lo habrá escrito Remedios Cervantes.....
#15 Vota Vota

3 i joanlopz 10-01-2012 17:26

¿Nadie se ha dado cuenta de que 7 millones de horas son casi 800 años?
#16 Vota Vota

0 i Diablillo 10-01-2012 17:32

Esto, FCO MORENO MECO lo resuleve mirando al tendido.
#17 Vota Vota

5 i altermundista 10-01-2012 17:33

Le voy a copiar a #8 b algo que escribí hace pocos días:

"Vaya, no sé qué pasa entre algunxs forerxs que piensan que ser idiota es una característica inherente a lxs becarixs.
Se nota que en la época de estudios de quien lxs desprecia no existía esa figura, sino se cuidarían muy mucho de menospreciarlxs así.
Tenéis que desprenderos del halo de superioridad ése que parece ser os otorga el tener un titulito universitario colgado en la pared."

Menudo clasismo...
#18 Vota Vota

3 i MikeA 10-01-2012 17:55

Lo más llamativo de la falta de ortografía es que ya aparece en la fuente de Europa Press

http://www.europapress.es/sociedad/ciencia/noticia-sudoku-no-puede-resolver-menos-17-cifras-pista-inicio-20120110124823.html

Hacen copy y paste y luego pasa lo que pasa...
#19 Vota Vota

1 i MikeA 10-01-2012 17:56

Las cosas no son siempre lo que parecen. Los detalles son importantes.
#20 Vota Vota

0 i Racano 10-01-2012 18:28

quien hace los sudokus?
#21 Vota Vota

1 i Attanar 10-01-2012 18:43

Madre mía qué redacción. Premio Planeta mínimo.
#22 Vota Vota

5 i visantet 10-01-2012 19:13

La única forma, de momento, de resolver un sodoku es por búsqueda ciega (método prueba-error: ir "rellenándolo" hasta encontrar la solución). No existe ningún algoritmo que permita su resolución "automática" (en computación un sodoku sería lo que se llama un problema NP). Pueden "estudiarse" métodos que "acorten" el proceso de búsqueda evitando, y detectando con prontitud en lo posible explorar vías de solución condenadas al fracaso (por ejemplo, en computación, "métodos de poda" en el árbol de búsqueda), tal como ha hecho el matemático del que se habla.
Lo que, supuestamente, ha demostrado este matemático es que en un soduko 9x9 ( un sodoku clásico cuadrado con 81 números) para que la solución sea ÚNICA (haya una única solución válida para el sodoku) es necesario que, como mínimo, se den 17 cifras-pista (aunque no queda claro si estas cifras-pista pueden ser al azar o han de cumplir alguna condición adicional). Si hay menos, habrá más de una solución válida para el sodoku, però óbviamente (y en eso se equivoca el titular) si que se podrá resolver.
Y, una vez más cada vez que se da una noticia de ciencia que el "periodista" no tiene porqué entender en su totalidad, aparte de transcribir y copiar la noticia de agencia (a veces mal, a veces bien pero sin darse cuenta que esa noticia a lo mejor ha sido "mal traducida", de su original inglés), ¿tanto trabajo cuesta llamar por teléfono a un especialista en la materia para poder dar la noticia sin decir burradas?
#23 Vota Vota

1 i MartynJones 10-01-2012 20:05

#4 jorgeviejo10-01-2012 15:32
--- MartynJones, resolver un sudoku no significa solo rellenar todas las casillas, ...

Ya lo se, y en un fin de semana muy aburrido del año pasado escribí un programa para resolver las rompecabezas sudokus legítimas y para identificar patrones no legítimos.

#6 Lanyel
--- Martyn lo que se busca es una solución única y es lo que revela la investigación

Pues, en este caso, si. Gracias.
#24 Vota Vota

3 i mgflorin4 10-01-2012 20:24

#2: "No es cierto. Se puede resolver un sudoku incluso sin ningún numero".

Sí MartynJones, se pueden hallar todas las posibles combinaciones de un sudoku en blanco, sólo que la lista conmprendería todos los sudokus posibles de ese tamaño habidos y por haber; el objetivo de un sudoku es hallar sólo la única posible y para ello deben enunciarse como premisas las ubicaciones de 17 de los 81 dígitos que lo componen.

Sí coincido contigo en que el método de la fuerza bruta no parece la única manera de hallarlas,
#25 Vota Vota

3 i WangLu 10-01-2012 21:32

No lo puedo evitar. La solución para es Sudoku de la foto de la noticia es:

+=============+
||2|3|4||8|9|1||5|6|7||
||1|6|9||7|2|5||4|3|8||
||5|7|8||3|4|6||9|1|2||
+=============+
||3|1|6||5|7|4||8|2|9||
||4|9|7||6|8|2||1|5|3||
||8|2|5||1|3|9||7|4|6||
+=============+
||6|4|2||9|1|8||3|7|5||
||9|5|3||4|6|7||2|8|1||
||7|8|1||2|5|3||6|9|4||
+=============+

:-D
#26 Vota Vota

-5 i Indignado 11-01-2012 00:30

Mucho funcionario veo yo por aquí...
#27 Vota Vota

0 i gaussianos 11-01-2012 03:54

Aparte del tema de la falta de ortografía (riesgos que se corren cuando uno copia tal cual una nota de prensa sin leerla), creo que también es importante el contenido de la noticia. Demasiada inconcreción bajo mi punto de vista. Quizás este post de mi blog sea de utilidad para los interesados en el tema:

http://gaussianos.com/demostrado-un-sudoku-debe-comenzar-con-17-numeros-dados-para-pueda-tener-solucion-unica/#comment-27305
#28 Vota Vota

0 i Doraemon 11-01-2012 09:59

#11 En absoluto es un sistema de ecuaciones. Si intentas hacerlo verás enseguida por qué. No importa que las distintas filas, columnas o cuadros formen cierta igualdad (una ecuación), sino que importa el orden dentro de cada una de ellas. En todo caso sería un 'sencillo' problema de combinatoria.
Y sería sencilla la resolución, claro, no la generalización matemática de las condiciones de resolubilidad del conjunto de todos los sudokus, que es algo mucho más complejo. La complejidad es infinitamente mayor; más o menos como la diferencia que hay entre encontrar midiendo la relación en un triángulo rectángulo, y demostrar el teorema de Pitágoras, o la diferencia entre resolver un enunciado lógico cualquiera y demostrar el teorema de Gödel.
#29 Vota Vota

1 i JAVIEREZ 12-01-2012 21:38

#26 Indignado
Y yo algún que otro tonto que no podría aprobar una oposición en la vida, ¡qué le vamos a hacer!
#30 Vota Vota

0 i Bathory 13-01-2012 17:29

#26 indignado, la mayoría de los comentarios son fuera del horario de 8h a 15h, que es cuando trabajan la mayoría de los funcionarios.
#31 Vota Vota

0 i Art Moli 14-01-2012 22:14

y.. entonces donde queda un resolvedor de sudocus digital que venden en florida, dolfin miami por 50 dolares, el cual tiene el tamaño de un gps o de un celular y te da las repuestas en segundos