Thursday, September 11, 2008

El problema de las 8 damas

A mediados de marzo de 1998 me encontraba en Tijuana. Estaba sentado frente a Enricco Wizard jugando una partida informal de ajedrez. Reconozcámoslo: Wizard 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 Enricco, 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, Wizard 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)

¿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, Wizard 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, Morsa, se trata nomá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 Enricco 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 1.844674407371e+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 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 86400 segundos y si tu programa calcula, conservadoramente, 100000 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). Wizard 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 en alrededor de 5 horas, la Pentium dio con las 92 soluciones. Finalmente el problema estaba resuelto.

El software de Enricco más una versión típica en turbo Prolog 2.0, sacada de los propios ejemplos de dicha herramienta de Borland, puede pedírmela, si le interesa, a mi correo morsa@la-morsa.com. Se incluye el código fuente.

No comments: