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.
#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.