8 rainhas em c++

Gimli · 1 de novembro de 2005

Olha só, meu nome é Alexandre Magno Pimentel Pinheiro Filho, aluno do curso de engenharia da computação da UFRN e o código postado abaixo fui eu q fiz e ele saiu somente da minha cabeça xD. Só quero tirar uma dúvida pra terminar o problema

Escrevi esse texto aí em cima porque o meu professor pode olhar aqui e achar q eu colei o trabalho todinho xD. Aí eu to falando isso pra ele ver q eu não colei.

Olha só, no meu programa, eu tenho q colocar 8 rainhas num tabuleiro de xadrez de modo q nenhuma ameace as outras e além disso, o programa tem q mostrar todas as 92 soluções possíveis, e é aí q está o problema, o meu programa só encontra 4 soluções, eu não consigo encontrar o erro de jeito nenhum, e gostaria de ter uma ajudinha xD

No meu programa eu usei uma matriz 8x8, onde cada elemento da matriz é igual a 0, exceto nos elementos ocupados pela rainha, onde cada elemento é igual a 1.

Um exemplo de solução encontrada pelo meu programa é:

1 0 0 0 0 0 0 0

0 0 0 0 1 0 0 0

0 0 0 0 0 0 0 1

0 0 0 0 0 1 0 0

0 0 1 0 0 0 0 0

0 0 0 0 0 0 1 0

0 1 0 0 0 0 0 0

0 0 0 1 0 0 0 0

daí, onde tem 1, tem rainha. Aí vai o meu código

#include <iostream.h>

#include <conio.h>

int soma_horizont(int i,int tabuleiro[8][8]){

//Verifica se tem alguma rainha na linha atual

int soma_horizontal=0;

for(int a=0;a<8;a++){

soma_horizontal=soma_horizontal+tabuleiro[a];

}

return(soma_horizontal);}

int soma_vert(int j,int tabuleiro[8][8]){

//Verifica se tem alguma rainha na coluna atual

int soma_vertical=0;

for(int b=0;b<8;b++){

soma_vertical=soma_vertical+tabuleiro[j];

}

return(soma_vertical);}

int soma_diagonal_ne(int i,int j,int tabuleiro[8][8]){

//Verifica se tem alguma rainha na diagonal nordeste da posicao atual

int soma_diagonal_nordeste=0;

for(int e=0;e<=i&&e<(8-j);e++){

soma_diagonal_nordeste=soma_diagonal_nordeste+tabuleiro[i-e][j+e];

}

return(soma_diagonal_nordeste);}

int soma_diagonal_no(int i,int j,int tabuleiro[8][8]){

//Verifica se tem alguma rainha na diagonal nordeste da posicao atual

int soma_diagonal_noroeste=0;

for(int c=0;c<=i&&c<=j;c++){

soma_diagonal_noroeste=soma_diagonal_noroeste+tabuleiro[i-c][j-c];

}

return(soma_diagonal_noroeste);}

int soma_direc(int i, int j, int tabuleiro[8][8]){

//Diz se existe alguma rainha em alguma das posições citadas acima

int soma_diagonal_nordeste;

int soma_diagonal_noroeste;

int soma_vertical;

int soma_horizontal;

int soma_direcoes=0;

soma_diagonal_nordeste=soma_diagonal_ne(i,j,tabuleiro);

soma_diagonal_noroeste=soma_diagonal_no(i,j,tabuleiro);

soma_vertical=soma_vert(j,tabuleiro);

soma_horizontal=soma_horizont(i,tabuleiro);

soma_direcoes=soma_diagonal_nordeste+soma_diagonal_noroeste+soma_horizontal+soma_vertical;

return(soma_direcoes);}

int soma_tot(int tabuleiro[8][8],int i, int j){

//Complemento da funcao acima

int soma_direcoes=0;

int soma_total=0;

soma_direcoes=soma_direc(i,j,tabuleiro);

if (soma_direcoes==0)

tabuleiro[j]=1;

else

tabuleiro[j]=0;

for(int g=0;g<8;g++){

for(int h=0;h<8;h++){

soma_total=soma_total+tabuleiro[g][h];

}}

return(soma_total);}

