Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

backtracking

Name: Anonymous 2009-06-26 14:12

hey. i'm trying to do a backtracking solution to the 8 queens puzzle. i don't know why it doesn't works. care to help?
#include <iostream>
using namespace std;
#define N 8
bool validatablero(bool (*tablero)[N], int x, int y) {
/*    for (int j=0; j<=N-1; j++) {
        for (int i=0; i<=N-1; i++) {
            if (tablero[i][j]==true) {
                if (x==i && y==j)
                    std::cout << "f";
                else
                    std::cout << "x";
            } else {
                if (x==i && y==j)
                    std::cout << "f";
                else
                    std::cout << "o";
            }
        }
        std::cout << endl;
    }
    cout << endl;*/
    for (int j=0; j<=N-1; j++) {
        for (int i=0; i<=N-1; i++) {
            if (tablero[i][j]==true && (x>7 || x<0 || y>7 || y<0 || x==i || y==j || x-i==y-j || x-i==-(y-j))) { //todos los casos en el que las reinas se podrían atacar
                return false;//si ocurre la función es falsa.
            }
        }
    }
    return true;
}   
void cuin(bool (*tablero)[N], int r, bool *t) {//pide un tablero, un contador para el número de reinas y un booleano para verificar que haya conseguido la solución
    for(int i=0; i<=N-1; i++) {
        for(int j=0; j<=N-1; j++) {//los ciclos me permiten hacer todos los movimientos posibles de las reinas
            if (validatablero(tablero, j, i)) {
                tablero[j][i]=true;//si validatablero es cierto, se puede poner la reina en esa posición
                if (r>=N) {//si el número de reinas que da r es igual al N, se consigue la solución
                    *t=true;
                    return;
                } else {//sino pasamos a la siguiente reina. aumentamos el contador en uno.
                    cuin(tablero, r++, t);
                    if (!*t)
                        tablero[j][i]=false; //si llegamos aqui y no hemos conseguido la solución, la reina no se cambia de posición
                }
            }
        }
    }
}
int main() {
    int x, y, z, w;
    bool f=false;
    bool tablero[N][N];
    for (int i=0; i<=N-1; i++) {
        for (int j=0; j<=N-1; j++) {
            tablero[i][j]=false;
        }
    }
    cuin(tablero, 1, &f);
    for (int j=0; j<=N-1; j++) { //imprimimos el tablero
        for (int i=0; i<=N-1; i++) {
            if (tablero[i][j]==true) {
                if (x==i && y==j)
                    std::cout << "f";
                else
                    std::cout << "x";
            } else {
                if (x==i && y==j)
                    std::cout << "f";
                else
                    std::cout << "o";
            }
        }
        std::cout << endl;
    }
}
thanks.

Name: Anonymous 2009-06-26 14:32

Please use the [code] tags.

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List