N_QUEEN(BACKTRACKING)

N_QUEEN SOLN(MY WRITTEN BAD SOLn i t hink) 

#include<bits/stdc++.h>

using namespace std;

bool isSafe(int row,int idx,vector<vector<int>>&checksafe){

    if(checksafe[row][idx]==0)return true;

    else return false;

}

void makeUnSafe(int row,int idx,vector<vector<int >>&checksafe){

    int n=checksafe.size();

    for(int i=0;i<n;i++)checksafe[row][i]++;

    for(int i=0;i<n;i++)checksafe[i][idx]++;

    checksafe[row][idx]--;

    int r1=row+1,r2=row-1,r3=row-1,r4=row+1;

    int i1=idx+1,i2=idx-1,i3=idx+1,i4=idx-1;

    while(r1<n&&i1<n){

        checksafe[r1++][i1++]++;

    }

    while(r2>=0&&i2>=0){

        checksafe[r2--][i2--]++;

    }

    while(r3>=0&&i3<n){

        checksafe[r3--][i2++]++;

    }

    while(r4<n&&i4>=0){

        checksafe[r4++][i4--]++;

    }

}

void makeSafe(int row,int idx,vector<vector<int>>&checksafe){

    int n=checksafe.size();

    for(int i=0;i<n;i++)checksafe[row][i]--;

    for(int i=0;i<n;i++)checksafe[i][idx]--;

    checksafe[row][idx]++;

    int r1=row+1,r2=row-1,r3=row-1,r4=row+1;

    int i1=idx+1,i2=idx-1,i3=idx+1,i4=idx-1;

    while(r1<n&&i1<n){

        checksafe[r1++][i1++]--;

    }

    while(r2>=0&&i2>=0){

        checksafe[r2--][i2--]--;

    }

    while(r3>=0&&i3<n){

        checksafe[r3--][i2++]--;

    }

    while(r4<n&&i4>=0){

        checksafe[r4++][i4--]--;

    }

}

void printboard(vector<vector<int>>&board){

    for(int i=0;i<board.size();i++){

        for(int j=0;j<board.size();j++){

            cout<<board[i][j]<<" ";

        }

        cout<<endl;

    }

}

void N_queen(int row,vector<vector<int>>&board,vector<vector<int>>&checksafe){

    if(row==board.size()){

                printboard(board);

                cout<<"----------------"<<endl;

                return;

    }

    for(int i=0;i<board.size();i++){

        

        if(isSafe(row,i,checksafe)){

            board[row][i]=1;

            makeUnSafe(row,i,checksafe);

            N_queen(row+1,board,checksafe);

            makeSafe(row,i,checksafe);

            board[row][i]=0;

            

        }

    }

}

int main(){

    int n=4;

    vector<vector<int>>board(n,vector<int>(n,0));

    vector<vector<int>>checksafe(n,vector<int>(n,0));

    N_queen(0,board,checksafe);

}

OPTIMAL_APPRAOCH(CHECK IN O(1) TIME)

#include<bits/stdc++.h>

using namespace std;

bool isSafe(int row,int col,vector<bool>&checkcol,vector<bool>&checkleft,vector<bool>&checkright){

    int n=checkcol.size()-1;

    if(checkcol[col]||checkleft[row+col]||checkright[col-row+n])return false;

    return true;

}

void makeUnsafe(int row,int col,vector<bool>&checkcol,vector<bool>&checkleft,vector<bool>&checkright){

    int n=checkcol.size()-1;

    checkcol[col]=1;

    checkleft[row+col]=1;

    checkright[col-row+n]=1;

}

void makeSafe(int row,int col,vector<bool>&checkcol,vector<bool>&checkleft,vector<bool>&checkright){

    int n=checkcol.size()-1;

    checkcol[col]=0;

    checkleft[row+col]=0;

    checkright[col-row+n]=0;

}

void printboard(vector<vector<int>>&board){

    for(int i=0;i<board.size();i++){

        for(int j=0;j<board.size();j++){

            cout<<board[i][j]<<" ";

        }

        cout<<endl;

    }

    cout<<"--------------------------------------------"<<endl;

}

void N_QUEEN(int row,vector<vector<int>>&board,vector<bool>&checkcol,vector<bool>&checkleft,vector<bool>&checkright){

    if(row==board.size()){

        printboard(board);

        return;

    }

    for(int i=0;i<board.size();i++){

        if(isSafe(row,i,checkcol,checkleft,checkright)){

            board[row][i]=1;

            makeUnsafe(row,i,checkcol,checkleft,checkright);

            N_QUEEN(row+1,board,checkcol,checkleft,checkright);

            makeSafe(row,i,checkcol,checkleft,checkright);

            board[row][i]=0;

        }

    }

}

int main(){

    int n=4;

    int k=2*n-1;

    vector<vector<int>>board(n,vector<int>(n,0));

    vector<bool>checkcol(n,0),checkright(k,0),checkleft(k,0);

    N_QUEEN(0,board,checkcol,checkleft,checkright);

}