Lunes 14 de febrero de 2022 09:44
El problema matemático de las reinas del ajedrez que un científico de Harvard resolvió tras 150 años sin solución
Se trata del problema de las n reinas, que ha tenido a muchos matemáticos (y computadoras) rompiéndose la cabeza en busca de una solución.
Es muy probable que cuando en 1848 el ajedrecista alemán Max Bezzel concibió el problema de las ocho reinas, no se imaginara las vueltas que su planteamiento daría.
Con el tiempo, le dio paso al problema de las n reinas, que ha tenido a muchos matemáticos (y computadoras) rompiéndose la cabeza en busca de una solución.
"En realidad a Bezzel le hubiera gustado estudiar matemáticas, pero sus amigos le aconsejaron que no lo hiciera, 'porque las perspectivas para un matemático en Baviera eran terribles en ese momento'", escribió Hans Siegfried en una breve biografía.
Se hizo abogado, pero no abandonó su pasión por el ajedrez y las matemáticas y así fue cómo surgió el famoso problema que involucra a la pieza más poderosa del tablero.
Un nuevo capítulo sobre el problema de las n reinas lo escribió alguien que confiesa no ser muy bueno en el ajedrez.
El 21 de enero, The Harvard Gazette, el órgano de prensa oficial de la Universidad de Harvard, informó que uno de sus matemáticos, Michael Simkin, había resuelto "en gran medida un problema de ajedrez de 150 años".
Y es que no hay certeza de cuándo se planteó por primera vez el problema de las n-reinas, aunque todo apunta a que fue antes de 1869.
¿De qué se trata el problema?
Bezzel "podría ser considerado uno de los primeros maestros del mundo del ajedrez", escribió Max Lange, otro grande del ajedrez alemán, en un libro de 1860.
Pero más allá de su destreza en ese juego, Bezzel se distinguió por plantear problemas ingeniosos y complejos.
"Era el lado matemático del ajedrez lo que le fascinaba", escribió Siegfried en el sitio web Ansbach Chess Club.
Así fue como propuso, en una publicación sobre ajedrez, el problema de cuántas maneras se pueden colocar ocho reinas en un tablero de 8 x 8 casillas sin que se encuentren entre sí.
La reina puede avanzar tantas casillas como quiera de forma lineal ya sea horizontal, vertical o diagonalmente.
Cuentan que el problema se volvió tan popular que incluso el extraordinario matemático Carl Friedrich Gauss trató de resolverlo.
Pero fue Franz Nauck, en 1850, quien enunció la solución: las ocho reinas se pueden colocar de 92 formas.
Esa es la primer versión del problema que se generalizó como el problema de las n reinas y que Simkin lo explica así:
"Supongamos que n es un número natural, como 1,2,8,100 o un millón. Ahora, imagina un tablero de ajedrez con n filas y n columnas.
¿De cuántas maneras hay de colocar n reinas en el tablero para que no haya dos que se amenacen entre sí?
En otras palabras, ¿cuántas formas hay de colocar n reinas en el tablero para que haya una reina en cada fila, una reina en cada columna y no más de una reina en cada diagonal?
El reto lo cautivó.
Le había llegado la hora a las reinas
Para Simkin, el planteamiento tiene "características agradables", se le puede explicar rápidamente a casi cualquier persona, "incluso a los no matemáticos", y eso es algo "inusual" cuando se abordan problemas de ese tipo.
Resalta que es un ejemplo propio de la "teoría del diseño combinatorio" y dados los avances en la combinatoria probabilística, le pareció que "era el momento adecuado para atacar el problema de las reinas".
Cuenta que nunca decidió enfocarse en el problema hasta que supo que lo había resuelto.
En ese momento, se apresuró a escribirlo y el resultado lo publicó en julio de 2021, en el artículo académico The number of n-queens configurations ("El número de configuraciones de n reinas").
"El problema me había estado rondando en la cabeza durante unos cinco años, pero no había progresado mucho y me había concentrado en otros proyectos".
Tras completar su doctorado en 2020, se mudó con su familia, de Israel a Boston, para asumir una posición de posdoctorado en Harvard.
En plena pandemia, sin mucha oportunidad de socializar, las n reinas le hicieron un nuevo guiño.
"La mayor parte del trabajo fue simplemente aprender las técnicas más nuevas en combinatoria probabilística", sin ser muy consciente de que al aprenderlas llegaría a resolver el problema. "Eso vino después".
Además de darse cuenta de que era factible "atacar el problema", tuvo que "luchar para obtener correctamente una gran cantidad de detalles técnicos" que le permitieran redactar y publicar "la prueba".
El momento eureka
El matemático cuenta que el momento "eureka" se produjo cuando se dio cuenta de "la necesidad de comprender dónde 'viven' las reinas en el tablero" y ocurrió cuando bajaba por la montaña Wachusett, en Massachusetts.
Había subido con su esposa y su hija, pero cuando llegó la hora de descender, la niña estaba muy cansada y Simkin se fue por el automóvil.
"Mientras caminaba solo y reflexionaba, me di cuenta de que el principal obstáculo en los intentos anteriores era asumir que las reinas estaban distribuidas uniformemente en el tablero".
"Y en realidad, no lo están".
Comprendió "finalmente" que la clave para contar el número de configuraciones de n-reinas es primero entender cómo "se ven".
"¿Están las reinas generalmente distribuidas uniformemente en el tablero? ¿Están agrupadas en el medio? ¿En las esquinas? ¿A los lados?"
"Por cada patrón posible de cómo las reinas pudieran estar colocadas en el tablero, calculé el número de configuraciones en que las reinas se ajustan a ese patrón. De esa forma, el problema se convierte en: ¿Cuál es el patrón que permite el mayor número de posicionamientos?".
"Esto es lo que los informáticos llaman un problema de optimización convexo. En particular, puedes usar una computadora para resolverlo".
La solución
Simkin calculó que para tableros de ajedrez enormes (n por n casillas) y con muchas reinas, hay alrededor de (0,143n)^n maneras de colocar las reinas sin que ninguna se amenace.
"Supongamos que queremos saber cuántas configuraciones para 1.000.000 de reinas hay", indica el investigador.
Es decir, queremos determinar el número de formas en que se pueden colocar 1.000.000 de reinas en un tablero de 1.000.000 x 1.000.000 (de casillas) sin que se ataquen entre sí.
Para calcular ese número, que es una aproximación, debemos multiplicar 1.000.000 por 0,143 y el resultado, 143.000, lo elevamos a la potencia de 1.000.000.
"En otras palabras, multiplica 143.000 por si mismo un millón de veces. El resultado es un número muy grande, con aproximadamente cinco millones de dígitos".
Ese sería aproximadamente el número de configuraciones.
¿Lo quieres ver con un número más pequeño? Tomemos el 1.000.
En entrevista con BBC Mundo, Jesús Fernando Barbero, matemático e investigador científico del Consejo Superior de Investigaciones Científicas de España, hizo el cálculo usando la ecuación de Simkin.
Si queremos saber aproximadamente cuántas configuraciones hay para 1.000 reinas, donde está la n ponemos 1.000:
0,143 x 1000= 143 y lo elevamos a 1.000.
El docente usó su computadora y este es el resultado que arrojó:
"Me da un número enorme, de más de 2.000 dígitos, pero muy cercano al valor real del número de configuraciones que hay para un tablero de tamaño 1000x1000".
"Un avance"
Con la ecuación final de Simkin se llega a un resultado aproximado, no es el número exacto de configuraciones, pero es la cifra más cercana al número real que se puede obtener hasta ahora.
Él mismo lo indica: "para problemas de este tipo es inusual tener una solución exacta".
Para Barbero, "es un avance enorme" en lo que se refiere al planteamiento de las n-reinas.
"Estos problemas pueden tener enunciados muy simples, pero que luego pueden ser horriblemente complicados".
"El problema estaba atascado, se había conseguido entender cómo resolverlo de manera exacta hasta el número 27".
"Lo que él (Simkin) ha encontrado es un procedimiento para dar una expresión que, aunque no es exacta, comete un error que es pequeño".
"Y eso es satisfactorio: de repente se pasa de no saberse nada sobre el comportamiento del número de soluciones, a ese problema de las reinas para valores grandes, a tener una idea bastante precisa en términos cuantitativos sobre cuántas configuraciones hay para un tablero de tamaño arbitrario".
"En ese sentido, el problema está resuelto, no es una solución final, uno podría aspirar a tener una fórmula exacta que tuviera la propiedad fantástica que al darle el tamaño del tablero me diera el número exacto de configuraciones de reinas que puedo poner".
Pero aunque es teóricamente posible acercarse a una respuesta mucho más precisa, lo conseguido por Simkin es elogiado por los conocedores.
"Básicamente, lo ha hecho con una precisión que nadie había alcanzado antes", dijo Sean Eberhard, investigador posdoctoral de la Universidad de Cambridge, en un artículo de la revista Quanta. Es "de lo más realista que uno puede esperar".
Simkin dice que la razón por la que la solución tomó "tanto tiempo" es porque la misma se basa en los avances recientes que se han conseguido en el campo de las matemáticas conocido como combinatoria probabilística, especialmente en lo que se refiere al análisis de algoritmos informáticos aleatorios.
¿Por qué es importante?
"Por los métodos que (Simkin) tuvo que desarrollar para resolver un problema del que se sabía tan poco", responde Barbero.
"Los métodos pueden tener aplicación fuera del contexto en el que se han concebido y nunca se sabe qué problemas se pueden resolver con ellos, aunque no siempre haya garantía de que servirán".
Para Simkin, la importancia es una mezcla de razones:
"La principal es que hacer matemáticas es la combinación de creatividad, que se necesita para generar nuevos argumentos, y rigor, lo que significa que una vez que has probado un resultado, lo que tienes en la mano es un trozo de verdad absoluta. No puede ser refutado".
Pero también está el hecho de que con el problema de las n reinas "se mejora nuestra comprensión de los algoritmos aleatorios, que se utilizan en casi todas las aplicaciones, por ejemplo en el aprendizaje automatizado o aprendizaje de máquinas".
Y también hay conexiones con otros campos, como el del diseño de circuitos.
"¿Qué le diría a alguien que quisiera recibir el testigo de su mano y buscar una respuesta aún más exacta?", le pregunté.
"¡Buena suerte! Déjame saber cómo te va. Sería muy interesante ver qué nuevas ideas serían necesarias para mejorar los parámetros".
Si te sirven algunas pistas, el matemático nos resumió lo que usó: análisis de algoritmos aleatorios, combinatoria probabilística, entropía, análisis funcional y optimización convexa.
Y aunque dice que es un "pésimo" jugador de ajedrez y que, por ahora, descansará de las n reinas, seguramente Max Bezzel estaría muy orgulloso de él.