Cuadrados mágicos (II): Solución Reto 2

Solución al segundo reto sobre cuadrados mágicos y ajedrez que he puesto recientemente en este blog, y en el que también se ve involucrada la programación.

El enunciado del reto decía lo siguiente: Partiendo del mismo cuadrado mágico que en el reto anterior (el que sirve para ilustrar este post), ¿Cuántas posibles soluciones al problema de las 8 reinas se esconden en él?.

Wikipedia nos dice que este problema tiene 92 soluciones, de las cuales 12 son esencialmente distintas, es decir, el resto de las soluciones existentes se pueden obtener a partir de traslaciones, simetrías y rotaciones de las 12 soluciones únicas citadas anteriormente.

La pregunta del reto se refiere al número de soluciones que se esconden en el cuadrado mágico, bien sean éstas esenciales, o bien sean variantes de las primeras por rotación, simetría o traslación.

Lógicamente, se pueden probar manualmente las 92 soluciones, pero esto, además de ser costoso, no tendría ninguna gracia, por lo que se pide resolver el reto mediante un pequeño programa escrito en el lenguaje de programación que se desee.

Solución: Decía en la segunda pista que puse para ayudar a resolver este reto que éste es "Muy fácil" si para su resolución partimos de algún programa de los existentes en Internet que obtenga todas las soluciones al problema de las 8 reinas y sólo tengamos que completar la tarea para averiguar cuáles de ellas se esconden en el cuadrado mágico del reto, es decir, en cuáles de ellas la suma de las casillas del cuadrado en las que se ubican las reinas es igual a su constante mágica (260).

Pues bien, a partir de uno de esos programas de Internet, genero un pequeño fichero con las 92 soluciones posibles (problema_8_reinas_soluciones.txt; una fila por solución con las 64 casillas del tablero, donde: "D" = casilla con Dama; "-" = casilla sin Dama) y creo un script muy simple en python para calcular la suma de las casillas en las que se ubican las reinas en cada una de las soluciones:

#

#====================================================

# SOLUCIÓN RETO 2: "LOS CUADRADOS MÁGICOS Y EL AJEDREZ (II)".

# Partiendo de un fichero con las 92 soluciones. 

#====================================================

#

cuadrado_magico=[1,2,62,61,60,59,7,8,

                             9,10,54,53,52,51,15,16,

                             48,47,19,20,21,22,42,41,

                             40,39,27,28,29,30,34,33,

                             32,31,35,36,37,38,26,25,

                             24,23,43,44,45,46,18,17,

                             49,50,14,13,12,11,55,56,

                             57,58,6,5,4,3,63,64]

f_problema_8_reinas_soluciones = open("problema_8_reinas_soluciones.txt")

s=1

for solucion in f_problema_8_reinas_soluciones:

    suma_posiciones_Damas=0

    for casilla in range(64):

        if solucion[casilla]=='D':

            suma_posiciones_Damas+=cuadrado_magico[casilla]

    if suma_posiciones_Damas==260:

        print('')

        print('****** Solución',s,'--> Suma casillas Damas =',suma_posiciones_Damas,'(constante mágica del cuadrado)')

        for i in range(8):

            print('|'+solucion[i*8:(i+1)*8]+'|')

    s+=1

f_problema_8_reinas_soluciones.close()

Lo ejecuto:

Y veo que el número de soluciones que se esconden en el cuadrado mágico del reto es cuatro. Las tres que ya indiqué en la solución del reto anterior:

Y otra que se me había "escapado":

Una vez vista la solución "Muy fácil", voy con la solución completa.

Lógicamente, una solución válida al problema de las 8 reinas será aquella que cumpla que ninguna de las Damas ocupe una casilla que se encuentre en la misma fila, columna o diagonal que la ocupada por otra.

Parto del planteamiento del problema que se realiza en Wikipedia y tomo las siguientes convenciones:

1.- Voy a numerar las filas del tablero del 0 al 7, de forma consecutiva y de arriba a abajo, y las columnas también del 0 al 7, de forma consecutiva y de izquierda a derecha.

