N reinas

[naza]

Hola que tal quisiera saber si alguien me podria ayudar, estoy tratando dse solucionar el problema de las N reinas, en un tienpo eficiente,
las N reinas consiste en poner N reinas en un tablero de NxN sin que se maten entre si,
se comen se estan en la misma fila, columna y diagonal.
ya hice el de 8 reinas(el clasico) con N! de complejidad con back,,,pero lo quiero para 100.000 reinas mas o menos
alguien tiene  una idea...ese no anda
gracias

[CID]

Lo que estas pidiendo es el algoritmo?
Porqué no colocas el que ya hiciste y lo vamos completando entre todos?

Saludos.

[naza]

Código

#include<stdio.h>
#include<conio.h>
#include<iostream.h>
 
#define TRUE 1
#define FALSE 0
#define N 8 /* las reinas que quiero colocar*/
//---------------------------------------------------------
/*cada posicion del arreglo es una reina y tambien su columna
  y cargo el arreglo con su respectiva fila
  ejemplo:
          quiero la reina i en la fila 3 columna i -> arreglo[i]=3;
  con esta representacion nos ahorramos la validacion
  por columna
  */
int reinas[N];
int tablero[N][N];
int cont_sol=0;
//---------------------------------------------------------
void Inicializar(){
for(int i=1; i <= N ; i++)
 reinas[i]=0;
}
//---------------------------------------------------------
void Imprimir_arreglo(){
cout<<"\t";
for(int i=1;i<=N;i++)
cout<<reinas[i]<<" ";
cout<<"\n";
}
//---------------------------------------------------------
void Borrar_solucion(){
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
 tablero[i][j]=0;
}
//---------------------------------------------------------
/*Me fijo si en el arreglo no tiene elementos repetidos, des esta
forma logro la restriccion por fila. Con la otra condicion
me fijo la restriccion de la diagonal*/
int Poda (int hijo,int i)
{
    for(int j=1; j <= i; j++)
    {
       if((reinas[j]==hijo) || (abs(hijo - reinas[j]) == abs(i-j)))
              return TRUE;
    }
    return FALSE;
}
//---------------------------------------------------------
void Back_reinas(int i){
if(i == N+1)
{
   cout<<"Es solucion:\t";
   cont_sol=cont_sol+1;
   Imprimir_arreglo();
   return;
}
for(int hijo=1; hijo <= N;hijo++)
{
 if(!Poda(hijo,i))
 {
   reinas[i]= hijo;
   Back_reinas(i+1);
   reinas[i]= 0;
 }
}
}
//---------------------------------------------------------
void main(){
clrscr();
Inicializar();
Back_reinas(1);
cout<<"\n"<<cont_sol<<" "<<"soluciones.\n";
getch();
}

------------------------------------------------------------------------------------
funciona barbaro esta hecho en builder 6 fijate en N que hay 8 te tiene que dar las 92 soluciones posible, bueno despues pònele digamos 100000 y va a andar pero no termina mas,, esa es la idea reducir el tiempo que t da todas las soluciones posibles
gracias de nuevo por la atencion

[naza]

y nadie tira una idea?   parece que es dificil el problema ja,,,, estoy en el orno .. lo mejore un toque despues lo coloco igual gracias, esto me hace sentir groso jajajaja
saludos