Ocho Reinas

Ocho Reinas

Por Manuel López Michelone

Hace unos pocos años me encontraba en Tijuana, México. Estaba sentado frente a Enrique Salazar jugando una partida informal de ajedrez. Reconozcámoslo: Salazar es pésimo para este milenario juego. De hecho, toda labor que involucre de alguna u otra manera la palabra “deporte”, le causa trastornos fenomenales. Si alguien es el prototipo del antideportista es Enrique, el cual tiene como lema: “Hacer deporte es dañino. Fíjate, los deportistas siempre viven lastimados”. Pues bien, debido a que en el encuentro ajedrecístico el monarca de mi amigo estaba en serios aprietos y que el final parecía predecible, Salazar remueve de pronto las piezas del tablero y me pregunta a bocajarro: “¿Cómo era el problema de colocar las reinas en el tablero de ajedrez?”. Su táctica dio resultado porque me olvidé inmediatamente de la partida y empecé a explicarle el llamado problema de las ocho damas. Se trata simplemente de colocar en un tablero de 8x8 casillas, a 8 reinas de manera que no se ataquen entre sí (considerando cómo se mueven de acuerdo a las reglas del ajedrez). Le dije además que el problema, aparentemente había sido propuesto, por primera vez, por M Bessel, en la publicación berlinesa Schachzeitung, en 1848 (esto lo indica Miodrag Petkovic en su libro Chess and Mathemátics, ed. Dover 1997), aunque hay otros autores que piensan que el problema había sido planteado incluso antes de ese año. En 1850 incluso el príncipe de las matemáticas, Carl Gauss, estudió el asunto en cuestión.

¿Cuántas soluciones habrá? ¿Será fácil o difícil obtenerlas? Pues bien, hay 92 soluciones, aunque en realidad son 23 ya que las otras 69 son meras imágenes rotadas de cada una de las originales encontradas. No es un problema sencillo y a prueba y error una persona tarda un rato hasta que halla con una posible solución. En cómputo, por supuesto, este tema se ha atacado en cuanto lenguaje existe y es uno de esos acertijos típicos que todo alumno de las carreras afines a la computación, tarde o temprano, deben resolver.

Pues bien, Salazar empezó a meditar en la creación de un programilla que resolviera el problema de la mejor manera. Me decía con insistencia: “Debe ser fácil, Manuel, se trata no más de hallar todas las posibles permutaciones de 8 damas”. Y sí, no es muy difícil hacer un programa que resuelva esta tarea, aunque para esto se pueden seguir diversos caminos. El hecho es que unas horas después Enrique tenía una primera versión del programa de marras. Entre sus divagaciones me decía: “asumimos que el número de ciclos que el programa debe ejecutar es 2^64, lo cual es 18.4467.440.7371e+19 (algo así como 18 trillones), lo cual es un titpuchal. De todas las combinaciones que mi programa debe intentar, sólo intenta validar las que contengan 8 reinas”.

Y no le faltaba razón, pero algo no estaba funcionando. El programa no parecía dar con solución alguna y ya llevaba más de 24 horas corriendo en una olvidada Pentium a 166 MHz. Hubo que analizar la dificultad. “El problema es muy sencillo”, le dije con docto afán, “lo que pasa es que son demasiadas combinaciones las que el programa debe probar. Si, por ejemplo, un día tiene 86.400 segundos y si tu programa calcula, conservadoramente, 100.000 posiciones por segundo, tardarás varias vidas para que termine con todas las posibilidades”. Eso lo convenció y rehizo su programa. El truco fue entonces eliminar las posiciones incongruentes (más de una dama por fila o columna). Salazar halló que el total de combinaciones posibles es de 64!/8!(64-8)!, lo cual es 4.426.165.368, lo cual sigue siendo poco manejable. No obstante, como cada reina puede sólo ocupar una fila o columna, se simplifica el número de posibilidades a 8^8, lo cual da 16.777.216 alternativas. Ahora sí, la computadora personal tiene una chance de hacer la tarea en tiempo razonable.

Las soluciones empezaron a surgir poco a poco y alrededor de 5 horas después la Pentium dio con las 92 soluciones. Finalmente el problema estaba resuelto. El software de Enrique más una versión típica en turbo Prolog se los mando a quien me los pida a mi correo electrónico:

Se incluye el código fuente, por supuesto.