N Queens

    1#include <bits/stdc++.h>
    2 
    3using namespace std;
    4 
    5int n, ans = 0;
    6void dfs(int row, vector<bool>& col, vector<bool>& dp, vector<bool>& dm){
    7    if(row == n) { // placed all the queens(one valid solution)
    8        ans++;
    9        return;
    10    }
    11    //try to place a queen in each column of the current row
    12    for(int i = 0; i < n; i++){
    13        int right_up = row + i;
    14        int left_down = row - i + n - 1; // + n - 1 to adjust for negative index
    15        //check if it is a valid placement
    16        if(!col[i] && !dp[right_up] && !dm[left_down]){
    17            //place a queen and mark placed
    18            col[i] = true; dp[right_up] = true; dm[left_down] = true;
    19            dfs(row + 1, col, dp, dm); // move on to the next queen
    20            //recite 
    21            col[i] = false; dp[right_up] = false; dm[left_down] = false;
    22        }
    23 
    24    }
    25}
    26int main(){
    27    ios::sync_with_stdio(0);
    28    cin.tie(0);
    29    cin >> n;
    30    vector<bool> col(n, false), dp(2 * n - 1, false), dm(2 * n - 1, false);
    31    dfs(0, col, dp, dm);
    32    cout << ans << '\n';
    33    return 0;
    34}