Problem: Place N queens on an N×N chessboard so that no two queens threaten each other.

Approach:

1. Use a recursive function to place queens one by one.
2. For each placement, check if it’s safe.
3. If it’s safe, place the queen and move to the next row.

Code Example:

#include <iostream>
#include <vector>

using namespace std;

bool isSafe(vector<string>& board, int row, int col, int n) {
    for (int i = 0; i < col; i++)
        if (board[row][i] == 'Q')
            return false;
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
        if (board[i][j] == 'Q')
            return false;
    for (int i = row, j = col; i < n && j >= 0; i++, j--)
        if (board[i][j] == 'Q')
            return false;
    return true;
}

void solveNQueensUtil(vector<vector<string>>& solutions, vector<string>& board, int col, int n) {
    if (col == n) {
        solutions.push_back(board);
        return;
    }
    for (int i = 0; i < n; i++) {
        if (isSafe(board, i, col, n)) {
            board[i][col] = 'Q';
            solveNQueensUtil(solutions, board, col + 1, n);
            board[i][col] = '.';
        }
    }
}

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> solutions;
    vector<string> board(n, string(n, '.'));
    solveNQueensUtil(solutions, board, 0, n);
    return solutions;
}

int main() {
    int n = 4;
    vector<vector<string>> solutions = solveNQueens(n);
    for (const auto& board : solutions) {
        for (const auto& row : board) {
            cout << row << endl;
        }
        cout << endl;
    }
    return 0;
}