Demostrado: un Sudoku debe comenzar con 17 números dados para que pueda tener solución única

Seguro que todos sabéis lo que es un Sudoku y que muchos de vosotros habéis resuelto (o al menos intentado) uno en alguna ocasión. Y es muy posible que algunos seáis unos auténticos “enganchados” de este interesante juego (el padre de Mamen entre ellos).

No todos los sudokus tienen la misma dificultad, eso también lo sabemos. Generalmente ésta depende de la cantidad de números que aparecen en el sudoku antes de comenzarlo y de la colocación de los mismos. Lo que sí es una norma es que todo sudoku bien planteado debe tener solución única. Teniendo en cuenta esta restricción, y partiendo de uno que tenga solución, ¿cuál es la cantidad mínima de números que deben aparecer inicialmente en el sudoku para que pueda estar bien planteado?

Sudoku con 17 casillas rellenas

Sudoku con 17 casillas rellenas, el mínimo necesario para que pueda tener solución única (aunque éste tiene más de una)

Este problema, que podríamos denominar el problema del sudoku mínimo o el problema del mínimo número de casillas rellenas, era hasta ahora un problema abierto sobre el cual ya hacía tiempo que se estaba trabajando (en Microsiervos hablaron sobre ello en este post hace más de 5 años). Pero ya no lo es, ya que el pasado domingo 1 de enero de 2012 pasó a convertirse en un problema resuelto. Se ha demostrado que el número mínimo de casillas que debe traer rellenas un sudoku para que pueda tener solución única es 17. Esto significa que todo sudoku (que tenga solución) con 16 casillas rellenas o menos seguro que tendrá más de una solución.

