5

De que se trata el reto:
Hola gente, no se si conocen el reto de las 8 reinas. Si no lo conocen se los explico en breve. Tenemos un tablero de ajedrez como cualquier otro y se tiene que colocar 8 reinas en el tablero sin que se ataquen. Si quieres ver más a fondo de que se trata este reto aqui te dejo un enlace:https://es.wikipedia.org/wiki/Problema_de_las_ocho_reinas

Bueno lo que quería hacer era un programa que dará una solución a este problema. Ya tengo el código pero me ha surgido un error en la linea 58:

Error:

Traceback (most recent call last):
  File "main.py", line 148, in <module>
    while(solucionado()):
  File "main.py", line 56, in solucionado
    if(tablero[i][j].getReina() != False):
AttributeError: 'NoneType' object has no attribute 'getReina'

Un resumen de lo que hace el programa:
Lo que hace el programa es crear una clase casilla que va contener la variable booleana 'afectado' que indica si la casilla está amenazada por una reina o no, otra variable también booleana llamada 'reina' que indica si hay una reina en el objeto 'casilla' que la contiene. Después revisa casilla por casilla mirando si no esta afectada por una reina y si no tiene contenida una reina, para poder poner una. Cuando pone una, afecta(cambia el valor 'afectado' del objeto casilla a 'True') todas las casillas que están involucradas con esa casilla que contiene la reina para que en esas casillas no se pueda poner una reina. Bueno ya saben, así hasta que ya allá puesto todas las reinas. Ah! bueno una cosa, si el numero de casillas libres es menor al numero de reinas que faltan por poner, significa que la estructura de reinas que hay ahora en el tablero esta mal, entonces lo que hace es afectar(cambia el valor 'afectado' del objeto casilla a 'True') la primera casilla con una reina que tiene esa estructura y después reinicia todas las casillas al los valores por defecto: 'False', exceptuando la casilla ya explicada(la primera casilla que contiene una reina en la estructura anterior de reinas) anteriormente para que la siguiente estructura de reinas que se coloque no sea igual a la anterior y así pueda ir probando todos los casos hasta encontrar la solución. Si no lo entendieron, estudien un poco más mi código así podrán entenderlo un poquito mejor. ¡Saludos!

Código fuente:

class Casilla_: #Cada casilla del tablero de ajedrez 
    afectado = False #Afectacion de la casilla por otra casillas
    reina = False #Si la casilla tiene reina o no
    def __init__(self,afectado = False,reina = False): 
        self.afectado = afectado 
        self.reina = reina

    def setAfectado(self,afectado): 
        self.afectado = afectado

    def getAfectado(self): 
        return self.afectado
    def setReina(self,reina):
        self.reina = reina
    def getReina(self): 
        return self.reina

tablero = [] #Creacion de la matriz
for i in range(0,8):
    tablero.append([None])
    for j in range(0,8):
        tablero[i].append(None)

#Inicializacion de objetos casillas
def reinicializacionTablero():
    global tablero 
    for i in range(0,len(tablero)):
        for j in range(0,len(tablero)):
            tablero[i][j] = Casilla_(False,False) 
def casillasLibres():
    libres = 0
    for i in range(len(tablero)):
       for i in range(len(tablero)):
           #Casilla vacia
           if(tablero[i][j].afectado == False and tablero[i][j].reina 
           == False):
             libres += 1 
    return libres #Retorna el numero de casillas libres             
def primeraReina():
    pos = ""
    for i in range(8):
        for j in range(8):
            if(tablero[i][j].getReina()):
                pos = str(i) + str(j)
                return pos
def solucionado():
    num_reinas = 0
    for i in range(8):
        for j in range(8):
            if(tablero[i][j].getReina() != False):
                num_reinas +=1
    if(num_reinas == 8):
        return False
    else:
        return True             

reinas = 8
primerPos = ""

