i tiene en casa unos cuantos ajedreces, intente hacer lo siguiente: coloque ocho damas en un tablero de manera que ninguna ataque a ninguna otra. Si lo logra, ¿puede encontrar una segunda disposición? ¿Y una tercera? ¿Cuántas hay?

Este reto tiene más de 150 años. Es la primera versión del problema matemático de las n damas, cuya solución ha anunciado Michael Simkin, investigador posdoctoral del Centro de Ciencias Matemáticas y Aplicaciones de la Universidad Harvard, en un artículo publicado en julio. En lugar de situar 8 damas en un tablero de ajedrez tradicional de 8 por 8 casillas (donde hay 92 configuraciones distintas que funcionan), el problema pregunta cuántas formas hay de colocar n damas en un tablero de n por n casillas. Podrían ser 23 damas en un tablero de 23 por 23 casillas, o 1000 en un tablero de 1000 por 1000, o cualquier número de damas en un tablero del tamaño correspondiente.

«Es [un problema] muy fácil de explicar», apunta Érika Roldán, investigadora posdoctoral del programa Marie Skłodowska-Curie en la Universidad Técnica de Múnich y la Escuela Politécnica Federal de Lausana.

Simkin ha demostrado que para tableros de ajedrez enormes, con un gran número de damas, hay en torno a (0,143n)ⁿ configuraciones. Así, en un tablero de un millón por un millón, el número de formas de disponer un millón de damas de tal modo que no se amenacen entre sí es de aproximadamente un 1 seguido de 5 millones de ceros.

El problema original en el tablero de 8 por 8 casillas apareció por primera vez en 1848, en una revista alemana de ajedrez. En 1869, ya había dado lugar al problema de las n damas. Desde entonces, los matemáticos han ido produciendo toda una serie de resultados sobre las n damas. Aunque otros investigadores habían usado simulaciones por ordenador para tratar de adivinar el resultado que halló Simkin, él es el primero que realmente lo ha demostrado.

«Básicamente, lo ha hecho con una precisión que nadie había alcanzado antes», valora Sean Eberhard, investigador posdoctoral de la Universidad de Cambridge.

Un obstáculo para resolver el problema de las n damas es que no hay formas obvias de simplificarlo. Incluso en un tablero relativamente pequeño, el número de posibles disposiciones es enorme. En un tablero más grande, hay que realizar una cantidad asombrosa de cálculos. En casos así, los matemáticos suelen tratar de encontrar algún patrón o estructura subyacente que les permita dividir los cálculos en otros más pequeños y fáciles de manejar. Pero el problema de las n damas no parecía tener ninguno.

«Una de las cosas reseñables de este problema es que, al menos a primera vista, no parece existir ninguna estructura», confirma Eberhard.

Y eso se debe a que no todas las casillas del tablero son iguales.

Para entender por qué, imaginemos de nuevo que construimos nuestra propia configuración de ocho damas. Si ponemos la primera dama cerca del centro, podrá atacar cualquier casilla situada en su fila, en su columna o en dos de las diagonales más largas del tablero. Eso deja 27 casillas seguras para nuestra siguiente dama. Pero si situamos la primera dama en un borde del tablero, solo amenaza 21 espacios, ya que las diagonales implicadas son más cortas. En otras palabras, las casillas centrales y las laterales son distintas y, como resultado, el tablero carece de una estructura simétrica que ayude a simplificar el problema.

Esa falta de estructura es la razón por la que, cuando Simkin visitó al matemático Zur Luria en la Escuela Politécnica Federal de Zúrich hace cuatro años para colaborar en el problema, comenzaron abordando el problema «toroidal» de las n-damas, que es más simétrico. En esa versión modificada, el tablero de ajedrez se «enrolla» sobre sí mismo en los bordes, como un toroide: si una pieza cae por la derecha del tablero, reaparece por la izquierda.

El problema toroidal parece más sencillo, debido a su simetría. A diferencia del tablero clásico, todas las diagonales tienen la misma longitud y cada dama puede atacar el mismo número de casillas: 27.

Simkin y Luria trataron de construir configuraciones en el tablero toroidal usando una receta en dos partes. En cada paso colocaban una dama al azar, eligiendo cualquier casilla con la misma probabilidad siempre que estuviera disponible. A continuación, bloqueaban todos los espacios que podía atacar. Analizando cuántas opciones tenían en cada paso, esperaban calcular un límite inferior, un mínimo absoluto para el número de configuraciones posible. Esa estrategia es lo que se llama un algoritmo voraz (greedy) aleatorio y se ha empleado para resolver muchos otros problemas en el ámbito de la combinatoria.

La simetría del tablero toroidal les dio a Simkin y Luria algo a lo que aferrarse. Pero la versión toroidal cambia libertad por simetría, y eso acabó por hacerles tropezar. En el tablero tradicional, la mayoría de las damas atacan menos de 27 espacios, lo que proporciona más flexibilidad para construir una configuración.

«Los confines de un tablero de ajedrez real resultan realmente útiles», comenta Eberhard.

Los avances de Simkin y Luria en el problema toroidal se vieron frenados cuando no lograron encontrar espacio para las últimas damas en una determinada configuración. Al toparse con ese obstáculo, pasaron a ocuparse de otros proyectos. Pero, con el tiempo, Simkin comprendió que la estrategia que había fracasado en el problema toroidal era muy adecuada para el tablero de ajedrez normal.

