N_Queen_Problem.cpp

#include <iostream>
using namespace std;

bool isSafe(int** arr, int x, int y, int n)
{
    for(int row=0;row<i;row++)
    {
        if(arr[row][y]==1)
        {
            return false;
        }
    }
    int row=x;
    int col=y;
    while(row>=0 && col>=0)
    {
        if(arr[row][col]==1)
        {
            return flase;
        }
        row--;
        col--;
    }

    int row=x;
    int col=y;
    while(row>=0 && col<n)
    {
        if(arr[row][col]==1)
        {
            return flase;
        }
        row--;
        col++;
    }
    return true;
}

bool nQueen(int** arr, int x, int y)
{
    if(x>=n)
    {
        return true;
    }

    for(int col=0;col<n;col++)
    {
        if(isSafe(arr,x,col,n)){
            arr[x][col]=1;

            if(nQueen(arr,x+1,n)){
                return true;
            }

            arr[x][col]=0    //backtraking
        }
    }
    return false;
}

int main()
{
    int n;
    cout<<"Enter the value of n \n";
    cin>>n;
    int** arr=new int*[n];
    for(int i=0;i<n;i++)
    {
        arr[i]=new int[n];
        for(int j=0;j<n;j++)
        {
            arr[i][j]=0;
        }
    }

    if(nQueen(arr,0,n)){
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                cout<<arr[i][j]<<endl;
            }
        }
    }

    return 0;
}