# Solving N Queens Problem Using Backtracking

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

• We check if there is already a queen on the left in the row.
• We check if there is already a queen on the upper diagonal.
• 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, then
Â Â Â Â Â Â Â Â  return False;

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

Â Â Â Â  If there is queen ‘Q’ positioned on the lower left diagonal, then
Â Â Â Â Â Â Â Â  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.

Implementation of N Queens problem using backtracking

``````from typing import List # For annotations

boardcnt = 0

def IsBoardOk (chessboard : List, row : int, col : int) :

# Check if there is a queen 'Q' positioned to the left of column col on the same row.
for c in range(col) :
if (chessboard[row][c] == 'Q') :
return False

# Check if there is queen 'Q' positioned on the upper left diagonal
for r, c in zip(range(row-1, -1, -1), range(col-1, -1, -1)) :
if (chessboard[r][c] == 'Q') :
return False

# Check if there is queen 'Q' positioned on the lower left diagonal
for r, c in zip(range(row+1, len(chessboard), 1), range(col-1, -1, -1)) :
if (chessboard[r][c] == 'Q') :
return False

return True

def DisplayBoard (chessboard : List) :

for row in chessboard :
print(row)

def PlaceNQueens (chessboard : List, col : int) :

# If all the columns have a queen 'Q', a solution has been found.
global boardcnt

if (col >= len(chessboard)) :

boardcnt += 1
print("Board " + str(boardcnt))
print("==========================")
DisplayBoard(chessboard)
print("==========================\n")

else :

# Else try placing the queen on each row of the column and check if the chessboard remains OK.
for row in range(len(chessboard)) :

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 '.'

def main() :

chessboard = []
N = int(input("Enter chessboard size : "))

for i in range(N) :
row = ["."] * N
chessboard.append(row)

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

if __name__ == "__main__" :
main()
``````

Output

``````Enter chessboard size : 4
Board 1
==========================
['.', '.', 'Q', '.']
['Q', '.', '.', '.']
['.', '.', '.', 'Q']
['.', 'Q', '.', '.']
==========================

Board 2
==========================
['.', 'Q', '.', '.']
['.', '.', '.', 'Q']
['Q', '.', '.', '.']
['.', '.', 'Q', '.']
==========================

Enter chessboard size : 5
Board 1
==========================
['Q', '.', '.', '.', '.']
['.', '.', '.', 'Q', '.']
['.', 'Q', '.', '.', '.']
['.', '.', '.', '.', 'Q']
['.', '.', 'Q', '.', '.']
==========================

Board 2
==========================
['Q', '.', '.', '.', '.']
['.', '.', 'Q', '.', '.']
['.', '.', '.', '.', 'Q']
['.', 'Q', '.', '.', '.']
['.', '.', '.', 'Q', '.']
==========================

Board 3
==========================
['.', '.', 'Q', '.', '.']
['Q', '.', '.', '.', '.']
['.', '.', '.', 'Q', '.']
['.', 'Q', '.', '.', '.']
['.', '.', '.', '.', 'Q']
==========================

Board 4
==========================
['.', '.', '.', 'Q', '.']
['Q', '.', '.', '.', '.']
['.', '.', 'Q', '.', '.']
['.', '.', '.', '.', 'Q']
['.', 'Q', '.', '.', '.']
==========================

Board 5
==========================
['.', 'Q', '.', '.', '.']
['.', '.', '.', 'Q', '.']
['Q', '.', '.', '.', '.']
['.', '.', 'Q', '.', '.']
['.', '.', '.', '.', 'Q']
==========================

Board 6
==========================
['.', '.', '.', '.', 'Q']
['.', '.', 'Q', '.', '.']
['Q', '.', '.', '.', '.']
['.', '.', '.', 'Q', '.']
['.', 'Q', '.', '.', '.']
==========================

Board 7
==========================
['.', 'Q', '.', '.', '.']
['.', '.', '.', '.', 'Q']
['.', '.', 'Q', '.', '.']
['Q', '.', '.', '.', '.']
['.', '.', '.', 'Q', '.']
==========================

Board 8
==========================
['.', '.', '.', '.', 'Q']
['.', 'Q', '.', '.', '.']
['.', '.', '.', 'Q', '.']
['Q', '.', '.', '.', '.']
['.', '.', 'Q', '.', '.']
==========================

Board 9
==========================
['.', '.', '.', 'Q', '.']
['.', 'Q', '.', '.', '.']
['.', '.', '.', '.', 'Q']
['.', '.', 'Q', '.', '.']
['Q', '.', '.', '.', '.']
==========================

Board 10
==========================
['.', '.', 'Q', '.', '.']
['.', '.', '.', '.', 'Q']
['.', 'Q', '.', '.', '.']
['.', '.', '.', 'Q', '.']
['Q', '.', '.', '.', '.']
==========================
``````
``````#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

``````Enter chessboard size : 1

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

Enter chessboard size : 4

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

Board 2
========================
. Q . .
. . . Q
Q . . .
. . Q .
========================
``````
``````import java.util.Scanner;

class NQueens {

private int boardcnt = 0;

boolean IsBoardOk (char 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.length; r++, c--) {
if (chessboard[r][c] == 'Q') {
return false;
}
}

return true;
}

void DisplayBoard (char chessboard[][]) {

for (int r=0; r<chessboard.length; r++) {
for (int c=0; c<chessboard.length; c++) {
System.out.print(chessboard[r][c]+" ");
} System.out.println();
}
}

void PlaceNQueens (char chessboard[][], int col) {

// If all the columns have a queen 'Q', a solution has been found.
if (col >= chessboard.length) {
++boardcnt;
System.out.println("Board "+boardcnt);
System.out.println("========================");
DisplayBoard(chessboard);
System.out.println("========================");

} 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.length; 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 '.'
}
}
}

public static void main(String args[]) {

int N;

Scanner obj_scanner = new Scanner(System.in);  // Create a Scanner object
System.out.print("Enter chessboard size : ");

N = obj_scanner.nextInt();  // Get user input

char chessboard[][] = new char[N][N];

for (int r=0; r<N; r++) {
for (int c=0; c<N; c++) {
chessboard[r][c] = '.';
}
}

NQueens obj = new NQueens();

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

``````

Output

``````Enter chessboard size : 4
Board 1
========================
. . Q .
Q . . .
. . . Q
. Q . .
========================
Board 2
========================
. Q . .
. . . Q
Q . . .
. . Q .
========================

Enter chessboard size : 5
Board 1
========================
Q . . . .
. . . Q .
. Q . . .
. . . . Q
. . Q . .
========================
Board 2
========================
Q . . . .
. . Q . .
. . . . Q
. Q . . .
. . . Q .
========================
Board 3
========================
. . Q . .
Q . . . .
. . . Q .
. Q . . .
. . . . Q
========================
Board 4
========================
. . . Q .
Q . . . .
. . Q . .
. . . . Q
. Q . . .
========================
Board 5
========================
. Q . . .
. . . Q .
Q . . . .
. . Q . .
. . . . Q
========================
Board 6
========================
. . . . Q
. . Q . .
Q . . . .
. . . Q .
. Q . . .
========================
Board 7
========================
. Q . . .
. . . . Q
. . Q . .
Q . . . .
. . . Q .
========================
Board 8
========================
. . . . Q
. Q . . .
. . . Q .
Q . . . .
. . Q . .
========================
Board 9
========================
. . . Q .
. Q . . .
. . . . Q
. . Q . .
Q . . . .
========================
Board 10
========================
. . Q . .
. . . . Q
. Q . . .
. . . Q .
Q . . . .
========================
``````