//
//  main.cpp
//  N Queen
//
//  Created by Himanshu on 22/04/22.
//

#include <iostream>
#include <cstdio>
#define N 8


// This function prints the solution
void printSolution(int board[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf(" %d ", board[i][j]);
        }
        printf("\n");
    }
}

// A function to check if a queen can
// be placed on board[row][col].
bool check(int board[N][N], int row, int col) {
    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 function to solve N Queen problem
bool solveUtil(int board[N][N], int col)
{
    // Base case: If all queens are placed then return true
    if (col >= N) {
        return true;
    }
    
    for (int i = 0; i < N; i++) {
        
        // Check if the queen can be placed
        if (check(board, i, col)) {
            board[i][col] = 1;
            
            // recur to place rest of the queens
            if (solveUtil(board, col + 1)) {
                return true;
            }
            
            board[i][col] = 0; // BACKTRACK
        }
    }
    
    return false;
}


int main() {
    int board[N][N] = {0};
    
    if (solveUtil(board, 0) == false) {
        printf("Solution does not exist");
    } else {
        printf("Solution:\n");
        printSolution(board);
    }
    
    return 0;
}