def afectarCasillas(row,column):
    b = False
    referenceRow = 0; referenceColumn = 0 
    #up (afect)
    referenceRow = row; referenceColumn = column
    while(b == False):
        referenceRow -=1 #Se decrementa los indices
        try: 
            tablero[referenceRow][referenceColumn].afectado = True
        except IndexError as e:
            b = True
            break
    b = False       
    #down (afect)
    referenceRow = row; referenceColumn = column 
    while(b == False):
        referenceRow -=1 #Se decrementa los indices
        try: 
            tablero[referenceRow][referenceColumn].afectado = True
        except IndexError as e:
           b = True
           break    
    b = False
    #left (afect)
    referenceRow = row; referenceColumn = column 
    while(b == False):
         referenceColumn -= 1 #Se decrementa los indices
        try: 
            tablero[referenceRow][referenceColumn].afectado = True
        except IndexError as e:
            b = True
            break   
    b = False
    #rigth (afect)
    referenceRow = row;#Asignacion de los indices
    while(b == False):
        referenceColumn += 1 #Se decrementa las los indices
        try: 
            tablero[referenceRow][referenceColumn].afectado = True
        except IndexError as e:
            b = True
            break
        b = False
        #up-left (afect)
        referenceRow = row; referenceColumn = column 
        while(b == False):
             referenceRow -=1; referenceColumn -= 1 
             try: 
                 tablero[referenceRow][referenceColumn].afectado=True
             except IndexError as e:
                 b = True   
        b = False
        #up-rigth (afect)
        referenceRow = row; referenceColumn = column 
    while(b == False):
        referenceRow +=1; referenceColumn += 1 
        try: 
            tablero[referenceRow][referenceColumn].afectado = True
        except IndexError as e:
            b = True
            break
    b = False
    #down-left (afect)
    referenceRow = row; referenceColumn = column 
    while(b == False):
        referenceRow +=1; referenceColumn -= 1 
        try: 
            tablero[referenceRow][referenceColumn].afectado = True
        except IndexError as e:
            b = True    
            break
    b = False
    #down-rigth (afect)
    referenceRow = row; referenceColumn = column 
    while(b == False):
        referenceRow +=1; referenceColumn += 1 
        try: 
            tablero[referenceRow][referenceColumn].afectado = True
        except IndexError as e:
            b = True    
            break                               
 #Bucle principal
 while(solucionado()):
     num_libres = casillasLibres() #Asigna a num_libres el numero de 
     casillas vacias que hay en el tablero
     bel = 't'
     while(reinas > 0): 
         for i in range(8):
            for j in range(8):
                #Caso de casilla libre
                if(tablero[i][j].getAfectado()==False and tablero[i] 
                [j].getReina()==False):
                    tablero[i][j].setReina(True) 
                    afectarCasillas(i,j) #Afecta todas las casillas relacionadas con la casilla actual
                    reinas -= 1 
                else:
                    num_libres = casillasLibres() 
                    if(num_libres > reinas):
                        bel = 'f'
                        primerPos = primeraReina() 
                        break               
            if(bel == 'f'):
                break
        if(bel == 'f'):
            break   
    if(bel == 'f'):
        reinicializacionTablero()
        fil = int(primerPos[0])
        col = int(primerPos[1])
        tablero[fil][col].setAfectado(True);
        reinas = 8
    else:
        continue    
def imprimiendoSolucion():
    print("SOLUCION: ")
    for i in range(0,8):
        for j in range(0,8):
            if(tablero[i][j].getReina()):
                print(" [R] ",end="")
            else:
                print(" [ ] ",end="")
        print(""); print("")            
imprimiendoSolucion() #Imprime toda la solcion de la matriz
1
  • 5
    Tu matriz tablero al inicio de tu ciclo while principal sigue siendo una matriz de elementos None. Debes inicializarla antes de esto para llenarla de objetos Casilla_, por ejemplo llamado a reinicializacionTablero
    – FJSevilla
    Commented el 9 jun. 2018 a las 9:42

2 respuestas 2

2

Hay una solución más simple al problema de las ocho reinas y es usar un método recursivo con backtracking.

El método recursivo es el siguiente: Se recibe el tablero y se pide poner ocho reinas. Se busca secuencialmente una casilla desocupada, no amenazada por otras reinas. Si se encuentra, se pone una reina y luego se invoca recursivamente la misma función para poner n-1 reinas.

