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 15:41


getAtLoc board r c | r < 0 || c < 0         = 0
                   | r >= length board      = 0
                   | c >= length (board!!r) = 0
                   | otherwise              = board !! r !! c

-- checks if the top row to be placed above board is safe for a queen in column h
isSafe [] _          = True
isSafe board       h = all (==0) (map (!!h) board) &&
                       all (==0) (foldl (flip $ (:).getFromDiagnal (+)) [] [0..length (head board)-h-1]) &&
                       all (==0) (foldl (flip $ (:).getFromDiagnal (-)) [] [0..h-1])
                 where getFromDiagnal f q = getAtLoc board q $ f h (q+1)

insertAt ys j n = insertAt' ys 0
            where insertAt' [] q          = [j]
                  insertAt' xs q | q == n = j:xs
                  insertAt' (x:xs) q      = x:insertAt' xs (q + 1)

queens boardSize = queens' boardSize
               where queens' 1 = possibleBoards []
                     queens' s = newBoards
                             where boardsTilNow = queens' $ s - 1
                                   newBoards = boardsTilNow >>= possibleBoards
                     emptyList = replicate (boardSize - 1) 0
                     possibleBoards b = map (:b) $ possibleRows b
                     possibleRows b   = map (insertAt emptyList 1) $ possibleSpaces b
                     possibleSpaces b = filter (isSafe b) [0..boardSize - 1]


There are 92 possible solutions to the 8x8 queens puzzle.

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