Los matemáticos resuelven un problema mínimo de sudoku

Sudoku es un acertijo numérico que consta de una cuadrícula de 9 x 9 en la que algunas celdas contienen pistas en forma de dígitos del 1 al 9. El trabajo del solucionador es completar las celdas restantes para que cada fila, columna y cuadro de 3 × 3 en la cuadrícula contiene los nueve dígitos.

Hay otra regla no escrita: el rompecabezas debe tener una sola solución. Por lo tanto, las cuadrículas no pueden contener solo algunas pistas iniciales.

Es fácil ver por qué. Una cuadrícula con 7 pistas no puede tener una respuesta única porque los dos dígitos que faltan siempre se pueden intercambiar en cualquier solución. Un argumento similar explica por qué las cuadrículas con menos pistas también deben tener múltiples soluciones.

Pero no es tan fácil ver por qué una cuadrícula con 8 pistas no puede tener una solución única, o de hecho, una con 9 o más pistas.

Eso plantea una pregunta interesante para los matemáticos: ¿cuál es el número mínimo de pistas de Sudoku que produce una respuesta única?

Esta es una pregunta que pesa sobre la comunidad de Sudoku, sobre todo porque creen que conocen 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 acechando en algún lugar del espacio del rompecabezas.

Ingresan Gary McGuire y sus amigos de University College Dublin. 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 todas las posibles soluciones de 16 pistas para cada posible cuadrícula de Sudoku. Nuestra búsqueda no arrojó acertijos adecuados de 16 pistas, pero si hubiera existido 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.

Pero, por suerte, no es necesario comprobarlos 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 complicado en sí mismo. Una forma de hacerlo es examinar cada subconjunto posible de 16 pistas para ver si alguna de ellas 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áticas son útiles. McGuire y compañía utilizaron un razonamiento inteligente para demostrar 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 se necesitaron 7,1 millones de horas centrales de tiempo 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 divertido matemático, 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 problemas en el análisis de expresión génica y en las pruebas de software y redes de computadoras.

Por 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 del Sudoku no está del todo descartado.

Este problema clama por 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 pistas o menos.

Una gran pregunta, lo sé, pero seguramente una a la que vale la pena apuntar.

Ref: arxiv.org/abs/1201.0749 : No hay sudoku de 16 pistas: Resolver el problema de número mínimo de pistas del Sudoku

Corrección: esta publicación fue editada el 6 de enero para reflejar el argumento de que si una cuadrícula de n pistas tiene una solución única, entonces agregar un dígito para hacer una cuadrícula de n + 1 pistas también debe tener una solución única. Entonces, si no hay cuadrículas de 16 pistas con solución única, no puede haber cuadrículas con menos pistas que se puedan resolver de manera única. Gracias a RealMurph y abooij.

esconder