Para los amantes del Sudoku, es claro que algunos resultan extremadamente difíciles de resolver. Por ejemplo, el buen amigo y estupendo programador, el matukense Jorge Kobeh, alguna vez me indicó que algo parece estar faltando en algunos sudokus porque la lógica parece no alcanzar para resolverlos y entonces uno tiene que buscar aplicar otras técnicas. Y en opinión de Kobeh (qure c omparto), eso no está bien. Un sudoku debería poderse resolver solamente aplicando la lógica al problema.
Evidentemente hay variadas técnicas para resolver este tipo de pasatiempos y uno de ellos es la fuerza bruta, es decir, poniéndo números y observando si todo va resultando. Si falla algo, entonces uno se regresa al paso previo (hace backtrack -dirían los que programan en Prolog) y busca otra combinación de números. De hecho, ésta es la técnica usada por muchos programas pues el sistema puede resultar en alguna medida manejable por las computadoras actuales. Hay unos 5 mil millones de sudokus diferentes (en una matriz de 9×9), por lo que pese a estos enormes números, ya les quedan chicos a las máquinas actuales, incluso las caseras.
Pues bien, si usted todavía batalla con algunos sudokus, los investigadores de las redes complejas, Zoltan Toroczkai y la investigadora postdoctoral María Ercsey-Ravasz, pueden ayudarnos. Ellos no solamente explican por qué algunos sudokus son más difíciles que otros, sino que han desarrollado un algoritmo matemático que resuelve los sudokus de manera muy rápida y sin tener que hacer backtrack o estar adivinando números.
Ambos investigadores han estudiado los sudokus como parte de su investigación en la teoría de la optimización y la complejidad computacional. Hacen notar que la mayoría de los entusiastas de los sudokus usan lo que se conoce como “fuerza bruta” para resolver el problema, combinado con un buen grado de adivinación sobre qué números deben ir en qué casillas. Este método aunque resulta adecuado para solucionar el problema, lleva demasiado tiempo.
Así, en lugar de esto, Toroczkai y Ercsey-Ravasz han propuesto un algoritmo determinístico (sin hacer búsquedas exhaustivas o asumir ciertos números) que lleva a la solución correcta y además, en mucho menos tiempo. Los investigadores descubrieron también que el tiempo que les lleva resolver el problema con su algoritmo está correlacionado con la dificultad del mismo. Esto llevó a una clasificación que va de 1 a 4, de “fácil” a “difícil”, llegando a “ultradifícil”. Un sudoku de rango 2 toma en promedio 10 veces más que resolver uno de rango 1. De acuerdo a este sistema, el sudoku más difícil hasta ahora es de 3.6, lo cual quiere decir que no se ha hallado uno más complejo o difícil aún.
Dice Toroczkai: “No me interesé por los sudokus hasta que empecé a trabajar en una clase de problemas de satisfabilidad general booleana” y agrega: “desde entonces hallamos que los sudokus son parte de esta clase y parece ser una buena cama de pruebas para nuestro programa que los resuelve. Para nosotros (como otros investigadores), resolver sudokus determinísticamente (sin backtracking) parecía ser algo imposible de realizar. Nuestro programa es determinístico y no hace elecciones azarosas o backtrack cuando usa esta dinámica”.
Toroczkai y Ercsey-Ravasz creen que el algoritmo puede ser aplicado a una amplia variedad de problemas en la industria, ciencias de la computación y biología computacional (aunque muchas veces esto no termina por cumplirse. Se dijo lo mismo con el programa SHRLDU, el cual iba a cambiar la manera en como se podía hacer lenguaje natural con la computadora y nunca prosperaron los intentos en otras ramas).
Ahora el investigador es un apasionado de los sudokus: “Ambos, mi mujer y yo tenemos varias apps en nuestros iPhones y los habremos jugado ya miles de veces, compitiendo para completar los niveles cada vez en menor tiempo”, dice. “Ella con frecuencia ve patrones que yo simplemente no alcanzo a ver y que tengo que deducir. Sin papel y lápiz para estas tareas, me es imposible resolver muchos de los problemas que nuestro programa resuelve, a pesar de caer en la categoría de “ultradifíciles”.
La metodología de Toroczkai y Ercsey-Ravasz se publicó en Nature Physics, y su aplicación al sudoku apareció el 11 de octubre en la publicación Nature Scientific Reports.
Referencias: