#include <iostream>
using namespace std;

class Reina {
	public: 
	// constructor
		Reina (int c, Reina* v);
		 
	// métodos de búsqueda de soluciones:
		bool buscaSolucion();
		bool avanzar();
	// método para imprimir resultados:
		void print();
	
	private:
	// atributos
		int fila;
		const int columna;
		Reina* vecina;
	// método interno
		bool puedeAtacar(int testfila, int testcolumna);
};

Reina::Reina (int c, Reina* v): columna(c), vecina(v) {
	fila = 1;	// empieza a buscar una solución desde la primera fila
}

bool Reina::buscaSolucion() {
	// si está bien colocada (nadie la puede atacar) ya es una solución:
	if ( !vecina || !vecina->puedeAtacar(fila, columna) ) return true;
		
	// si no, intenta avanzar a una posición donde no la puedan atacar:
	if ( avanzar() ) return true;	
		
	return false; // no se ha encontrado una solución
}

bool Reina::avanzar() {	
	if ( fila < 8 ) {	// avanzar una posición y mira si hay solución
		fila++;
		return buscaSolucion();
	}

	// si no puede avanzar, intenta que lo hagan las vecinas:
	if ( !vecina || !vecina->avanzar() ) 	return false;
	// Si ponemos la misma condición que en Java:
	//if ( vecina && !vecina->avanzar() )		return false;
	// con esa condición cuando la reina 1 se queda sin filas no devuelve falso
	// y al explorar todas las soluciones el programa se mete en bucle infinito
	// (no sale del while que hay en el main() de este programa C++)
	
	// habiendo avanzado la vecina, 
	// vuelve a la primera fila para encontrar una nueva solución:
	fila = 1;	
	return buscaSolucion();	
}

bool Reina::puedeAtacar(int testfila, int testcolumna) {
		int diferenciaColumnas = testcolumna - columna;
		if (	(fila == testfila) ||						// en la misma fila
				(fila + diferenciaColumnas == testfila) ||	// o en una diagonal
				(fila - diferenciaColumnas == testfila))
			return true;
		
		// mira si es atacable por alguna vecina
		return ( vecina && vecina->puedeAtacar(testfila, testcolumna) );
}

void Reina::print() {
	// primero lista las vecinas
	if (vecina)	vecina->print();
	// y luego su propia posición 
	cout << "columna " << columna << " fila " << fila << '\n';
}


int main() {
	int cuenta = 0; // cuenta de todas las posibles soluciones
	Reina* ultimaReina = 0;
	
	for (int i = 1; i <= 8; i++) {
		// crea una reina
		ultimaReina = new Reina(i, ultimaReina);
		// e intenta colocarla sin que nadie le ataque
		if ( !ultimaReina->buscaSolucion() ) cout << "No hay solución\n" ;
	}	
		
	cout << "Soluciones al problema de las 8 reinas" << endl;
	do {
		cout << "\nSolución " << ++cuenta << " ==============" << endl;
		ultimaReina->print();
	}
	while ( ultimaReina->avanzar() );
}