NRainhasEduardo

Eduardo Pinhão Mello
O problema das 8-Rainhas, ou Eight Queen Puzzle é um desafio onde devem ser posicionadas 8 rainhas em um tabuleiro de xadrez sem quem elas se ataquem. Neste trabalho o problema será generalizado para posicionar N rainhas no tabuleiro.
Como as rainhas não podem ficar em posição onde seja possível uma atacar a outra, cada rainha deve ficar em uma linha distinta da outra, e dada essa propriedade a abordagem utilizada será representar a coordenada X como a posicao na lista e a coordenada Y como o valor em cada posição.
A ideia básica para achar a solução é criar uma lista de tamanho N, selecionar cada um dos elementos dessa lista e ir testando se não há ataque de posicao em posicao, caso não haja ataque esta posição deve ser adicionada à lista de solução.
%Esta é a funcao de chamada do programa, seu parametro é o numero de rainhas desejado
%Ela imprime o resultado na tela rainha_solver(N) :rainhas(N, Q), write(Q), nl. rainhas(N,Rainhas) :gera_lista(1,N,Ns), %Gera uma lista de tamanho N rainhas(Ns,[],Rainhas). %Chama a funcao rainhas passando esta lista gerada rainhas([],Rainhas,Rainhas). %Se a lista passada for vazia retornar QS rainhas(RainhasNaoPosicionadas,RainhasSeguras,Rainhas) :seleciona(RainhasNaoPosicionadas,RainhasNaoPosicionadas1,Q), posicao_sem_ataque(RainhasSeguras,Q), %Verifica se nao ha ataque entre as RainhasSeguras e Q rainhas(RainhasNaoPosicionadas1,[Q|RainhasSeguras],Rainhas). %Concate Q a lista de
RainhasSeguras
posicao_sem_ataque(Xs,X) :posicao_sem_ataque(Xs,X,1). posicao_sem_ataque([],_,_) :- !. posicao_sem_ataque([Y|Ys],X,N) :X =\= Y+N, X =\= Y-N,
N1 is N+1, posicao_sem_ataque(Ys,X,N1). %Funcao seleciona é responsavel por percorrer a lista e retornar separadamente cada uma de seus variaveis no terceiro paramentro
%e no segundo parametro retorna a lista menos a variavel escolhida seleciona([X|Xs],Xs,X). seleciona([Y|Ys],[Y|Zs],X) :- seleciona(Ys,Zs,X).
%Esta funcao é responsavel por gerar uma lista de tamanho N com seus valores