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, 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 , 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.

Fuente:

Gaussianos