2.- Llamaré diagonal descendente a aquellas diagonales cuya trayectoria va desde una casilla de la primera fila (fila 0) y/o primera columna (columna 0) a la casilla situada en la fila siguiente y columna siguiente de la casilla anterior, después a la casilla situada en la fila siguiente y columna siguiente de la casilla anterior, y así sucesivamente.

3.- Llamaré diagonal ascendente a aquellas diagonales cuya trayectoria va desde una casilla de la última fila (fila 7) y/o primera columna (columna 0) a la casilla situada en la fila anterior y columna siguiente de la casilla anterior, después a la casilla situada en la fila anterior y columna siguiente de la casilla anterior, y así sucesivamente.

Es decir:

Lo que se indica en la figura anterior es fácilmente comprobable y sirve para saber si una Dama se encuentra situada en una misma diagonal, tanto ascendente como descendente, que otra. Por ejemplo, si una Dama se encuentra situada en la fila 6 y columna 5, y otra en la fila 4 y columna 7, como:

a) 6 - 5 = 1 es diferente de 4 - 7 = -3, ambas Damas no se encuentran en la misma diagonal descendente.

b) 6 + 5 = 11 es igual a 4 + 7 = 11, ambas Damas sí se encuentran en la misma diagonal ascendente.

Con lo que hay que concluir que cualquier tablero con dos Damas situadas en esas dos casillas, respectivamente, no constituye una solución válida al problema de las 8 reinas.

Lo anterior, junto a que una Dama no puede ubicarse en la misma columna que ninguna otra, proporciona la base de un algoritmo realmente eficiente para comprobar si una nueva Dama se ve amenazada por otra de las colocadas anteriormente, pudiendo usarse este algoritmo para realizar una búsqueda exhaustiva en profundidad utilizando una estrategia recursiva de vuelta atrás ('backtracking') con objeto de obtener todas las posiciones de 8 Damas que resuelven el problema de las 8 reinas. ¡Qué bonito queda decirlo así en lugar de decir que voy a hacerlo mediante la fuerza bruta, es decir, "a lo bestia", probando todas las posibles soluciones mediante un refinamiento de este método que consiste en emplear un algoritmo que se llame a sí mismo y que abandone la comprobación de cada posible solución a examinar cuando detecte que ésta no es válida o confirme que se trata de una solución correcta!

Utilizaré el vector (D₀, D₁, D₂, D₃, D₄, D₅, D₆, D₇) para representar la posición de las 8 Damas en un tablero (cada índice, 0 ≤ i ≤ 7, representa una fila y el valor, 0 ≤ Di  ≤ 7, la columna en la que se ubica una Dama). Por ejemplo: el vector (4, 2, 0, 6, 1, 7, 5, 3) representaría la primera de las soluciones a este reto indicadas anteriormente en este post:

Es decir: la primera Dama estaría en la fila 0 y la columna 4; la segunda en la fila 1 y la columna 2; la tercera en la fila 2 y la columna 0; la cuarta en la fila 3 y la columna 6; la quinta en la fila 4 y la columna 1; la sexta en la fila 5 y la columna 7; la séptima en la fila 6 y la columna 5 y la octava en la fila 7 y la columna 3.

Dicho todo lo anterior, para resolver el problema de las 8 reinas lo único que hay que hacer es una búsqueda en profundidad empezando por colocar la primera Dama en la fila 0 y columna 0, la segunda en una casilla de la fila 1 no amenazada por la anterior, la siguiente en una casilla de la fila 2 no amenazada por ninguna de las anteriores, y así sucesivamente hasta que no se pueda colocar la Dama en una fila, porque todas sus casillas estén amenazadas por las anteriores, o  hasta que se coloquen las 8 Damas, es decir, se haya encontrado una solución, momento en el cuál se pasará a verificar la siguiente posible solución hasta que se agoten todas las alternativas.

Pongo un ejemplo:

