Por @Alvy — 24 de Enero de 2012

Sudoku17Pistas

Los sudokus buenos, buenos, de pata negra fetén, tienen una solución única sergún la definición más estricta de este pasatiempo matemático. Desde hace tiempo se especulaba con cuál sería el sudoku mínimo, es decir, cuántos «números-pista» iniciales debía tener como mínimo un sudoku para que su solución fuera única.

Unos matemáticos publicaron recientemente un trabajo donde analizaban el problema. Puede leerse al completo en There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem. La conclusión es que, como se suponía y ellos han podido demostrar, hacen falta como mínimo 17 números iniciales para componer un sudoku de solución única.

Para llegar a la solución examinaron mediante software y fuerza bruta unos 5.500 sudokus seleccionados a partir de ciertas premisas, demostrando básicamente que no había sudokus de 16 números con soluciones únicas. Así que como con 17 números iniciales sí que se conocen muchos, ese es el valor buscado.

Hay algo más de información sobre el tema en Gaussianos: Demostrado: un Sudoku debe comenzar con 17 números dados para que pueda tener solución única.

Compartir en Flipboard  Compartir en Facebook  Tuitear

16 comentarios

#1 — Iván

[Un vídeo de Numberphile] habla de eso

http://www.youtube.com/watch?v=MlyTq-xVkQE

#2 — Pulido

Una pequeña corrección: en el artículo de gaussianos dice que tuvieron que probar 5.500 millones de sudokus.

Saludos

#3 — Carlos

muy bueno y elemental como siempre.

http://www.hd-tecnologia.com

#4 — Madeleine

Bueno... y alguien me puede explicar qué diablos significa > fetén?

#5 — Madeleine

Bueno... y alguien me puede explicar qué diablos significa "Pata negra" fetén?

La palabreja o modismo es bastante incomprensible y no acierto a saber que intenta decir, no atino a interpretar de forma adecuada el sentido oculto de la frase.

#6 — Alvy

Significa… Sudokus «auténticos», «genuinos», «más apreciados».

De «pata negra» como el jamón ibérico / pata negra, y de fetén: «1. adj. Bueno, estupendo, excelente. Conocí a una chica fetén. 2. adj. coloq. Sincero, auténtico, verdadero, evidente.»

#7 — Madeleine

Gracias por la aclaración, ahora si pude entender bien el contenido del artículo, máxime que soy una fanática/adicta estos tableritos numéricos que bastantes quebraderos de cabeza me han dado, pero no puedo dejar pasar un día sin resolver alguno.

#8 — Omegan

Como minimo 17, pero... ¿Todos los de 17 tienen solución?

#9 — Accesibilidad web

No me queda muy claro... porque no creo que sea muy científico examinar 5.500 o 5.500 millones de sudokus y, como no se ha encontrado ninguno que se pueda plantear con 16 números iniciales pero sí con 17, afirmar categóricamente que el mínimo es 17. Eso es una falacia de inducción.

#10 — Alvy

Si los examinas todos el razonamiento es impecable. Se ha usado muchas veces. No es lo más elegante pero a veces sí efectivo: Búsqueda de fuerza bruta + Ataque de fuerza bruta.

#11 — Iker

Pero Alvy, creo que examinar "solo" 5.500 millones queda bastante lejos de examinarlos todos.. no?

#12 — Alvy

Al parecer son todos los que hace falta examinar. Es decir, si calculas el total y razonas los que puedes eliminar por simetrías, giros, etc. y otras cosas que se puedan eliminar por lógica, y te quedan esos 5.500 millones… con mirarlos uno por uno tienes suficiente.

Así se resolvió también el problema de los cuatro colores, por cierto, la primera demostración de este tipo –con ordenadores– en la historia.

#13 — I&I

Alvy,el Sudoku de la imagen no es un "Sudoku pata negra".No tiene solución única.

#14 — Alvy

Anda, pues lo ponían como tal (?!)

#15 — I&I

Ahí van dos soluciones diferentes para el Sudoku de la imagen.Hay más.Lo bonito sería saber ¿Cuántas más?
396841752. 934821567
281795436. 261795438
574326918. 587346219
169572843. 316572894
435689127. 795684123
728134569. 428139756
642918375. 642918375
853467291. 153467982
917253684. 879253641

#16 — fer

Yo la verdad, desde que el google googles me soluciona los sudokus, he perdido interés por ellos. Maldita tecnologia! Acaba quitandole la emocion a todo.