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, el mínimo necesario para que pueda tener solución única (aunque éste tiene más de una)
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 
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:
- Exhaustive search solves fiendish Sudoku mystery en NewScientist.
- 16 clue sudokus en Michael Trick’s Operations Research Blog.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
También aparece en Nature:
Mathematician calims breakthrough in Sudoku puzzle
para mi esto es una mentira tengo un sudoku en mis manos con mas de 17 números iniciales y tiene por lo menos, dos soluciones . el cambio es pequeño; Es de uno o dos números pero si varia . entonces este articulo es falso. y cualquier duda, lo tengo guardado por, si lo quieren ver ….
me retracto de este comentario no pude editarlo a tiempo …. que pagina rara no me deja borrarlo…
Luis Cabarcas
Te doy la razon , he resuelto correctamente un sudoku con 36 numeros iniciales y este difiere al que figura en el solucionario del libro, quiere decir que por lo menos hay 2 soluciones.
A los dos: partid de un sudoku resuelto, y eliminad los 8 y los 9. El resultado será un sudoku inválido con 63 números iniciales. Inválido porque tiene dos soluciones: una la original, y otra intercambiando los 8 y los 9.
Pero esto no contradice el artículo. Lo que dice el artículo es que al parecer se ha demostrado que nunca vais a encontrar un sudoku válido (con solución única) con menos de 17 números iniciales.
Difiero con dicha demostración: Tengo un sudoku con más de 17 casillas inicialmente establecidas y este tiene dos posibles soluciones, se deberia ańadir a dicha descripción la posición relativa en la que se deben encontrar las casillas inicialmente rellenas para que así tenga validez este articulo. i.e. un sudoku con dos posibles soluciones y con más de 17 casillas lo adjunto a continuación: A4: 7 A6: 4 A9:2 B3:4 B6:8 B8:3 C2:7 C3:5 C7:8 D1:9 D4:1 E2:6 E4:5 E6:2 E8:9 E9:8 F1:3 F7:5 G1:7 G8:4 H1:8 H2:2 H5:3 I3:3 I4:6 I6:9 I7:2 Podreis observar que en la posición D3, D8,… Lee más »
Información Bitacoras.com…
Valora en Bitacoras.com: 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 ……
excelente voy a modificar mi programa ya que en dificil arranca con 15
^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.
ZetaSelberg, pues no, debo haberme confundido. Ahora mismo cambio la frase debajo de la imagen. Gracias por el aviso.
Pero, no me quedo claro.
Quiere decir que el minimo posible son 17? o que el mas dificil posible es de tan solo 17?
LAS DOS AFIRMACIONES SON VÁLIDAS.
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.
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?
En el título falta un «que» entre «para» y «pueda».
Cierto Miércoles, gracias por el aviso 🙂
[…] I spotted on Mathbloggin.org a Spanish post on the minimal number of clues to solve a Sudoku in a unique way. The original paper was posted on […]
[…] los comentarios 1 visto 1 alma 19 Demostrado: un Sudoku debe comenzar con 17 números dados para que pueda tener […]
Desde la ignorancia de un estudiante de primero; por debajo de 17 cifras, ¿sería el conjunto de soluciones un espacio vectorial sobre
?
que poco me gustan las demostraciones computacionales…
A veces es la única manera de hacerlo. Como en el problema de la manada de Arquímedes o el número de sudokus 9×9.
Yo lo que no entiendo es que tienen que ver los dados con los sudokus
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.
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… Lee más »
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.
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
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.
Resumiendo, entiendo que un sodoku que tenga 17 numeros tiene una sola solucion, y que si tiene menos tendra al menos mas de una solucion. Pregunto puedo colocar 17 numeros en forma aleatoria, claro sin que se cruzen entre ellos?
Este sudoku nivel fácil, tiene la posibilidad de invertir el orden de los números 5 y 8 sin que afecte el resultado.
https://ibb.co/fn7V5n
Este es el sudoku inicial para solucionar:
https://ibb.co/hawbBS
Y si cambiamos el 7 , 4 del 1er. cuadrante por el 7 , 4 del 2º pasa lo mismo . Y si cambiamos el 4 , 3 del 1er. cuadrante por el 3 , 4 del 3º pasa lo mismo . Y si cambiamos el 3, 1 de 1er. cuadrante por el 1 , 3 del 7º pasa los mismo , etc. , etc. , etc . Esto ocurre siempre que una pareja o trio de números estén repetidos en la misma linea o columna enfrentada a otra aunque no sea en el mismo orden .El orden de los… Lee más »
Y se puede intercambiar varias parejas o trio a la vez en el mismo sudoku y siguen siendo válidas las soluciones
Hola gente! He resuelto un sudoku de 23 números iniciales y he encontrado 3 soluciones diferentes: una, la que me brindaba la revista; dos, a la que llegué yo; tres, una pequeña variación de mi solución anterior.
Difiero con dicha demostración: Tengo un sudoku con más de 17 casillas inicialmente establecidas y este tiene dos posibles soluciones, se deberia ańadir a dicha descripción la posición relativa en la que se deben encontrar las casillas inicialmente rellenas para que así tenga validez este articulo. i.e. un sudoku con dos posibles soluciones y con más de 17 casillas lo adjunto a continuación: A4: 7 A6: 4 A9:2 B3:4 B6:8 B8:3 C2:7 C3:5 C7:8 D1:9 D4:1 E2:6 E4:5 E6:2 E8:9 E9:8 F1:3 F7:5 G1:7 G8:4 H1:8 H2:2 H5:3 I3:3 I4:6 I6:9 I7:2 Podreis observar que en la posición D3, D8,… Lee más »
Julián, la cuestión no es que todo sudoku con más de 17 casillas dadas tenga solución única, sino que todo sudoku que quiera tener solución única debe venir con, al menos, 17 casillas dadas.
Por tanto, habrá sudokus con más de 17 casillas dadas que tengan solución única y sudokus con más de 17 casillas dadas que tengan más de una solución, pero lo que se ha demostrado es que un sudoku (que tenga solución) con menos de 16 casillas dadas seguro que tiene más de una solución.
Espero haberme explicado bien ahora.
La posición del ejemplo tiene 2271070 soluciones.
FALSO …sudoku con dos soluciones y con 32 casillas numeradas
Tengo un sudoku con 17 casillas y tiene más de una solución.