Problema das Oito Rainhas
O trabalho tem como ênfase apresentar o problema das oito rainhas e demonstrar uma forma de solucioná-lo. Este problema tem como objetivo posicionar oito rainhas em um tabuleiro de xadrez de modo que nenhuma delas ataque nenhuma outra rainha. Será baseado nas propriedades da rainha de um jogo de xadrez.
Podemos buscar uma solução eficiente para o problema estudando as propriedades das rainhas. Uma das propriedades da rainha é que não pode haver outra rainha na linha ou na coluna onde esta se encontra. Assim, na construção do algoritmo de solução, não tentaremos posicionar uma rainha em uma posição que esteja sendo atacada. Esta mesma propriedade também vale para as diagonais em relação as rainha já posicionadas.
Uma possível solução para esse problema está exemplificada na figura abaixo.
Download do código em C++ para a solução do problema das oito rainhas:
- Desenvolvedor
Raul Joaquim Câmara dos Santos
Write a comment
Guilherme (Sunday, 05 September 2010 14:43)
voce poderia tradizir este codigo para portugol??
Mayumi (Wednesday, 16 February 2011 11:44)
opa. Vou ver se o seu está parecido com o meu. No meu algoritmo (usando C#) eu faço chamadas recursivas indo do ponto onde se quer colocar a rainha até o final da linha, se não exits outra rainha(retorno false) coloca-se a rainha aí.
Vamos ver se o meu é muito pior que o seu
rauljcs (Wednesday, 16 February 2011 19:40)
Olá Guilherme.
Trazduzir para Portugol está meio complicado.
Não pelo código em si, mas estou realmente sem tempo agora de fazer isto. Assim que der eu posto aqui pelo menos um esquema em portugol de como fazer este algoritmo.
rauljcs (Wednesday, 16 February 2011 19:42)
Olá Mayumi,
A ideia é a mesma da sua. Eu utilizei o algoritmo de backtracking, testando todas as possibilidades, passando as rainhas para todas as posições possíveis.
Se o seu funcionar, não deverá ficar pior, nem melhor que o meu (pelo menos na complexidade!)
=]
Boa sorte!
Jonas Oliveira (Sunday, 11 December 2011 14:20)
Cara, o que o return faz dentro do if(rainha[0]>7?
rauljcs (Monday, 12 December 2011 05:08)
Olá, Jonas.
O teste 'if(rainha[0]>7' na busca é para verificar se a primeira rainha já percorreu todas as posições na primeira linha. Como é um algoritmo de backtracking, se isto ocorreu, quer dizer que todos os campos possíveis já foram percorridos (já desceu até a última linha, retornou todas as possibilidades até chegar a 8 posição).
Resumindo, como são 8 posições (0 à 7), em 'if(rainha[0]>7', quer dizer que a primeira rainha está na posição 9, ou seja, o tabuleiro acabou =].
Anderson (Thursday, 23 April 2015 19:03)
Amigo, poderia me explicar o código, tá perfeito, rodou de boa aqui, mt bem organizado, mas não to entendendo. Quero aprender mesmo. Obrigado! :)
rauljcs (Thursday, 23 April 2015 19:17)
Olá, Anderson,
Usarei como base a explicação que dei a um colega por e-mail:
Eu utilizei um vetor para indicar as posições no tabuleiro das oito rainhas.
No caso, o vetor acaba servindo como uma matriz (tabuleiro).
É sabido que a rainha terá oito posições no tabuleiro em posições necessariamente diferentes.
tendo cada posição como um campo [x,y]. nas oito posições, eu sei que será [1,y1],[2,y2],[3,y3],[4,y4] ... [8,y8] . Os oito valores de y também serão numeros de 1 a 8 que não poderão se repetir.
Portanto, eu só preciso descobrir os ys, pois eu sei, com certeza, que os valores de x serão de 1 a 8. E para isso eu utilizei os índices do vetor.
então, eu usei o índice do vetor como o x. E a posição da "matriz" que cabia eu inseria no valor do campo do vetor.
Então minha matriz nada mais é do que a composição de [indice_do vetor , valor_do vetor]. Como o índice do vetor já é acessível no próprio vetor, eu só preciso armazenar os valores nos índices .
Ex:
int[] rainhas = new int[8];
se encontrei:
rainhas = [3,4,2,5,6,1,7,0];
então minha "matriz" do tabuleiro é é [0,3],[1,4],[2,2]....[7,0]
Entendido?