«Dos o tres años después de habernos dado por vencidos, me di cuenta de que para el problema clásico, en realidad, resultaba mucho más fácil», rememora Simkin.

Así que Simkin y Luria trataron de completar su configuración en un tablero de ajedrez normal (de cualquier dimensión). Descubrieron que en general podían lograrlo ajustando algunas de las piezas que ya habían colocado.

«Basta con mover un par de damas, quitar una aquí y meter dos nuevas allá», explica Nick Wormald, de la Universidad Monash.

Pero la falta de simetría del problema clásico volvió a frenar a los investigadores. El algoritmo voraz aleatorio trata todos los espacios del tablero por igual y es más apropiado para los problemas muy simétricos, donde todas las casillas son iguales. Cuando las damas se sitúan al azar en un tablero estándar, el algoritmo no distingue entre las casillas centrales y las laterales.

Debido a esta cortapisa, al final Simkin y Luria solo pudieron mejorar el límite inferior que ya se conocía para el problema. Publicaron sus resultados el pasado mes de mayo.

Pero Simkin siguió dándole vueltas al problema, incluso después de trasladarse de Israel a Boston el pasado otoño, tras acabar su doctorado en la Universidad Hebrea de Jerusalén. Al final, se percató de que podía adaptar el algoritmo voraz aleatorio al entorno asimétrico de un tablero de ajedrez estándar de n por n casillas. En concreto, comprendió que, en una configuración de n damas, las piezas tenían muchas más probabilidades de ocupar ciertas casillas que otras… así que la estrategia que él y Luria habían empleado, donde elegían cada casilla con la misma probabilidad, no tenía sentido.

«Entendí que era posible aprovechar esas asimetrías», señala Simkin.

Como las damas en la mitad del tablero son las que más espacios atacan, la mayoría de las configuraciones presentan más damas en los bordes del tablero que cerca del centro. Simkin descubrió que esos efectos empezaban a dominar sobre el resto de posibilidades cuando el tablero tiene más de 100 casillas de lado. Solo tenía que averiguar el peso exacto que había que asignar a cada casilla al situar las damas al azar.

«Supongamos que ponemos todas las configuraciones de damas una sobre otra, y entonces nos preguntamos: ¿con qué frecuencia se ocupa esta posición concreta?», ilustra Nati Linial, profesor de la Universidad Hebrea y director de tesis de Simkin.

Para entender a grandes rasgos cómo se dispondrían las damas, Simkin dividió el tablero de ajedrez de n por n casillas en distintas secciones, cada una de ellas con miles de casillas. Luego, en vez de especificar exactamente en qué casillas había damas, adoptó una perspectiva más general: ¿cuántas damas había en cada sección?

Una vez que averiguó cómo asignar las damas por secciones, volvió a las técnicas que había empleado con Luria. Solo que esta vez podía usarlas de manera más precisa: en vez de colocar las damas completamente al azar, eligió los espacios donde había más damas con mayor frecuencia. Eso le permitió determinar una fórmula para el número mínimo de configuraciones válidas.

Por último, Simkin demostró que esa fórmula era algo más que un mínimo: era casi un valor exacto. Para ello empleó una estrategia conocida como el método de la entropía.

Supongamos que tenemos una configuración válida de n damas y queremos compartirla con alguien. Si la otra persona sabe más o menos el aspecto que tiene una configuración, ¿cuánta información adicional necesitamos transmitirle para que pueda reconstruirla con precisión?

Simkin logró calcular un número máximo de configuraciones examinando el número de casillas no atacadas tras desvelar la posición de cada nueva dama adicional. Ese valor máximo coincidía casi perfectamente con el mínimo, lo que permitió a Simkin llegar a la conclusión de que prácticamente había determinado el número de configuraciones posibles para n damas. Su prueba arrojó mucha luz sobre este problema clásico.

Es probable que los matemáticos sigan jugando con el problema y tratando de acercar aún más esos límites máximo y mínimo, aunque el resultado de Simkin ha eliminado la mayor parte del misterio.

Es «de lo más realista que uno puede esperar», admite Eberhard.

El artículo de Simkin se enmarca en una reciente explosión de actividad en torno a problemas similares. De hecho, hace un par de semanas, Candida Bowtell y Peter Keevash, de la Universidad de Oxford, encontraron una solución análoga para el problema toroidal de las n damas. Y hay muchos otros problemas abiertos en combinatoria que podrían aprovechar las ideas de estos artículos. Simkin espera que su trabajo haya aumentado las probabilidades de que se produzcan tales aplicaciones adicionales.

«Lo interesante son los métodos», concluye Simkin. «Tratamos constantemente de hacer que nuestras herramientas sean más potentes. Con este trabajo, espero haberlo conseguido.»

Leila Sloman

Artículo traducido por Investigación y Ciencia con el permiso de QuantaMagazine.org, una publicación independiente promovida por la Fundación Simons para potenciar la comprensión pública de la ciencia.

Referencia: «The number of n-queens configurations», Michael Simkin en arXiv:2107.13460 [math.CO], 28 de julio de 2021; «The n-queens problem», Candida Bowtell y Peter Keevash en arXiv:2109.08083 [math.CO], 16 de septiembre de 2021.