No hay solución única a los sudokus con 16 números



El acertijo del sudoku es apasionante para muchos, particularmente para quienes hacen ciencia. Todo parece ser matematizable y el sudoku no se ha salvado de ser analizado por matemáticos y programadores en todo el mundo. A pesar de esto, no se sabe todo sobre la estructura algorítmica de los sudokus, por lo que se trabaja buscando resolver problemas como estos: ¿cuántos números mínimo debe haber en el sudoku para poderse resolver? ¿cuántos números deben ser diferentes? ¿cuándo hay solución única?

Investigaciones actuales han llegado a un resultado que parece ya incontrovertible: no se puede resolver un sudoku si sólo hay 16 números (si se busca una solución única). El sudoku estándar se juega en una rejilla de 9×9 en donde hay cajas de 3×3, que deben contener los números del 1 al 9 sin repetición. Cada fila y columna de la rejilla de 9×9 debe además contener los nueve primeros números, también sin repetición. Se busca que los sudokus a resolver tengan una sola solución.

Dado que hay 81 celdas en la rejilla, aparecen una serie de números, normalmente unos 25, para poder resolverlo. Sin embargo, se ha hallado que se requieren al menos 17 números para que el sudoku pueda ser resuelto.

Por ejemplo: Dado que la dificultad de un sudoku probablemente dependa del número de pistas, es muy interesante saber que no ha podido ser hallado un sudoku que pueda resolverse con sólo 16 números. Ahora sabemos porqué.

Un grupo lidereado por Gary McGuire del Dublin University College, ha logrado probar que si un sudoku tiene 16 números entonces tiene más de una solución, por lo cual no hay sudokus con 16 números. Para llegar a esta conclusión, un primer método usado fue un poco salvaje: una búsqueda exhaustiva sobre todo el espacio de todos los sudokus con 16 números. Una vez teniendo esos, se vio qué solución particular tenía cada uno. Sin embargo, aunque se hiciese este trabajo de manera optimizada, probablemente tardaría unos 300,000 años. Así pues, hubo que buscar otro enfoque.

Cabe hacer notar que este enfoque de fuerza bruta no lleva a ninguna parte. Se puede probar fácilmente que un sudoku con 7 números diferentes tiene al menos dos soluciones -los dos números que no están en el sudoku son intercambiables. Sin embargo, un sudoku con 8 números diferentes no resulta tan obvio de probar que tiene más de una solución.

El programa que hizo las búsquedas de los sudokus con 16 pistas -que a la postre no funcionó- usó algunos teoremas para hacer más pequeño el espacio de búsquedas. El algoritmo es explicado en el “paper“ parece que además puede ser usado para bioinformática, redes, genómica e incluso pruebas de software. Eventualmente se llegó a la conclusión que estamos ante un problema clásico NP-completo, lo cual implica que computacionalmente es difícil, muy difícil.

El algoritmo final tomó unas 7.1 millones de horas de procesamiento en 320 nodos, cada uno con 6 núcleos. El programa se inició en enero del 2011 y terminó en diciembre de ese mismo año. ¿Qué significa todo esto al que juega sudokus? Probablemente no mucho. Quizás si ve un sudoku con 16 números pueda decir a los que tenga alrededor con aire de suficiencia: “este sudoku tiene dos soluciones al menos“. Por lo demás, la lección es que incluso las preguntas más simples sobre cosas finitas pueden ser de pronto muy difíciles de aprender.

Anuncios

Responder

Por favor, inicia sesión con uno de estos métodos para publicar tu comentario:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: