# N Queens problem

#### N Queens problem implemented using backtracking algorithm

N Queens problem: Place N queens on a chessboard of dimension N x N i.e N rows x N columns, such that no two queens can attack each other.
Consider below chessboards of size 4, the board on the left side is valid in which no two queens can attack each other; whereas the board on the right is invalid. N Queens placement idea :
The idea behind placing NQueens on a chessboard is as below.
a) Try placing the queen on (and starting from) the 0’th column of the chessboard.
b) For every selected column, try placing the queen from the 0’th row of the chessboard such that it does not attack any of the already placed queens.

For every possible valid placement of the queen on the chessboard the next empty column is selected; hence while checking if a queen on a (row, column) is correctly placed we check only the left side of the column. i.e
a) We check if there is already a queen on the left in the row.
b) We check if there is already a queen on the upper diagonal.
c) We check if there is already a queen on the lower diagonal.

If for a selected column, a queen cannot be placed in the current row, try placing it in the next row. If the queen cannot be placed in any of the rows of the selected column, backtrack and try placing the previously placed queen in the next row before trying to place the current one again.

Algorithm : N Queens

bool IsBoardOk (chessboard, row R, column C) {

If there is a queen ‘Q’ positioned to the left of column C in row R.
return False;

If there is queen ‘Q’ positioned on the upper left diagonal
return false;

If there is queen ‘Q’ positioned on the lower left diagonal
return false;

return true;
}

PlaceNQueens ( chessboard, column )

a) If the chessboard size equals column number (chessboard.size() == column)
All the queens are correctly placed on the chessboard. Display the chessboard.

b) Else try placing the queen on each row of the column and check if the chessboard remains valid.
for ( row = 0; row < chessboard.size(); row++ )
Place the queen ‘Q’ at position [ row, column ] and check if the chessboard remains valid
chessboard [ row ] [ column ] = ' Q ‘
Check if ( IsBoardOk ( chessboard, row, column ) == true ) {
Try placing another queen ‘Q’ in the next column.
PlaceNQueens ( chessboard, column + 1 ) ;
}
Chessboard was not valid hence revert
chessboard [ row ] [ column ] = ' . ‘

Time complexity of N queens algorithm: For finding a single solution where the first queen ‘Q’ has been assigned the first column and can be put on N positions, the second queen has been assigned the second column and would choose from N-1 possible positions and so on; the time complexity is O(N * (N-1) * (N-2) * … 1). i.e The worst-case time complexity is O(N!). Thus, for finding all the solutions to the N Queens problem the time complexity runs in polynomial time.

Python

Python program for solving the N Queens problem using backtracking.

Java

Java program for solving the N Queens problem using backtracking.

C++ program for solving the N Queens problem using backtracking.

``````#include<iostream>
#include<string>
#include<vector>

using namespace std;
int boardcnt = 0;

bool IsBoardOk (vector<string>& chessboard, int row, int col) {

// Check if there is a queen 'Q' positioned to the left of column col
// on the same row.
for (int c=0; c<col; c++) {
if (chessboard[row][c] == 'Q') {
return false;
}
}

// Check if there is queen 'Q' positioned on the upper left diagonal
for (int r=row-1, c=col-1; r >= 0 && c >= 0; r--, c--) {
if (chessboard[r][c] == 'Q') {
return false;
}
}

// Check if there is queen 'Q' positioned on the lower left diagonal
for (int r=row+1, c=col-1; c >= 0 && r<chessboard.size(); r++, c--) {
if (chessboard[r][c] == 'Q') {
return false;
}
}

return true;
}

void DisplayBoard (vector<string>& chessboard) {
for (auto& row : chessboard) {
for(auto& ch : row) {
cout << ch << " ";
} cout << endl;
}
}

void PlaceNQueens (vector<string>& chessboard, int col) {

// If all the columns have a queen 'Q', a solution has been found.
if (col >= chessboard.size()) {
cout << endl << "Board " << ++boardcnt << endl;
cout << "========================" << endl;
DisplayBoard(chessboard);
cout << "========================" << endl;

}  else {

// Else try placing the queen on each row of the column and check if the chessboard remains OK.
for (int row=0; row<chessboard.size(); row++) {

chessboard[row][col] = 'Q';

if (IsBoardOk(chessboard, row, col) == true) {
//Chess board was OK, hence try placing the queen 'Q' in the next column.
PlaceNQueens(chessboard, col + 1);
}

chessboard[row][col] = '.'; // As previously placed queen was not valid, restore '.'
}
}
}

int main() {

vector<string> chessboard;
int N;

cout << "Enter chessboard size : ";
cin >> N;

for(int i=0; i<N; i++) {
string row(".", N);
chessboard.push_back(row);
}

// Start placing the queen 'Q' from the 0'th column.
PlaceNQueens(chessboard, 0);

return 0;
}
``````

Output of N Queens problem based on backtracking implemented in C++

``````Enter chessboard size : 1

Board 1
========================
Q
========================

Enter chessboard size : 4

Board 1
========================
. . Q .
Q . . .
. . . Q
. Q . .
========================

Board 2
========================
. Q . .
. . . Q
Q . . .
. . Q .
========================

``````