Problema:
Se quiere saber todas las formas en la que se pueden colocar N reinas en un tablero de NxN sin que ninguna de estas sea capaz de atacar a otra.
(Cada solucion se almacenara en un archivo llamado "solucionR")
Respuesta:
#include <iostream>
#include <fstream>
using namespace std;
class reina{
public:
bool **validar;
char **tablero;
fstream enter;
int contador;
int N;
reina(int n){
N = n;
validar = new bool*[N];
tablero = new char*[N];
for(int i=0; i<N; i++){
validar[i] = new bool[N];
tablero[i] = new char[N];
for(int j=0; j<N; j++){
validar[i][j] = false;
tablero[i][j] = '.';
}
}
enter.open("solucionR.txt", fstream::out);
enter << "Soluciones en tablero de " << N << "*"<< N <<endl<<endl;
contador = 0;
}
void solucion(int x, int y, int n){
tablero[x][y] = 'R';
bloquear(x, y);
if(n==N) mostrar();
else{
for(int i=0; i<N; i++){
if(validar[i][y+1]==false) solucion(i, y+1, n+1);
}
}
quitarRellenar(x, y);
}
void bloquear(int x, int y){
int aux1, aux2;
//horizontal
aux2 = y;
aux1 = 0;
while(aux1<N){
validar[aux1][aux2] = true;
aux1++;
}
//vertical
aux2 = 0;
aux1 = x;
while(aux2<N){
validar[aux1][aux2] = true;
aux2++;
}
//diagonal negativa
aux1 = x; aux2 = y;
while(aux1>0 && aux2>0){
aux1--; aux2--;
}
aux1++; aux2++;
while(aux1<N && aux2<N){
validar[aux1][aux2] = true;
aux1++; aux2++;
}
//diagonal positiva
aux1 = x; aux2 = y;
while(aux1<N && aux2>0){
aux1++; aux2--;
}
aux1--; aux2++;
while(aux1>=0 && aux2<N){
validar[aux1][aux2] = true;
aux1--; aux2++;
}
}
void quitarRellenar(int x, int y){
tablero[x][y] = '.';
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
validar[i][j] = false;
}
}
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
if(tablero[i][j]=='R') bloquear(i, j);
}
}
}
void mostrar(){
contador++;
enter << "Solucion N# "<< contador <<endl;
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
enter << tablero[i][j] << " ";
}
enter <<endl;
}
enter <<endl;
}
void todoSol(){
for(int i=0; i<N; i++){
solucion(i, 0, 1);
}
enter.close();
}
};
int main(){
int n;
cout <<"Introduzca numero de reinas"<<endl;
cin >> n;
reina *Queen = new reina(n);
Queen->todoSol();
cout <<"Se ha creado el archivo 'solucionR'"<<endl;
return 0;
}
Muy buen programa, pero hubieran puesto comentarios ya que casi no se entiende.
ResponderEliminarHola no se si me podrias ayudar a entender ese codigo, yo solo se java y no entiendo c++
EliminarHola no se si me podrias ayudar a entender ese codigo, yo solo se java y no entiendo c++
EliminarQue lastima que este blog se haya abandonado:
ResponderEliminarTenia muchas preguntas sobre este codigo para reformarlo y probar hasta cuantas N Reinas se podría resolver.
Si lees esto, contestame. Ya que soy muy novato en C++ pero tengo un algoritmo mejorado para resolver el problema de N Reinas pero no se como implementarlo en C++.