Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como resolver o problema das N rainhas usando backtracking?

+1 voto
654 visitas
perguntada Mai 11, 2016 em Ciência da Computação por danielcajueiro (5,661 pontos)  

O problema das \(N\) rainhas pode ser descrito da seguinte forma:

Aloque \(N\) rainhas em um tabuleiro de xadrez de forma que duas rainhas não ataquem uma a outra (não existem duas rainhas na mesma linha, coluna ou diagonal).

Compartilhe

2 Respostas

+2 votos
respondida Mai 11, 2016 por danielcajueiro (5,661 pontos)  

Uma implementação simples usando Python:

import numpy as np

def is_legal(Q,r,theColumn):
    for i in range(r):
        if((Q[i]==theColumn)or(Q[i]==theColumn+r-i)or(Q[i]==theColumn-r+i)):
            return False
    return True        

def recursive_n_queens(Q,r):
    n=len(Q)
    if(r==n):
        print Q
        pass
    else:
        for j in range(n):
            if(is_legal(Q,r,j)):
                Q[r]=j
                recursive_n_queens(Q,r+1)
if __name__ == '__main__':
    n=8
    # It is obvious that each queen is in each row
    Q=np.empty([n]) # It keeps the column of each row
    r=0
    recursive_n_queens(Q,r)
+1 voto
respondida Jul 10, 2016 por PRosa (61 pontos)  
editado Ago 4, 2016 por PRosa

Este é um outro exemplo.

global n
global chamadas
chamadas=0

def poeRainha(mat,rainhas,posicao):
    global n,chamadas
    chamadas+=1

    if len(rainhas)==n:
        imprimeSolucao(mat)
        return rainhas
    elif len(rainhas)==0 and posicao>=n:
        return None   # sem solução

    # abandona se deixou linha em branco      
    abandonar=False    
    if len(rainhas)>0:
       ultPosicao=rainhas[len(rainhas)-1] 
       if posicao > ultPosicao+n:     
          abandonar=True

    # encontra próxima célula disponível    
    while not abandonar and posicao < n*n and not pode(mat,posicao):
       posicao+=1

    if not abandonar and pode(mat,posicao):
        rainhas.append(posicao)
        l,c=linhaColuna(posicao)
        mat[l][c]=1    # coloca a rainha
        poeRainha(mat,rainhas,posicao+1)
    else:
        if posicao>n*n-1 or abandonar:
           if len(rainhas)>0:
               ultTentativa=rainhas.pop()   # retira a última colocada
           else:
               ultTentativa=0

           lUlt,cUlt=linhaColuna(ultTentativa)
           mat[lUlt][cUlt]=0
           poeRainha(mat,rainhas,ultTentativa+1)

    return rainhas     

def linhaColuna(posicao):
    global n
    l=posicao//n    
    c=posicao-(l*n)    
    return (l,c)

def imprimeSolucao(mat):
    global chamadas
    print "Chamadas recursivas:",chamadas    
    print "Solução:"    
    for i in mat:
        print i

def pode(mat,posicao):

    global n
    if posicao >= n*n:
       return False

    l=posicao//n    
    c=posicao-(l*n)    

    #conflito na linha?
    conflito=False
    for i in range(n):
        if mat[l][i]==1:
            conflito=True
            break
    #conflito na coluna?
    if not conflito:
        for i in range(n):
            if mat[i][c]==1:
                conflito=True
                break
    # conflito na diagonal \?
    if not conflito:
        i,j=l,c
        while j>0 and i>0:
            i-=1
            j-=1
            if mat[i][j]==1:
                conflito=True
                break
    # conflito na diagonal / ?
    if not conflito:
        i,j=l,c
        while i>0 and j<n-1:
            i-=1
            j+=1
            if mat[i][j]==1:
                conflito=True
                break

    return not conflito

if __name__ == "__main__":
    global n

    n=11
    mat= [ [0 for i in range(n)] for j in range(n)]  

    rainhas=[]
    rainhas=poeRainha(mat,rainhas,0)

    print "Posições:", rainhas
...