Matemático afirma un gran avance en el rompecabezas de Sudoku


Por Eugenie Samuel Reich de la revista Nature. Un matemático irlandés ha utilizado un algoritmo complejo y millones de horas de tiempo de supercomputación para resolver un problema abierto importante en las matemáticas de Sudoku, el juego popularizado en Japón que implica completar una cuadrícula de 9x9 con los números 1-9 según algunos reglas. Gary M

Por Eugenie Samuel Reich de la revista Nature.

Un matemático irlandés ha utilizado un algoritmo complejo y millones de horas de tiempo de supercomputación para resolver un problema abierto importante en las matemáticas de Sudoku, el juego popularizado en Japón que implica completar una cuadrícula de 9x9 con los números 1-9 según algunos reglas.

Gary McGuire de University College Dublin muestra en una prueba publicada en línea el 1 de enero que el número mínimo de pistas, o dígitos iniciales, necesarios para completar un rompecabezas es 17; Los rompecabezas con 16 o menos pistas no tienen una solución única. La mayoría de los rompecabezas de periódicos tienen alrededor de 25 pistas, y la dificultad de los rompecabezas disminuye a medida que se dan más pistas.

El consenso emergente entre los matemáticos en una conferencia en Boston, Massachusetts, el 7 de enero fue que la prueba de McGuire es probablemente válida y un importante avance en el creciente campo de las matemáticas del Sudoku.

"El enfoque es razonable y plausible. Yo 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 en el Matemáticas del sudoku.

Las reglas de Sudoku requieren que los rompecabezas completen una cuadrícula de 9x9 con los números 1-9 para que no se repita ningún dígito dentro de la misma columna, fila o sub-cuadrícula de 3x3. Las pistas son los números que se completan para empezar, y los entusiastas han observado durante mucho tiempo que, aunque hay algunos rompecabezas con 17 pistas, nadie ha podido encontrar un rompecabezas válido de 16 pistas. Eso llevó a la conjetura de que los rompecabezas de 16 pistas con soluciones únicas simplemente no existen. Una forma potencial de demostrar que podría ser revisar todas las cuadrículas posibles para cada rompecabezas de 16 pistas, pero eso tomaría demasiado tiempo de computación. Así que McGuire simplificó el problema diseñando un 'algoritmo de conjunto de golpes'. La idea detrás de esto fue buscar lo que él llama conjuntos inevitables, o arreglos de números dentro del rompecabezas completo que son intercambiables y, por lo tanto, podrían resultar en múltiples soluciones. Para evitar que los conjuntos inevitables causen soluciones múltiples, las pistas deben superponerse, o "golpear", los conjuntos inevitables. Una vez que se encuentran los conjuntos inevitables, es una tarea de computación mucho más pequeña, aunque todavía no trivial, para mostrar que ningún rompecabezas de 16 pistas puede golpearlos a todos.

Después de pasar dos años probando el algoritmo, McGuire y su equipo utilizaron alrededor de 700 millones de horas de CPU en el Irish Center for High-End Computing en Dublín, buscando posibles cuadrículas con el algoritmo de conjunto de golpes. "La única forma realista de hacerlo fue con el enfoque de la fuerza bruta", dice Gordon Royle, matemático de la Universidad de Australia Occidental en Perth que había estado trabajando en el problema de contar 17 rompecabezas de pistas usando diferentes algoritmos. "Es un problema desafiante que inspira a las personas a llevar al límite las técnicas computacionales y matemáticas. Es como escalar la montaña más alta".

Dice Laura Taalman, matemática también de la Universidad James Madison, que es coautora del libro Tomando en serio el Sudoku: La matemática detrás El rompecabezas de lápices más popular del mundo con Rosenhouse. Taalman señala que el libro, que salió la semana pasada, ya está desactualizado: dice que el problema sigue abierto y que quien resuelva será una "estrella de rock".

McGuire dice que su enfoque puede dar sus frutos de otras maneras. La idea de conjunto de golpes que desarrolló para la prueba se ha utilizado en artículos sobre análisis de secuenciación de genes y redes celulares, y espera ver si otros investigadores pueden adaptar su algoritmo. "Ojalá esto estimule más interés", dice.

Pero dice que, irónicamente, mientras dedicaba más tiempo a las matemáticas del dilema, pasó menos tiempo disfrutando del rompecabezas. "Todavía encuentro una buena forma de relajarme de vez en cuando, pero para ser honesto, prefiero hacer el crucigrama", dice.

Este artículo se reproduce con permiso de la revista Nature. El artículo fue publicado por primera vez el 6 de enero de 2012.

Últimas noticias

La geoingeniería podría convertir el cielo en blancoHouse Science Panel agrega miembros que niegan el climaHermosa, segura, asequible, y obtiene 100 millas por galón: X PRIZE elige la siguiente ronda de concursantes automotricesCómo mejorar el monitoreo de las emisiones globales de gases de efecto invernadero¿Qué significa la nueva "mente abierta" de Trump en el Acuerdo Climático?Se amplía la brecha entre la política climática de EE. UU. Y el arrendamiento de carbónCómo conseguir más ciclistas en la carreteraCombatiendo el cambio climático: cultivando soluciones para el calentamiento global