#include <stdbool.h> 
#include <stdio.h> 
#include <iostream>
using namespace std;
/* A utility function to print solution */
void printSolution(int **board,int N)
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            printf(" %d ", board[i][j]);
        printf("\n");
    }
}

/* A utility function to check if a queen can
   be placed on board[row][col]. Note that this
   function is called when "col" queens are
   already placed in columns from 0 to col -1.
   So we need to check only left side for
   attacking queens */
bool isSafe(int **board, int row, int col,int N)
{
    int i, j;

    /* Check this row on left side */
    for (i = 0; i < col; i++)
        if (board[row][i])
            return false;

    /* Check upper diagonal on left side */
    for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
        if (board[i][j])
            return false;

    /* Check lower diagonal on left side */
    for (i = row, j = col; j >= 0 && i < N; i++, j--)
        if (board[i][j])
            return false;

    return true;
}

/* A recursive utility function to solve N
   Queen problem */
bool solveNQUtil(int **board, int col,int N)
{
    if (col >= N)
        return true;
    for (int i = 0; i < N; i++) {
        if (isSafe(board, i, col,N)) {
            board[i][col] = 1;
            if (solveNQUtil(board, col + 1,N))
                return true;

            board[i][col] = 0; 
        }
    }
    return false;
}
bool solveNQ()
{
    int N;
    int** board;
    cout << "Enter N for NxN chessboard";

    if (solveNQUtil(board, 0,N) == false) {
        printf("Solution does not exist");
        return false;
    }

    printSolution(board,N);
    return true;
}

// driver program to test above function 
int main()
{
    solveNQ();
    return 0;
}