famous_n_queen_problem

n_queen_problem.cpp

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

/**
 * Given nxn board place n queen on this board so that they dont attack each other. One solution is to find
 * any placement of queens which do not attack each other. Other solution is to find all placements of queen
 * on the board.
 *
 * Time complexity O(n^n)
 * Space complexity O(n*n)
 */
void display(vector<string> &board , int n)
{
    cout<<"displaying board...\n" ;
    for(int i = 0 ; i<n ; i++)
    {
        for(int j = 0 ; j<n ; j++)
            cout<<board[i][j]<<" " ;
        cout<<endl ;
    }
}
bool isValid(vector<string > &board , int row , int col , int n)
{
        //check if the column had a queen before.
        for (int i = 0; i < row; ++i)
            if (board[i][col] == 'Q')
                return false;

        //check if the 135° diagonal had a queen before.
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j)
            if (board[i][j] == 'Q')
                return false;

        //check if the 135° diagonal had a queen before.
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j)
            if (board[i][j] == 'Q')
                return false;
        return true;
}
bool solveNQueen_helper(vector< string > &board , int row , int n)
{
    //base case
    if(row == n)
        return true ;

    //recursive case
    for(int col = 0 ; col < n ; col++)
    {
        if(isValid(board , row , col , n))
        {
            board[row][col] = 'Q' ;
            bool place_next_queen = solveNQueen_helper(board , row+1 , n) ;
            if(place_next_queen)
                return true ;
            board[row][col] = '.' ;//backtrack
        }
    }
    return false ;
}
void solveNQueen(int n)
{
    //define a board of size n*n and initialize each cell with '.'
    vector< string > board(n , string(n , '.')) ;
    bool flag = solveNQueen_helper(board , 0 , n) ;
    if(flag == false)
        cout<< "n queens could not be placed .. \n" ;
    else
        display(board , n) ;
}

int main()
{
    int n ;
    cout<<"enter the value of n :" ;
    cin>>n ;
    cout<<endl ;

    solveNQueen(n) ;
    return 0;
}