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

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor del blog Gaussianos. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

17 Comentarios

  1. ^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.

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

    Publica una respuesta
  3. Pero, no me quedo claro.

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

    Publica una respuesta
  4. 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.

    Publica una respuesta
  5. 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?

    Publica una respuesta
  6. 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}?

    Publica una respuesta
  7. Yo lo que no entiendo es que tienen que ver los dados con los sudokus

    Publica una respuesta
  8. 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.

    Publica una respuesta
  9. 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.

    Publica una respuesta
  10. 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.

    Publica una respuesta
  11. 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

    Publica una respuesta
  12. 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.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: Seguro que todos sabéis lo que es un Sudoku y que muchos de vosotros…
  2. Sudokus with minimum number of clues « Xi'an's Og - [...] I spotted on Mathbloggin.org a Spanish post on the minimal number of clues to solve a Sudoku in a…
  3. Demostrado: un Sudoku debe comenzar con 17 números dados para que pueda tener solución única - [...] los comentarios 1 visto 1 alma 19…

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.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Uso de cookies

Este sitio web utiliza cookies para que tengas la mejor experiencia de usuario. Si continúas navegando estás dando tu consentimiento para la aceptación de las mencionadas cookies y la aceptación de nuestra política de cookies. Más información sobre las cookies <aquí..

ACEPTAR