Los artífices de esta demostración son Gary McGuire, Bastian Tugemann y Gilles Civario, de la School of Mathematical Sc (University College Dublin, Ireland, que han colgado en arXiv su trabajo There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem. En este artículo, de solamente 36 páginas, se demuestra que no hay sudokus con 16 casillas rellenas de principio que tengan solución única mediante el estudio de todos los posibles resultados. Es decir, McGuire y su equipo han estudiado todos los posibles sudokus con 16 números colocados de principio y han visto que ninguno de ellos tiene solución única. Para no tener que comprobarlo en todos los casos posibles, unos 6,7 \cdot 10^{21}, estudiaron posibles simplificaciones atendiendo, por ejemplo, a ciertos tipos de simetrías. Obtuvieron así que tenían que estudiar unos 5500 millones de sudokus esencialmente distintos, una ardua tarea que realizaron mediante software. Vamos, fuerza bruta pero con ayudas.

Teniendo en cuenta que si un sudoku con n casillas dadas de principio tiene solución única, entonces también la tiene uno con n+1 casillas dadas, obtenemos que ningún sudoku con menos de 16 números dados de antemano tendrá solución única. Añadiendo esto a lo anterior demostramos que el número mínimo necesario para que un sudoku pueda tener única solución es 17.

Según el equipo responsable de la demostración, este resultado puede ayudar a resolver algunos problemas de teoría de grafos y puede tener aplicaciones en bioinformática y en testeo de software.


Fuentes:

Share

20 comentarios

  1. gaussianos | 7 de enero de 2012 | 18:59

    Vótalo Thumb up 0

    También aparece en Nature:

    Mathematician calims breakthrough in Sudoku puzzle

  2. Trackback | 7 ene, 2012

    Bitacoras.com

  3. didtux | 7 de enero de 2012 | 19:58

    Vótalo Thumb up 0

    excelente voy a modificar mi programa ya que en dificil arranca con 15

  4. ZetaSelberg | 7 de enero de 2012 | 20:57

    Vótalo Thumb up 0

    ^DiAmOnD^ ¿Estás seguro que ese Sudoku tiene solución única?

    Después de mucho hecharle cabeza, me he rendido y lo he metido a varios programas solucionadores de sudokus y me han soplado una solución común: Hay varias soluciones.

  5. gaussianos | 7 de enero de 2012 | 22:00

    Vótalo Thumb up 0

    ZetaSelberg, pues no, debo haberme confundido. Ahora mismo cambio la frase debajo de la imagen. Gracias por el aviso.

  6. Cristhian_ | 8 de enero de 2012 | 05:26

    Vótalo Thumb up 0

    Pero, no me quedo claro.

    Quiere decir que el minimo posible son 17? o que el mas dificil posible es de tan solo 17?

  7. ZetaSelberg | 8 de enero de 2012 | 05:33

    Vótalo Thumb up 0

    Hola Cristian,

    Lo que ha demostrado el artículo es simplemente que todos los sudokus que tienen 16 números iniciales tienen más de una solución o no tiene solución.

    De ese hecho viene el que un sudoku con 17 números iniciales es difícil, ya que las ayudas para resolverlo estarían al mínimo.

  8. Sebastián Espinar | 8 de enero de 2012 | 10:56

    Vótalo Thumb up 0

    Una pregunta tonta: ¿Esto implica que si tengo un sudoku hecho, siempre hay 17 números que los puedo borrar de sus casillas de tal forma que otra persona solo los puede volver a rellenar creando el sudoku original?

  9. Miércoles | 8 de enero de 2012 | 20:57

    Vótalo Thumb up 0

    En el título falta un “que” entre “para” y “pueda”.

  10. gaussianos | 8 de enero de 2012 | 23:05

    Vótalo Thumb up 0

    Cierto Miércoles, gracias por el aviso :)

  11. Trackback | 9 ene, 2012

    Sudokus with minimum number of clues « Xi'an's Og

  12. Trackback | 9 ene, 2012

    Demostrado: un Sudoku debe comenzar con 17 números dados para que pueda tener solución única

  13. Leonardo | 10 de enero de 2012 | 17:53

    Vótalo Thumb up 0

    Desde la ignorancia de un estudiante de primero; por debajo de 17 cifras, ¿sería el conjunto de soluciones un espacio vectorial sobre \mathbb{Z}/_{10} \mathbb{Z}?

  14. chobin | 11 de enero de 2012 | 01:06

    Vótalo Thumb up 0

    que poco me gustan las demostraciones computacionales…

  15. Nico Granelli | 11 de enero de 2012 | 09:50

    Vótalo Thumb up 0

    Yo lo que no entiendo es que tienen que ver los dados con los sudokus

  16. Manuel | 12 de enero de 2012 | 13:09

    Vótalo Thumb up 1

    El resultado está expresado de una forma un tanto confusa.

    Yo entiendo que NO cualquier disposición de 17 números garantiza: a) que haya solución y b) que haya solución única

    Lo que entiendo es que, dado un sudoku válido, siempre se puede encontrar al menos un conjunto de 17 números-pista que proporcionan esa solución de forma unívoca.

  17. SudoTonteria | 12 de enero de 2012 | 13:38

    Vótalo Thumb up 0

    Leyendo el artículo y pensando que alguien ha invertido tiempo en esto para hacer una publicación entiendo porque la ciencia y en específico la matemática está marginada y deslucida.

    Saber si hay solución es lo único importante en un problema de decisión, no importa si es solución única. Por otro lado el siguiente problema después de saber que existe solución es encontrar la solución que es otro problema y se soluciona de la misma manera sabiendo si existe una o mil soluciones.

    la verdad es que de absurdos está lleno el mundo.

    Recomiendo que lean acerca del problema 2-SAT y 3-SAT del cual el sudoku no es más que una instancia.

  18. HM2P33 | 13 de enero de 2012 | 01:54

    Vótalo Thumb up 0

    SudoTonteria: En mi opinión, al publicarse un sudoku es tan importante la existencia como la unicidad de la solución, puesto que si esta última condición no se satisface, es imposible llegar a la solución por medio de únicamente razonamientos sin ningún tipo de adivinanza. A jugadores como a mi, nos molesta tremendamente tener que recurrir a adivinanzas en este tipo de juegos, aún los sudokus más difíciles admiten una resolución por razonamiento por más complicados que estos sean (y largos en algunos casos). En conclusión, no me parece ninguna tontería esta publicación.

  19. Claudio | 10 de abril de 2013 | 23:21

    Vótalo Thumb up 0

    Lo que quiere decir el articulo es nunca hay un sudoku con una solucion con menos de 17 pistas , pero no que haya siempre una solucion con 17 pistas o mas por que depende de las posicion comprobado por master sudoku

  20. Henry | 6 de septiembre de 2013 | 01:40

    Vótalo Thumb up 0

    Por definición un sudoku debe tener una única solución y para ello se requieren 17 o mas candidatos. De aquí se desprende que todo sudoku con 16 o menos candidatos, pasaría a ser algo así como un seudo-sudoku.

Escribe un comentario

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia. Utiliza la Vista Previa antes de publicar tu comentario para asegurarte de que las fórmulas están correctamente escritas.