void main(){

int tabuleiro[8][8];

int soma_total;

//Esse for abaixo tira todas as rainhas do tabuleiro

for(int n=0;n<8;n++){

for(int o=0;o<8;o++){

tabuleiro[n][o]=0;

}}

//Esse for abaixo coloca as rainhas nos seus devidos lugares

for(int i=0;i<8;i++){

for(int j=0;j<8;j++){

soma_total=soma_tot(tabuleiro,i,j);

//O comentario abaixo foi utilizado para ver cada matriz feita depois q as 4 solucoes encontradas sao exibidas

/*if((tabuleiro[0][0]==0)&&(soma_total==7)){

for(int l=0;l<8;l++){

for(int m=0;m<8;m++){

cout<<tabuleiro[l][m]<<" ";

}

cout<<"\n";}getch();cout<<"\n";}*/

//Esse bloco imprime um tabuleiro com 8 rainhas e procura outra solucao

if(soma_total==8){

for(int l=0;l<8;l++){

for(int m=0;m<8;m++){

cout<<tabuleiro[l][m]<<" ";

}

cout<<"\n";}getch();cout<<"\n";

for(int p=7;p>=0;p--){

for(int q=7;q>=0;q--){

if (tabuleiro[p][q]==1){

tabuleiro[p][q]=0;

i=p;

j=q;

p=0;

q=0;}}}}

//Esse bloco procura outra solucao se não for possivel colocar 8 rainhas no tabuleiro

else if((soma_total!=8)&&(i==7)&&(j==7)){

for(int p=7;p>=0;p--){

for(int q=7;q>=0;q--){

if (tabuleiro[p][q]==1){

tabuleiro[p][q]=0;

i=p;

j=q;

p=0;

q=0;}}}}

}}

//Esse bloco eu fiz apenas para ver qual a ultima matriz feita antes q o programa terminasse inesperadamente

for(int l=0;l<8;l++){

for(int m=0;m<8;m++){

cout<<tabuleiro[l][m]<<" ";

}

cout<<"\n";}

}

andrems · 1 de novembro de 2005

92? Não seriam 192? porque me parece que a solução tem quer múltimpla de 8, já que qualquer solução pode ser espelhada e/ou rotacionada.

Gimli · 1 de novembro de 2005

são 92 mesmo, acho q tem q ser múltiplo de 4 e não de 8, já q o tabuleiro de xadrez só tem 4 lados

knaip · 1 de novembro de 2005

Isso é um problema de GRAFOS.....Procura por grafos e 8 rainhas... tu vai achar algumas coisinhas...GRAFOS Ë OSSSO viu...ai ai ...nem quero ver isso ai ....

http://64.233.161.104/search?q=cache:R2o75...ainhas&hl=pt-BR

Bom já dei minha dica...sei que tu vai quebrar a cabeça e conseguir!

Olha que isso ai ainda é mais fácil que o problema do PASSEIO DO CAVALO!

Abraços e boa sorte

alexkidd2 · 1 de novembro de 2005

Eu odeio esses tipos problemas! O seu professor não deve gostar muito da sua turma.

Alguns livros descrevem esse problema, no livro de Adam drosdek(acho que esse o nome) foi implementado uma funcao recursiva, no qual ela botava uma peca e chama ela propria para botar outra peca mas se essa peca entrava em conflito com outra, a funcao retorna e a chamada anterior coloca a peca em outra posicao e tenta de novo.

Ta bem confusa a minha descricao, se não me engano o nome dessa tecnica se chama "caminho de volta" ou "backtracking".

Gimli · 1 de novembro de 2005

valeu pelas ajudas, to até olhando esse problema aí de grafos, mas eu já fiz uma grande parte do problema, meu algoritmo já dá 4 soluções, faltam 88 xD, o problema dele é q ele num consegue encontrar nenhuma solução se não tiver uma rainha na 1ª casa do tabuleiro, aí eu queria saber se alguem me ajudava a encontrar o erro. ele só encontra as soluções em q na primeira casa do tabuleiro tem uma rainha

knaip · 2 de novembro de 2005

Isso é um problema de GRAFOS..... se voce não encontrar um grafo pra isso ...você vai ter que fazer um a um manualmente....

I LOVE GRAFOS!

Há...é difícil mesmo.... mas tente procurar no google o codigo fonte...tenta o nbome do problema em inglês...e tipo 8 rainhas.cpp....8rainhas.pas com certeza voce acha algo!

knaip · 2 de novembro de 2005


#include <iostream>.h>
#include <conio.h>
using namespace std;
//Anca-Maria Toader 19.11.2003
//programa que resolve o problema das 8 rainhas
//apresenta a primeira soluça˜o encontrada
int ataca(int col[], int i,int j){
  if (col[i]==col[j]) return (1);
   if ((i-j)==(col[i]-col[j])) return (1);
    if ((j-i)==(col[i]-col[j])) return (1); 
        return (0);
}
int compat(int col[], int i){
  if (i==0) return (1);
   for (int j=0; j<i; ++j)
    if (ataca(col,i,j)) return(0);
     return(1);
}
int colocar(int col[], int &i) {
  while (col[i]==7) {
     if (i==1) {
       cout << "não existe solucao"<< endl;
       getch();
       exit(1);
     }
     col[i]=-1;
     --i;
   }
   ++col[i];
   return (1);
}
 int main () {
    int i,j,n=8;
    int col[8];
    cout<<"Digite a posicao da primeira rainha"<< endl;
    cin >> col[0];
    for (i=1;i<8;++i) col[i]=-1;
      i=1;
      while (i<8) {
         colocar(col,i);
         if (compat(col,i))
             ++i;
      }
      for (i=0;i<8;++i) {
         for (j=0;j<8; ++j)
            if (j==col[i]) cout << " O";
         else cout << " x";
              cout << endl;
      }
  getch();
}