Ocho
Reinas
En
Matemáticas, Aplicaciones Informáticas, Sistemas Expertos,
Inteligencia Artificial, etc., es frecuente plantear como ejercicio
el problema de cómo colocar ocho reinas en un tablero de ajedrez de
manera que ninguna de ellas se amenace entre sí, teniendo en cuenta
que una reina puede desplazarse en sentido vertical, horizontal y en
diagonal tantas casillas como permita el tablero.
Dado
que un tablero de ajedrez tiene ocho filas y ocho columnas, resulta
que cada reina tiene 8x8 = 64 posiciones posibles. Si tenemos que
colocar ocho reinas y cada una de ellas tiene 64 posiciones posibles,
nos da un resultado de 64x64x64x64x64x64x64x64, lo que supone un
total de 281.474.976.710.656 combinaciones posibles, un cálculo
impracticable en un tiempo razonable incluso para los ordenadores más
modernos. Luego, además, habría que ir rechazando todas aquellas
combinaciones que no cumplieran la premisa de no amenazarse entre sí.
-
Un primer análisis nos permitiría ahorrar trabajo al ordenador
considerando que dos reinas no pueden estar en la misma casilla, por
lo que la primera reina tendría 64 posiciones posibles, la segunda
63, la tercera 62, etc., con lo que quedarían “sólo” un total
de 64x63x62x61x60x59x58x57 = 178.462.987.637.760 combinaciones
posibles.
-
El siguiente paso a considerar sería que dos reinas no pueden estar
en la misma columna, porque se amenazarían entre sí, por lo que la
primera reina podría estar en cualquiera de las 8 casillas de la
primera columna, la segunda reina en cualquiera de las 8 casillas de
la segunda columna, y así sucesivamente. Tendríamos entonces un
total de 8x8x8x8x8x8x8x8 = 16.777.216 posibilidades, un trabajo sin
duda mucho más asequible para el ordenador.
-
A continuación deberíamos tener en cuenta que dos reinas tampoco
podrían estar en la misma fila, porque se amenazarían igualmente entre sí .
Es decir, la primera reina podría ocupar cualquiera de las 8
casillas de la primera columna, la segunda reina sólo podría ocupar
7 casillas de la segunda columna porque de lo contrario estarían en
distinta columna pero en la misma fila , la tercera reina sólo
podría ocupar 6 casillas de la tercera columna, etc. Esto hace un
total de 8x7x6x5x4x3x2x1 = 40.320 combinaciones posibles, cifra mucho
más fácil de manejar por un sistema informático.
-
Y hay aún una última consideración a tener en cuenta, y es que
aunque las reinas estén en distintas casillas, en distintas filas y
en distintas columnas, deben estar también en distintas diagonales,
dado que las reinas pueden desplazarse también en diagonal, lo que
simplifica el algoritmo de cálculo de manera considerable.
El
resultado final es que sólo hay 12 soluciones posibles al problema
planteado, resultado al que se llega con un algoritmo informático
(implementado con lenguajes de programación como C++, Java, Python,
Prolog, etc.) que hemos simplificado simplemente analizando el
problema antes de empezar a trabajar en él, con lo que hemos
convertido un problema inicialmente irresoluble en un problema de
fácil solución.
Del
mismo modo, la vida diaria nos plantea problemas que a veces se nos
antojan irresolubles, pero que una vez analizados y divididos
adecuadamente, resultan no serlo tanto.
----------------------
Los
enemigos de mis enemigos son mis amigos.
