Singles Salamanca

La red single gratuita de Salamanca

Ocho Reinas

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.

http://templar-alquimia.blogspot.com.es/2016/02/ocho-reinas.html