El backtracking aparece cuando no se logran colocar otra reinas. En tal caso, se deshace la última reina y se busca otra casilla más adelante, desocupada, reintentando colocarla y comprobar si así se logran las ocho reinas. Si finalmente no se encuentra ninguna casilla apropiada, se retrocede un nivel y se prueba a reubicar la reina anterior, y asi sucesivamente.

La función free(row, col) chequea que la casilla no este afectada por alguna otra reina. La única parte complicada es recorrer las diagonales que pasan por esa casilla.

def free(row, col):
        """ Determina si la casilla rowxcol está libre de ataques.

        @param row: Fila
        @param col: Columna
        @return: True si la casilla está libre de ataques por otras reinas.
        """
        for i in range(8):
            if tablero[row][i] == 'R' or tablero[i][col] == 'R':
                return False

        if row <= col:
            c = col - row
            r = 0
        else:
            r = row - col
            c = 0
        while c < 8 and r < 8:
            if tablero[r][c] == 'R':
                return False
            r += 1
            c += 1

        if row <= col:
            r = 0
            c = col + row
            if c > 7:
                r = c - 7
                c = 7
        else:
            c = 7
            r = row - (7 - col)

        while c >= 0 and r < 8:
            if tablero[r][c] == 'R':
                return False
            r += 1
            c -= 1

        return True

def agregar_reina(n):
        """ Agrega n reinas al tablero.

        @param: n El número de reinas a agregar
        @return True si se pudo agregar las reinas requeridas
        """
        if n < 1:
            return True

        for idx_row in range(8):
            for idx_col in range(8):
                if free(idx_row, idx_col):
                    tablero[idx_row][idx_col] = 'R'
                    if agregar_reina(n-1):
                        return True
                    else:
                        tablero[idx_row][idx_col] = '_'

        return False


tablero = []
for i in range(8):
    tablero.append(['_'] * 8)
agregar_reina(8)
for row in tablero:
    print(*row)

produce

R _ _ _ _ _ _ _
_ _ _ _ R _ _ _
_ _ _ _ _ _ _ R
_ _ _ _ _ R _ _
_ _ R _ _ _ _ _
_ _ _ _ _ _ R _
_ R _ _ _ _ _ _
_ _ _ R _ _ _ _
0

Espero que no te moleste. Me agrado tu código y pues es el único bueno que logre encontrar para un trabajo de la U así que lo tome y agregue unas cosas para poder hacerlo con n reinas.

def free(row, col, n):
    """ Determina si la casilla rowxcol está libre de ataques.

    @param row: Fila
    @param col: Columna
    @return: True si la casilla está libre de ataques por otras reinas.
    """
    for i in range(n):
        if tablero[row][i] == 'R' or tablero[i][col] == 'R':
            return False

    if row <= col:
        c = col - row
        r = 0
    else:
        r = row - col
        c = 0
    while c < n and r < n:
        if tablero[r][c] == 'R':
            return False
        r += 1
        c += 1

    if row <= col:
        r = 0
        c = col + row
        if c > n-1:
            r = c - (n-1)
            c = n-1
    else:
        c = n-1
        r = row - ((n-1) - col)

    while c >= 0 and r < n:
        if tablero[r][c] == 'R':
            return False
        r += 1
        c -= 1

    return True

def agregar_reina(n,m):
    """ Agrega n reinas al tablero.

    @param: n El número de reinas a agregar
    @return True si se pudo agregar las reinas requeridas
    """
    if m < 1:
        return True

    for idx_row in range(n):
        for idx_col in range(n):
            if free(idx_row, idx_col, n):
                tablero[idx_row][idx_col] = 'R'
                if agregar_reina(n,m-1):
                    return True
                else:
                    tablero[idx_row][idx_col] = '▢'

    return False

n= int(input("DIGITE NUMERO DE REINAS: "))
m=n
tablero = []
for i in range(n):
    tablero.append(['▢'] * n)
agregar_reina(n,m)
for row in tablero:
    print(*row)

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.