Esta es una pregunta que ha pesado mucho sobre la comunidad de Sudoku, sobre todo porque creen que saben la respuesta. Los fanáticos del sudoku han encontrado numerosos ejemplos de cuadrículas con 17 pistas que tienen una solución única, pero nunca han encontrado una con 16 pistas.
Eso sugiere que el número mínimo es 17, pero nadie ha podido demostrar que no hay una solución de 16 pistas al acecho en algún lugar del rompecabezas.
Ingrese Gary McGuire y amigos en el University College de Dublín. Estos tipos han resuelto el problema utilizando la técnica matemática probada y confiable de pura fuerza bruta.
En esencia, estos muchachos han examinado cada posible solución de 16 pistas para cada posible grilla de Sudoku. “Nuestra búsqueda no encontró acertijos de 16 pistas, pero si hubiera uno, entonces lo habríamos encontrado”, dicen.
Esa es una hazaña impresionante. Hay exactamente 6, 670, 903, 752, 021, 072, 936, 960 posibles soluciones para Sudoku (aproximadamente 10 ^ 21). Eso es mucho más de lo que se puede verificar en un período de tiempo razonable.
- ¿A qué pregunta crees que nunca recibirás una respuesta?
- ¿Cuánto tiempo lleva vaciar un jacuzzi con una pajita para beber?
- ¿Por qué los crucigramas publicados por revistas semanales / mensuales se crean intencionalmente a un nivel fácil?
- ¿Cuál es la respuesta al ‘acertijo de Einstein’?
- Aparezco una vez por segundo, dos veces por mes y 3 veces por año. ¿Qué soy? ¿Quién puede responder esto primero?
Pero como la suerte lo tendría, no es necesario verificarlos a todos. Varios argumentos de simetría prueban que muchas de estas cuadrículas son equivalentes. Esto reduce el número que debe verificarse a solo 5, 472, 730, 538.
Así que McGuire y compañía escribieron un programa llamado Checker para verificar cada una de estas cuadrículas en busca de una solución de 16 pistas.
Pero el proceso de verificar una sola cuadrícula es en sí complicado. Una forma de hacerlo es examinar cada subconjunto posible de 16 pistas para ver si alguno de ellos conduce a una solución única. El problema es que hay unos 10 ^ 16 subconjuntos para cada cuadrícula.
Una vez más, un poco de matemática es útil. McGuire y compañía utilizaron un razonamiento inteligente para mostrar que ciertos subconjuntos son equivalentes a muchos otros y esto reduce drásticamente la cantidad de subconjuntos que deben verificarse.
Sin embargo, el cálculo resultante sigue siendo un monstruo. El equipo de Dublín dice que tomó 7,1 millones de horas de procesamiento en una máquina con 640 procesadores Intel Xeon de núcleo hexagonal. Comenzaron en enero de 2011 y terminaron en diciembre.
Todo el ejercicio puede parecer un poco de diversión matemática, pero este tipo de resolución de problemas tiene muchas aplicaciones importantes. McGuire y compañía dicen que el problema de la verificación de la cuadrícula de Sudoku es formalmente equivalente a los problemas en el análisis de expresión génica y en las pruebas de software y redes informáticas.
Por lo tanto, los métodos del equipo de Dublín para acelerar el cálculo también tendrán un impacto directo en estas áreas.
Pero si bien el resultado es claramente impresionante, el problema mínimo de sudoku no está del todo descartado.
Este problema está pidiendo una prueba elegante que nos permita “ver” por qué el número mínimo debe ser 17; más bien como la prueba de que no puede haber soluciones únicas para 7 o menos pistas.
Una gran pregunta, lo sé, pero seguramente merece la pena apuntar.
Fuente – Resolviendo el problema del número mínimo de pistas de Sudoku,
MIT Technology Review