Uno de mis pasatiempos favoritos es completar sudokus. Hay algo en este baile aparentemente simple, pero desafiante, de dígitos arriba y abajo, izquierda y derecha que logra mantenerme muy entretenido a través de una mezcla perfectamente equilibrada de emoción y frustración. Si crees que eres lo suficientemente bueno para resolver cualquier tipo de sudoku, ten en cuenta que algunas combinaciones son imposibles de resolver.
Gary McGuire, un matemático del University College Dublin, ha ideado minuciosamente un algoritmo a través del cual ha demostrado científicamente que un sudoku no puede tener menos de 17 pistas, ya que los acertijos con 16 pistas o menos no tienen una solución única. Su típico sudoku de periódico tiene alrededor de 25 pistas, en el lado seguro, lo suficiente como para no aburrirse, mientras mantiene la frustración por no ver la solución a raya.
¡Jadear! De repente me di cuenta de que algunos lectores de ZME podrían no saber qué es un sudoku en primer lugar. Bueno, debo darme prisa antes de seguir explicando cómo funciona el juego. Muy simple: el sudoku implica completar una cuadrícula de 99 cuadrados, de acuerdo con un conjunto de reglas (cada casilla de 33 debe completarse con cada número del 1 al 9, lo mismo ocurre con cada columna y línea de la cuadrícula de 99). Para comenzar y poder encontrar una solución, el rompecabezas tiene algunos cuadros que se completan en un orden particular. Estas son tus pistas, cuantas menos tengas, más difícil se vuelve el juego.
De vuelta a la ciencia. El profesor McGuire presentó su trabajo en la reciente conferencia en Boston, donde sus hallazgos fueron anunciados como válidos y considerados como un avance importante en el creciente campo de las matemáticas del Sudoku, que es más importante de lo que uno podría pensar. Llegaré a eso lo suficientemente pronto.
Ha habido miles de pruebas literarias de sudoku de 16 pistas, sin embargo, se encontró que en cada caso, solo se podía encontrar una solución, pero ¿cómo demostrar esto? Gary McGuire desarrolló un algoritmo de conjunto de golpes para probar definitivamente la teoría. Este algoritmo busca lo que McGuire llama conjuntos inevitables, pares de valores completos en los valores completos que, cuando se intercambian, pueden dar como resultado múltiples soluciones. Al reemplazar estos valores y posiciones de conjuntos inevitables con valores clave, la tarea informática en cuestión se vuelve mucho menos compleja, aunque todavía muy complicada.
El enfoque es razonable y plausible. Diría que la actitud es de optimismo cauteloso, dice Jason Rosenhouse, matemático de la Universidad James Madison en Harrisonburg, Virginia, y coautor de un libro recientemente publicado sobre las matemáticas del Sudoku.
Para ejecutar este algoritmo para soluciones, la fuerza bruta es la única opción. Incluso con el algoritmo de conjuntos inevitables en funcionamiento, que tardó dos años en modificarse, McGuire y su equipo utilizaron alrededor de 700 millones de horas de CPU en el Centro Irlandés de Computación de Alta Gama en Dublín, buscando a través de posibles cuadrículas con el algoritmo de conjuntos de aciertos. El trabajo, dice McGuire, tiene implicaciones más allá del propio Sudoku.
Acertar con los problemas establecidos tiene aplicaciones en muchas áreas de la ciencia, como la bioinformática y las pruebas de software, dice.
El artículo de McGuires se publicó en una edición reciente de la revista Nature .
a través de
"