El sudoku es un popular pasatiempo cuya resolución corresponde a un problema matemático de satisfacción con restricciones. Mária Ercsey-Ravasz y Zoltán Toroczkai proponen una manera muy curiosa de saber cuando un Sudoku concreto es fácil o difícil de resolver a mano. Han construido un sistema dinámico continuo (un conjunto de ecuaciones diferenciales ordinarias) capaz de resolver cualquier sudoku y han observado que los problemas difíciles son los que presentan un transitorio con caos determinista. La duración en tiempo κ de este transitorio permite medir la dificultad de un sudoku utilizando una escala logarítmica (similar a la escala de Richter) vía η = -log κ. Un sudoku es fácil si 0<η≤1, de dificultad media si 1<η≤2, difícil si 2<η≤3, y ultradifícil si η>3.
Estos investigadores han sido incapaces de encontrar un sudoku con η>4,
Me ha llamado la atención este trabajo porque estos autores ya presentaron un sistema dinámico caótico similar para resolver el problema k-SAT (con k≥3) que fue portada de Nature Physics, en concreto Mária Ercsey-Ravasz, Zoltán Toroczkai, “Optimization hardness as transient chaos in an analog approach to constraint satisfaction,” Nature Physics 7: 966–970 (2011) [arXiv:1208.0526].Estos investigadores han sido incapaces de encontrar un sudoku con η>4,
La resolución de un sudoku generalizado a un tablero N×N es un problema NP-completo porque puede ser reescrito como un problema k-SAT de satisfacibilidad booleana (problema NP-completo para k≥3). Por tanto, es un problema intratable salvo que P=NP, ya que todos los algoritmos conocidos para resolverlo, en el peor caso, tienen un coste en tiempo exponencial (en la variable N), aunque, para verificar si una solución es correcta basta un tiempo polinómico. Los análogos continuos para la resolución de problemas NP-completos tienen mucho interés teórico porque ofrecen un nuevo punto de vista para estudiar sus propiedades, aunque por ahora sean solo una mera curiosidad.
Entrar en los detalles matemáticos del sistema dinámico continuo (sistema de ecuaciones diferenciales ordinarias) que describe un sudoku nos llevaría demasiado lejos (aunque no es difícil), baste decir que los autores escriben el problema del sudoku como un problema k-SAT (algo bien conocido para la mayoría de los que saben lo que es un problema k-SAT) y que aplican la misma técnica que ya usaron en su artículo de Nature Physics (que es muy “natural” para quienes han estudiado redes de neuronas artificiales de Hopfield). Este sistema dinámico incorpora la configuración de números de partida en el tablero y evoluciona desde una condición inicial aleatoria. Si la solución existe y es única, la evolución en tiempo de este sistema acabará alcanzándola.
Para ilustrar el comportamiento caótico del sistema dinámico, los autores han seleccionado un cuadrado vacío del tablero y han dibujado para diferentes instantes de tiempo (t=10, 15 y 20 en la figura) el dígito dominante para dicho cuadrado (utilizando la tabla de colores mostrada en la propia figura) según el sistema dinámico a partir de una condición inicial con dos valores dados, sean s1 y s2, y con el resto seleccionados de forma aleatoria. El diagrama resultante permite visualizar la diferencia entre un problema fácil (arriba) y otro difícil (abajo). En el segundo caso se observa en el plano (s1,s2) una geometría muy irregular característica de los sistemas caóticos deterministas (en la figura el transitorio todavía no ha concluido).
Caracterizar los sistemas caóticos es difícil, por la irregularidad de su comportamiento, por lo que lo habitual es introducir parámetros que caractericen el comportamiento a largo tiempo. Los autores han decidido introducir un parámetro κ que mide la duración del transitorio caótico (que acaba desapareciendo porque el sistema dinámico acaba convergiendo a la solución exacta). Sea p(t) la probabilidad de que la dinámica no haya encontrado la solución correcta en un tiempo t, entonces la teoría de los sistemas caóticos garantiza que p(t) sigue una distribución exponencial exp(-κ t); en esta teoría a κ se le llama tasa de escape del atractor caótico.
Esta figura muestra el comportamiento de κ en función del número inicial de dígitos d en el tablero del sudoku para múltiples problemas obtenidos de la web con dificultad diversa (medida de forma cualitativa); las páginas web de las que se han extraído estos problemas concretos aparecen en las referencias del artículo técnico. Los autores utilizan esta evidencia empírica para proponer el logaritmo del parámetro κ como medida de la dificultad, de forma similar a como se definió la escala Richter para los seísmos.
En resumen, un artículo realmente curioso que nos muestra una curiosa aplicación de la teoría del caos. Obviamente, que nadie se lleve a engaño, el sistema dinámico utilizado para resolver sudokus es muy ineficiente y costoso comparado con los algoritmos más habituales.
