Fuente: Tim Psych/ Flickr
La clave del sudoku es que tiene una solución única, y llegar hasta ese punto puede resultar complicado. Para quien no sea usuario habitual de la sección de pasatiempos de los periódicos, donde el rompecabezas japonés se hizo popular internacionalmente, el objetivo del juego es rellenar una cuadrícula de 9 × 9 celdas, dividida a su vez en subcuadrículas de 3 × 3, con las cifras del 1 al 9 partiendo de números ya dispuestos en algunas casillas.
La dificultad estriba en que cada columna, fila y región sólo puede contener los números del 1 al 9 una vez. Por ello, es imposible llegar muy lejos sin establecer una lista de posibles valores o candidatos para cada celda vacía. Hacer esto a mano es bastante laborioso, y a menudo aparta del placer de resolver estos rompecabezas a muchos usuarios.
Cada vez existen más programas en la red que ayudan en este paso, relegando la diversión únicamente a aplicar la lógica para resolver cada enigma. Ahora, investigadores de la Universidad de Notre Dame en Indiana, Estados Unidos, han encontrado un método que, además de exitoso, consumo mucho menos tiempo.
El equipo liderado por Dame Zoltan Toroczkai y María Ercsey-Ravasz no sólo puede explicar por qué algunos Sudoku son más difíciles que otros, sino que también ha desarrollado un algoritmo matemático que los resuelve rápidamente, sin tener que adivinar combinaciones o dar marcha atrás para probar nuevos números.
La dificultad estriba en que cada columna, fila y región sólo puede contener los números del 1 al 9 una vez. Por ello, es imposible llegar muy lejos sin establecer una lista de posibles valores o candidatos para cada celda vacía. Hacer esto a mano es bastante laborioso, y a menudo aparta del placer de resolver estos rompecabezas a muchos usuarios.
Cada vez existen más programas en la red que ayudan en este paso, relegando la diversión únicamente a aplicar la lógica para resolver cada enigma. Ahora, investigadores de la Universidad de Notre Dame en Indiana, Estados Unidos, han encontrado un método que, además de exitoso, consumo mucho menos tiempo.
El equipo liderado por Dame Zoltan Toroczkai y María Ercsey-Ravasz no sólo puede explicar por qué algunos Sudoku son más difíciles que otros, sino que también ha desarrollado un algoritmo matemático que los resuelve rápidamente, sin tener que adivinar combinaciones o dar marcha atrás para probar nuevos números.
Algoritmo determinista
Según publica la Universidad de Notre Dame en un comunicado, la mayoría de los entusiastas de este rompecabezas utilizan lo que se conoce como "fuerza bruta" para resolverlos, combinado con una buena dosis de suerte. Los sistemas de fuerza bruta, en esencia, despliegan todas las combinaciones posibles de números en cada celda hasta dar con la respuesta correcta. Aunque el método es efectivo, requiere demasiado tiempo.
En cambio, la propuesta desarrollada por Toroczkai y Ercsey-Ravasz parte de un algoritmo analógico universal completamente determinista, es decir, sin estimaciones ni búsqueda exhaustiva, entrenado para llegar siempre a la solución correcta del problema y de forma mucho más rápida.
Los investigadores también descubrieron que el tiempo que se tarda en resolver un problema con su algoritmo correlaciona con la dificultad del mismo, como ocurre a los solucionadores humanos. Esto les llevó a desarrollar una escala de clasificación según la dificultad del rompecabezas.
La escala va del 1 a 4, y se ajusta muy bien con el nivel fácil, intermedio, difícil o extremadamente difícil que se aplica actualmente a los Sudoku. Un rompecabezas con calificación 2 requiere un promedio de 10 veces más tiempo para resolverlo que uno con calificación 1. Según este sistema, el Sudoku más difícil conocido hasta ahora tiene una calificación 3,6, y no se sabe si los habrá aún más complicados.
Toroczkai y Ercsey-Ravasz procedían de la Universidad Babeș-Bolyai (UBB) en Rumanía, donde comenzaron a estudiar Sudokus como parte de su investigación sobre la teoría de la optimización y la complejidad computacional. “Yo no había estado interesado en el Sudoku hasta que empezamos a trabajar los diferentes tipos de problemas de satisfacibilidad booleana;, asegura Toroczkai.
En teoría de la complejidad computacional, se trata de determinar si a las variables de una fórmula booleana se le pueden asignar determinados valores que hagan que su resultado sea verdad. “El Sudoku es un problema de este tipo, por lo que parecía un buen banco de pruebas para dar con la solución, así que me familiaricé con él”, continúa explicando el profesor.
Tanto para los líderes de este estudio como para un buen número de investigadores que estudia este tipo de problemas, una pregunta interesante es hasta dónde puede llegar el ser humano para resolver un Sudoku de forma determinista, es decir, sin vuelta atrás, sin hacer una elección al azar para comprobar dónde conduce, y si falla, volver a empezar. “Nuestro solucionador es determinista, no hay elecciones al azar ni retrocesos durante la dinámica”, insiste Toroczkai.
Según publica la Universidad de Notre Dame en un comunicado, la mayoría de los entusiastas de este rompecabezas utilizan lo que se conoce como "fuerza bruta" para resolverlos, combinado con una buena dosis de suerte. Los sistemas de fuerza bruta, en esencia, despliegan todas las combinaciones posibles de números en cada celda hasta dar con la respuesta correcta. Aunque el método es efectivo, requiere demasiado tiempo.
En cambio, la propuesta desarrollada por Toroczkai y Ercsey-Ravasz parte de un algoritmo analógico universal completamente determinista, es decir, sin estimaciones ni búsqueda exhaustiva, entrenado para llegar siempre a la solución correcta del problema y de forma mucho más rápida.
Los investigadores también descubrieron que el tiempo que se tarda en resolver un problema con su algoritmo correlaciona con la dificultad del mismo, como ocurre a los solucionadores humanos. Esto les llevó a desarrollar una escala de clasificación según la dificultad del rompecabezas.
La escala va del 1 a 4, y se ajusta muy bien con el nivel fácil, intermedio, difícil o extremadamente difícil que se aplica actualmente a los Sudoku. Un rompecabezas con calificación 2 requiere un promedio de 10 veces más tiempo para resolverlo que uno con calificación 1. Según este sistema, el Sudoku más difícil conocido hasta ahora tiene una calificación 3,6, y no se sabe si los habrá aún más complicados.
Toroczkai y Ercsey-Ravasz procedían de la Universidad Babeș-Bolyai (UBB) en Rumanía, donde comenzaron a estudiar Sudokus como parte de su investigación sobre la teoría de la optimización y la complejidad computacional. “Yo no había estado interesado en el Sudoku hasta que empezamos a trabajar los diferentes tipos de problemas de satisfacibilidad booleana;, asegura Toroczkai.
En teoría de la complejidad computacional, se trata de determinar si a las variables de una fórmula booleana se le pueden asignar determinados valores que hagan que su resultado sea verdad. “El Sudoku es un problema de este tipo, por lo que parecía un buen banco de pruebas para dar con la solución, así que me familiaricé con él”, continúa explicando el profesor.
Tanto para los líderes de este estudio como para un buen número de investigadores que estudia este tipo de problemas, una pregunta interesante es hasta dónde puede llegar el ser humano para resolver un Sudoku de forma determinista, es decir, sin vuelta atrás, sin hacer una elección al azar para comprobar dónde conduce, y si falla, volver a empezar. “Nuestro solucionador es determinista, no hay elecciones al azar ni retrocesos durante la dinámica”, insiste Toroczkai.
El algoritmo resuelve Sudokus con fórmulas deterministas. Fuente: Scientific Reports.
Del juego a la investigación
Sin embargo, la finalidad del estudio no acaba en la resolución efectiva del popular rompecabezas. Toroczkai y Ercsey-Ravasz creen que su algoritmo tiene potencialidad para aplicarse a una amplia variedad de problemas en la industria, la informática y la biología computacional. Aunque para ello habrá que esperar a avances futuros.
De momento, la experiencia de la investigación ha convertido a Toroczkai en un devoto del juego. “Tanto mi esposa como yo tenemos varias aplicaciones de Sudoku en nuestros iPhones, y debemos haber jugado miles de veces, compitiendo para obtener los tiempos más cortos para terminar todos los niveles", afirma.
“Ella ve a menudo combinaciones de patrones que para mí pasan desapercibidos. Tengo que deducirlos. Sin papel y lápiz para anotar las posibilidades, me resulta imposible resolver muchos de los Sudokus que nuestro solucionador clasifica como difíciles o extremadamente difíciles”, reconoce el profesor.
El método de Toroczkai y Ercsey-Ravasz fue publicado por primera vez en la revista Nature Physics, y su aplicación al Sudoku aparece en la edición del 11 de octubre de Nature Scientific Reports.
Sin embargo, la finalidad del estudio no acaba en la resolución efectiva del popular rompecabezas. Toroczkai y Ercsey-Ravasz creen que su algoritmo tiene potencialidad para aplicarse a una amplia variedad de problemas en la industria, la informática y la biología computacional. Aunque para ello habrá que esperar a avances futuros.
De momento, la experiencia de la investigación ha convertido a Toroczkai en un devoto del juego. “Tanto mi esposa como yo tenemos varias aplicaciones de Sudoku en nuestros iPhones, y debemos haber jugado miles de veces, compitiendo para obtener los tiempos más cortos para terminar todos los niveles", afirma.
“Ella ve a menudo combinaciones de patrones que para mí pasan desapercibidos. Tengo que deducirlos. Sin papel y lápiz para anotar las posibilidades, me resulta imposible resolver muchos de los Sudokus que nuestro solucionador clasifica como difíciles o extremadamente difíciles”, reconoce el profesor.
El método de Toroczkai y Ercsey-Ravasz fue publicado por primera vez en la revista Nature Physics, y su aplicación al Sudoku aparece en la edición del 11 de octubre de Nature Scientific Reports.