n queen

#include <iostream>
#include <vector>
using namespace std;

// Function to print the solution board
void printSolution(const vector<vector<int>>& board, int N) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << (board[i][j] == 1 ? "Q" : ".") << " ";
        }
        cout << endl;
    }
}

// Function to check if it's safe to place a queen at board[row][col]
bool isSafe(const vector<vector<int>>& board, int row, int col, int N) {
    // Check this column in previous rows
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 1) return false;
    }

    // Check upper-left diagonal
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 1) return false;
    }

    // Check upper-right diagonal
    for (int i = row - 1, j = col + 1; i >= 0 && j < N; i--, j++) {
        if (board[i][j] == 1) return false;
    }

    return true;
}

// Recursive function to solve the N-Queens problem
bool placeQueens(vector<vector<int>>& board, int row, int N) {
    // If all queens are placed
    if (row == N) return true;

    // Try placing a queen in all columns for the current row
    for (int col = 0; col < N; col++) {
        if (isSafe(board, row, col, N)) {
            board[row][col] = 1;  // Place queen
            if (placeQueens(board, row + 1, N)) return true;  // Recur to place the next queen
            board[row][col] = 0;  // Backtrack
        }
    }

    return false;  // If no place is found, return false
}

// Function to solve N-Queens and print the solution
void solveNQueens(int N) {
    vector<vector<int>> board(N, vector<int>(N, 0));  // Initialize N x N board with 0

    if (placeQueens(board, 0, N)) {
        printSolution(board, N);
    } else {
        cout << "No solution exists!" << endl;
    }
}

int main() {
    int N;
    cout << "Enter the value of N: ";
    cin >> N;

    solveNQueens(N);

    return 0;
}