Para implementar lo anterior y, después, resolver el reto de forma análoga que en la solución "Muy fácil", voy a crear un pequeño script en python que, en primer lugar, encuentre todas las soluciones al problema de las 8 reinas y las grabe en un fichero, y después, a partir de dicho fichero, encuentre las soluciones que se esconden en el cuadrado mágico del reto:

def busqueda_exhaustiva_soluciones(f):

#-------------------------------------------------------------------

# Busca todas las soluciones al problema de las 8 reinas.

#-------------------------------------------------------------------

#

    global s

    c=0

    while c<8:

        if not casilla_amenazada(f,c):

            Dama[f]=c

            if f==7:

                s+=1

                print('[+] Encontrada solución',s,'al problema de las 8 Damas:',Dama)

                for D in Dama:

                    f_problema_8_reinas_soluciones.write(str(D))

                f_problema_8_reinas_soluciones.write('\n')

            else:

               busqueda_exhaustiva_soluciones(f+1)

        c+=1

def casilla_amenazada(f,c):

#-------------------------------------------------------------------

# Verifica si una casilla está amenazada.

#-------------------------------------------------------------------

#

    i=0

    while i<f:

        if Dama[i]==c or i-Dama[i]==f-c or i+Dama[i]==f+c:

            return True

        i=i+1

    return False

#

#=======================================================

# SOLUCIÓN RETO 2: "LOS CUADRADOS MÁGICOS Y EL AJEDREZ (II)".

#=======================================================

#

global s

cuadrado_magico=[[1,2,62,61,60,59,7,8],

                             [9,10,54,53,52,51,15,16],

                             [48,47,19,20,21,22,42,41],

                             [40,39,27,28,29,30,34,33],

                             [32,31,35,36,37,38,26,25],

                             [24,23,43,44,45,46,18,17],

                             [49,50,14,13,12,11,55,56],

                             [57,58,6,5,4,3,63,64]]

f=0

Dama=[8,8,8,8,8,8,8,8]

#

# Busca todas las soluciones al problema de las 8 reinas y las graba en un fichero.

#

f_problema_8_reinas_soluciones=open("problema_8_reinas_soluciones_2.txt","w")

s=0

print('*** PASO 1: Búsqueda de todas las soluciones al problema de las 8 Damas:')

busqueda_exhaustiva_soluciones(f)

print('--- Total de soluciones encontradas al problema de las 8 Damas:',s)

f_problema_8_reinas_soluciones.close()

#

# A partir del fichero con las soluciones, calcula la suma de las 8 casillas del cuadrado

# mágico donde se colocarían las Damas de cada solución para averiguar en cuáles de

# ellas dicha suma es igual a la constante mágica (260).

#

f_problema_8_reinas_soluciones = open("problema_8_reinas_soluciones_2.txt")

s=0

print('')

print('*** PASO 2: Búsqueda de soluciones cuya suma en el cuadrado mágico es 260:')

for solucion in f_problema_8_reinas_soluciones:

    suma_posiciones_Damas=0

    for i in range(8):

        suma_posiciones_Damas+=cuadrado_magico[i][int(solucion[i:i+1])]

    if suma_posiciones_Damas==260:

        s+=1

        print('[+]',solucion.rstrip('\n'),'--> Suma casillas Damas =',suma_posiciones_Damas,

                '(constante mágica del cuadrado)')

print('--- Total de soluciones cuya suma en el cuadrado mágico es 260:',s)

f_problema_8_reinas_soluciones.close()

Lo ejecuto:

Y, tal y como se puede ver en la figura anterior, tras obtenerse y examinarse las 92 soluciones posibles al problema de las 8 reinas, se concluye que el número de soluciones que se esconden en el cuadrado mágico del reto es cuatro (las soluciones se muestran con el valor, Di, de los correspondientes vectores y son las mismas que las obtenidas utilizando la solución "Muy fácil").

******** PRÓXIMO RETO
Reto 3:   "Los cuadrados mágicos y el ajedrez (III)".