RecorteX

Solución al problema de las Ocho Reinas, en el que usamos backtracking.

descargar
 
#include <cstdlib>
#include <iostream>
 
using namespace std;
 
// Constantes
const int MAX = 8; // Cambiar el 8 por N para obtener problemas con N reinas y un tablero de NxN
 
// Tipos
typedef int TReinas reinas [MAX];
 
// Cabeceras de funciones y procedimientos
void OchoReinas(TReinas &r, int fila);
bool EsSeguro(TReinas r, int fila, int prueba);
void PintarTablero(TReinas r);
 
//Programa principal
int main () {
	TReinas reinas;
 
	OchoReinas(reinas,0);
}
 
// Implementación de funciones y procedimientos
void OchoReinas(TReinas &r, int fila) {
	int prueba;
	
	for(prueba = 0; prueba < MAX; prueba++) {
		if(EsSeguro(r,fila,prueba)) {
			r[fila] = prueba;
			if(fila == (MAX-1)) {
				PintarTablero(r);
			}
			else {
				OchoReinas(r,fila+1);
			}
		}
	}
}
 
bool EsSeguro(TReinas r, int fila,int prueba) {
	int i;
	
	for(i = 1; i < MAX; i++) {
		if((r[fila-i] == prueba) || (r[fila-i] == prueba-i) || (r[fila-i] == prueba+i)) {
			return false;
		} 
	}
	return true;
}
 
void PintarTablero(TReinas r) {
	
	cout << "---------------------------------" << endl;
	for(int fila = 0; fila < MAX; fila++) {
		for(int i = 0; i < r[fila]; i++) {
			cout << "|   ";
		}
		cout << "| X ";
		for (int j = (r[fila] + 1); j < MAX; j++) {
			cout << "|   ";
		}
		cout << "|" << endl << "---------------------------------" << endl;
	}
	cout << endl;
}