#include <iostream>
using namespace std;

// N define el tamaño del tablero.
// Como es el problema de las nueve reinas,
// usamos un tablero de 9x9.
const int N = 9;

// Esta matriz representa el tablero de ajedrez.
// 0 = casilla vacía
// 1 = hay una reina colocada
int tablero[N][N];


// ------------------------------------------------------------
// Función: esSeguro
// Verifica si es posible colocar una reina en la posición
// (fila, col) sin que sea atacada por otra reina.
// ------------------------------------------------------------
bool esSeguro(int fila, int col)
{
    int i, j;

    // Revisar si existe una reina en la misma fila
    // hacia la izquierda (columnas anteriores).
    // No revisamos hacia la derecha porque aún
    // no hemos colocado reinas allí.
    for(i = 0; i < col; i++)
        if(tablero[fila][i])
            return false;

    // Revisar diagonal superior izquierda.
    // Si encontramos una reina, la posición no es válida.
    for(i = fila, j = col; i >= 0 && j >= 0; i--, j--)
        if(tablero[i][j])
            return false;

    // Revisar diagonal inferior izquierda.
    for(i = fila, j = col; i < N && j >= 0; i++, j--)
        if(tablero[i][j])
            return false;

    // Si no hay conflictos, la posición es segura.
    return true;
}


// ------------------------------------------------------------
// Función: resolverReinas
// Implementa el algoritmo de backtracking.
// Intenta colocar una reina en cada columna.
// Si una posición no funciona, retrocede (backtrack)
// y prueba otra posición.
// ------------------------------------------------------------
bool resolverReinas(int col)
{
    // Si ya colocamos reinas en todas las columnas,
    // significa que encontramos una solución válida.
    if(col >= N)
        return true;

    // Intentar colocar la reina en cada fila
    // de la columna actual.
    for(int i = 0; i < N; i++)
    {
        // Verificar si la posición es segura.
        if(esSeguro(i, col))
        {
            // Colocamos la reina.
            tablero[i][col] = 1;

            // Intentamos colocar la siguiente reina
            // en la siguiente columna.
            if(resolverReinas(col + 1))
                return true;

            // Si no se pudo encontrar solución,
            // quitamos la reina (backtracking)
            // y probamos otra fila.
            tablero[i][col] = 0;
        }
    }

    // Si ninguna fila funcionó en esta columna,
    // devolvemos false para retroceder.
    return false;
}


// ------------------------------------------------------------
// Función: imprimirTablero
// Muestra el tablero en pantalla.
// Q representa una reina.
// . representa una casilla vacía.
// ------------------------------------------------------------
void imprimirTablero()
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            if(tablero[i][j] == 1)
                cout << "Q ";
            else
                cout << ". ";
        }
        cout << endl;
    }
}


// ------------------------------------------------------------
// Función principal del programa.
// Inicializa el tablero y llama al algoritmo
// que resuelve el problema.
// ------------------------------------------------------------
int main()
{
    // Inicializamos todo el tablero en 0
    // (sin reinas).
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            tablero[i][j] = 0;

    // Intentamos resolver el problema
    // comenzando por la columna 0.
    if(resolverReinas(0))
    {
        cout << "Solucion encontrada:\n\n";
        imprimirTablero();
    }
    else
    {
        cout << "No existe solucion.\n";
    }

    return 0;
}