domingo, 26 de agosto de 2012

Recursividad N reinas C++

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;
}

4 comentarios:

  1. Muy buen programa, pero hubieran puesto comentarios ya que casi no se entiende.

    ResponderEliminar
    Respuestas
    1. Hola no se si me podrias ayudar a entender ese codigo, yo solo se java y no entiendo c++

      Eliminar
    2. Hola no se si me podrias ayudar a entender ese codigo, yo solo se java y no entiendo c++

      Eliminar
  2. Que lastima que este blog se haya abandonado:

    Tenia 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++.

    ResponderEliminar