N Queens

#include <bits/stdc++.h>
using namespace std;

bool isCellSafe(int row, int col, vector<vector<bool> > &chess){
    // check column (|), if the current queen is able to kill a queen in the same column or not
    for(int i = 0; i < row; i++){
        if(chess[i][col]){
            return false;
        }
    }

    // check upper left diagonal (\), if the current queen is able to kill a previous queen in the left diagonal or not
    for(int i = row - 1, j = col - 1; (i >= 0 && j >= 0); i--, j--){
        if(chess[i][j]){
            return false;
        }
    }

    //check upper right diagonal (/), if the current queen is able to kill a previous queen in the right diagonal or not
    for(int i = row - 1, j = col + 1; (i >= 0 && j < chess[0].size()); i--, j++){
        if(chess[i][j]){
            return false;
        }
    }

    // currently placed queen would not be able to kill any queen placed before it, so safe to place the queen there
    return true;
}

void placeNQueens(int row, vector<vector<bool> > &chess, vector<string> &configurations){
    //base case (print any configuration that reaaches base case, as we would only reach base case, if we are able to place all the N queens in N rows, as we have explored ONLY VALID options at each row, and we have made the decisions for all N rows, if our current state/row = N [we started from row 0, row 1 ...... row (n - 1) = N rows])
    if(row == chess.size()){
        string validConfig = "";
        for(int i = 0; i < chess.size(); i++){
            for(int j = 0; j < chess[0].size(); j++){
                if(chess[i][j]){
                    // cout << '[' << i << ']' << '[' << j << ']' << '-';
                    validConfig += "[" + to_string(i) + "]" + "[" + to_string(j) + "]" + "-";
                }
            }
        }
        // cout << '\n';
        configurations.push_back(validConfig);
        return;
    }
    /*
    level/state = row
    options/transition = columns
    */
    //explore all the options in each row (queen sits in which column for a given row r)
    for(int col = 0; col < chess[row].size(); col++){
        // we will place the current queen in column col, only if it does not kill any queen placed before it in row - 1 rows
        if(isCellSafe(row, col, chess)){
            chess[row][col] = true;
            placeNQueens(row + 1, chess, configurations);
            chess[row][col] = false;
        }
    }
}

int main() {
    // your code goes here
    int n;
    cin >> n;

    //chessboard n X n
    vector<vector<bool> > chess(n, vector<bool>(n, false));

    // Valid Positions
    vector<string> configurations;
    placeNQueens(0, chess, configurations);

    //print configurations
    cout << "Total configurations: " << configurations.size() << ':' << '\n';
    for(auto config : configurations){
        cout << config << '\n';
    }
}