211service.com
Las matemáticas del sudoku conducen a la 'escala de Richter' de la dureza del rompecabezas
La fascinación global por el Sudoku ha llevado a un repentino interés en las propiedades matemáticas del rompecabezas. En los últimos meses en este blog, hemos visto cómo los matemáticos han resuelto el problema mínimo de Sudoku e incluso cómo han usado las matemáticas del Sudoku para encriptar imágenes.
Hoy, obtenemos una visión diferente del Sudoku gracias al trabajo de Maria Ercsey-Ravasz en la Universidad Babes-Bolyai en Rumania y Zoltan Toroczkai en la Universidad de Notre Dame en Indiana.
Estos chicos han desarrollado una forma de medir la dificultad de un Sudoku en particular y dicen que su escala de Richter de dificultad de rompecabezas podría aplicarse a una amplia gama de otros juegos.
Primero, un poco de historia sobre el Sudoku. Este es un acertijo numérico que consta de una cuadrícula de 9 x 9 en la que algunas celdas contienen pistas en forma de dígitos del 1 al 9. El trabajo del solucionador es completar las celdas restantes para que cada fila, columna y cuadro de 3 × 3 en la cuadrícula contiene los nueve dígitos. Además, cada cuadrícula solo puede tener una solución.
Los rompecabezas de Sudoku generalmente se clasifican como fáciles, medios o difíciles, y los rompecabezas tienen más pistas iniciales en general, pero no siempre son más fáciles de resolver. Pero cuantificar matemáticamente la dificultad es difícil.
Ahora Ercsey-Ravasz y Toroczkai dicen que han encontrado una forma de hacerlo utilizando la teoría de la complejidad algorítmica. Señalan que es fácil diseñar un algoritmo que resuelva el Sudoku probando cada combinación de dígitos para encontrar el que funciona. Ese tipo de solución de fuerza bruta le garantiza una respuesta, pero no muy rápidamente.
En cambio, los diseñadores de algoritmos buscan formas más inteligentes de encontrar soluciones que aprovechen la estructura y las limitaciones del problema. Estos algoritmos y su comportamiento son más complejos pero obtienen una respuesta más rápidamente.
El punto central del argumento de Ercsey-Ravasz y Toroczkai es que debido a que un algoritmo refleja la estructura del problema, su comportamiento –los giros y vueltas que sigue a través del espacio de estados– es una buena medida de la dificultad del problema.
Para demostrarlo, abordan el ejemplo del Sudoku. En lugar de la solución de fuerza bruta, diseñan un algoritmo mucho más elegante que aprovecha las diversas limitaciones del rompecabezas, como el hecho de que cada fila, columna y subcuadrícula debe contener todos los dígitos del 1 al 9.
De esta manera, transforman el problema en un tipo conocido por los teóricos de la complejidad como un problema k-sat.
Comienzan insertando un conjunto aleatorio de números en la cuadrícula y siguen la trayectoria del algoritmo a través del espacio de estados mientras busca una solución. Para un problema simple, esa trayectoria es simple, como se muestra en la parte superior de las dos figuras en la parte superior de esta publicación.
Pero todo eso cambia por un problema difícil. Ercsey-Ravasz y Toroczkai prueban su algoritmo contra una cuadrícula de Sudoku con tanta fuerza que tiene su propio nombre: el rubio platino. El resultado se muestra en la mitad inferior de la figura. Es considerablemente más complejo y tarda diez veces más en resolverse.
Ercsey-Ravasz y Toroczkai dicen que para problemas difíciles, la trayectoria se vuelve caótica antes de decidirse por una solución. De hecho, el tiempo que lleva escapar de este estado caótico es una simple medida de dificultad.
Sobre esa base, crean una 'escala de Richter' de dificultad de rompecabezas basada en la tasa de escape. La escala va de 1 a 4, siendo uno el más fácil y 4 el ultraduro.
Dicen que esta escala se correlaciona sorprendentemente bien con las calificaciones humanas subjetivas con 1 correspondiente a acertijos fáciles, 2 a acertijos medianos y 3 a acertijos difíciles. El rubio platino tiene una dificultad de 3.5789.
Un corolario interesante es que no se conoce ningún Sudoku con una dificultad de 4. Y el número de pistas tampoco es siempre una buena medida de dificultad. Ercsey-Ravasz y Toroczkai dicen que probaron muchos acertijos, incluidos varios con las 17 pistas, el número mínimo y algunos con 18 pistas.
Todos estos fueron más fáciles de resolver que el rubio platino, que tiene 21 pistas. Eso es porque la dureza del rompecabezas depende no solo de la cantidad de pistas, sino también de su posición.
Una pregunta interesante ahora es si realmente existe un rompecabezas ultraduro con una dificultad de 4 y cómo se puede encontrar.
Más significativo que esto es que el método de Ercsey-Ravasz y Toroczkai se generaliza a todos los problemas de k-sat de la misma clase que el Sudoku. Por tanto, la dificultad de estos problemas puede clasificarse mediante escalas similares de tipo Richter.
Eso deja solo una pregunta: ¿cómo debería llamarse la escala de dificultad del rompecabezas? La respuesta obvia es la escala de Ercsey-Ravasz y Toroczkai o escala ERT. Cualquier otra sugerencia en la sección de comentarios a continuación.
Ref: arxiv.org/abs/1208.0370 : El caos dentro del Sudoku