N Queen Problem

N Queen Problem

Given a NxN Chess board, we have to place N Queens such that they do not attack each other. (A queen can attack any square vertically, Horizontally, or diagonally).

Example of N Queen Problem :

Given, N = 8,

One of the possible solution such that no queen attack any of the other queens,

Example of N Queen Problem

Method 1 (Using Backtracking)

As we know we cannot place any two queens in the same row thus every queen will be placed in different rows. Now, we can place ith queen to ith row if the square we are placing in is safe to place due to the previously placed queens; if there are no such squares left we can backtrack and return false. 

For every queen we are placing we have to check, 

  • There should be no queen in the same column,
  • There should be no queen in the same row,
  • There should be no queen in the same diagonal (upper left and right diagonal).

Note that we can eliminate the row search as we are already moving row wise to place the queens thus there will be no other queen in the same row thus we can eliminate that search.

Code for above implementation : 

C++ Code

/* Function to print solution */
void printBoard(vector<vector<int>> chess)
{
	int N = chess.size();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N;j++) {
			cout<<chess[i][j]<<" ";
		}
		cout<<endl;
	}
}

bool isValid(vector<vector<int>> chess, int r, int c)
{
	int N = chess.size();

	/* Check this column only upward */
	for (int i = 0; i < r; i++)
		if (chess[i][c]==1)
			return false;

	/* Check upper diagonal on right side */
	for (int i = r, j = c; j < N && i >= 0; i--, j++)
		if (chess[i][j]==1)
			return false;

	/* Check upper diagonal on left side */
	for (int i = r, j = c; i >= 0 && j >= 0; i--, j--)
		if (chess[i][j]==1)
			return false;

	return true;
}

/* Recursive function for N-Queen Problem*/
bool recurNqueen(vector<vector<int>> chess, int r,int N)
{
/* if no queens are left to place
	we return true. */
	if (r >= N)
		return true;

	for (int i = 0; i < N; i++) {
		/*Check if placing queen to chess[r][i] is valid.*/
		if (isValid(chess, r, i)) {
			/* Place this queen in chess[r][i] */
			chess[r][i] = 1;

			/* move ahead for next row */
			if (recurNqueen(chess, r + 1,N))
				return true;

			/* Backtracking */
			chess[r][i] = 0; 
		}
	}

	/* If the queen cannot be placed in any column for
	the given row we return false.*/
	return false;
}

        void NQueen(int N)
{
	/* creating chess board of NxN and initialising it with 0*/
	vector<vector<int>> chess(N,vector<int>(N,0));
	
	/*initialising the recursive function from 0th row*/
	if (recurNqueen(chess, 0, N) == 0) {
		/* if no solution exists the recursive function will end up 
		returning false.*/
		cout<<"Solution Do not exist for "<<N<<" Queens ";
		return;
	}
	/* else solution exists and printing out the solution*/
	printBoard(chess);
	return;
}

Java Code

static void printBoard(int chess[][],int N)
{
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			System.out.print(" " + chess[i][j] + " ");
        }
        System.out.println();
	}
}

static boolean isValid(int chess[][], int r, int c,int N)
{
	/* Check this column only upward */
	for (int i = 0; i < r; i++)
		if (chess[i][c]==1)
			return false;

	/* Check upper diagonal on right side */
	for (int i = r, j = c; j < N && i >= 0; i--, j++)
		if (chess[i][j]==1)
			return false;

	/* Check upper diagonal on left side */
	for (int i = r, j = c; i >= 0 && j >= 0; i--, j--)
		if (chess[i][j]==1)
			return false;

	return true;
}

/* Recursive function for N-Queen Problem*/
static boolean recurNqueen(int chess[][], int r,int N)
{
	/* if no queens are left to place
	we return true. */
	if (r >= N)
		return true;

	for (int i = 0; i < N; i++) {
		/*Check if placing queen to chess[r][i] is valid.*/
		if (isValid(chess, r, i, N)) {
			/* Place this queen in chess[r][i] */
			chess[r][i] = 1;
 
			/* move ahead for next row */
			if (recurNqueen(chess, r + 1, N))
				return true;

			/* Backtracking */
			chess[r][i] = 0; 
		}
	}

	/* If the queen cannot be placed in any column for
	the given row we return false.*/
	return false;
}

static void NQueen(int N)
{
    /* creating chess board of NxN and initialising it with 0*/
    int chess[][] = new int[N+1][N+1];
    for(int i=0;i<N+1;i++){
        for(int j=0;j<N+1;j++){
            chess[i][j] = 0;
        }
    }
	/*initialising the recursive function from 0th row*/
	if (recurNqueen(chess, 0, N) == false) {
		/* if no solution exists the recursive function will end up 
		returning false.*/
        System.out.print("Solution Do not exist for " + N + " Queens. ");
		return;
	}
	/* else solution exists and printing out the solution*/
	printBoard(chess, N);
	return;
}

Python Code

# Function to print solution 
def printBoard(chess,N) :
    for i in range(N):
        for j in range(N):
            print(chess[i][j],end=' ')
        print()

def isValid( chess, r, c, N) :	
	# Check this column only upward 
	for i in range(r):
		if chess[i][c]==1:
			return False

	# Check upper diagonal on right side
	for i, j in zip(range(r, -1, -1),range(c, N, 1)):
		if chess[i][j]==1:
			return False

	# Check upper diagonal on left side 
	for i, j in zip(range(r, -1, -1),range(c, -1, -1)):
		if chess[i][j]==1:
			return False

	return True

# Recursive function for N-Queen Problem
def recurNqueen( chess, r, N):
	# if no queens are left to place
	# we return true. 
	if r >= N:
		return True

	for i in range(N):
		# Check if placing queen to chess[r][i] is valid.
		if isValid(chess, r, i, N) == True: 
			# Place this queen in chess[r][i] 
			chess[r][i] = 1

			# move ahead for next row 
			if recurNqueen(chess, r + 1, N):
				return True

			# Backtracking 
			chess[r][i] = 0 

	# If the queen cannot be placed in any column for
	# the given row we return false.
	return False

def NQueen(N):
	# creating chess board of NxN and initialising it with 0
    chess = [[0 for i in range(N+1)] for j in range(N+1)]
    # initialising the recursive function from 0th row
    if recurNqueen(chess, 0, N) == 0:
		# if no solution exists the recursive function will end up 
		# returning false.
        print("Solution not found !!")
        return

    # else solution exists and printing out the solution*/
    printBoard(chess, N)
	

Time Complexity of the Above approach : O(N!).

Method 2 (A little optimisation)

In the above approach we can make some of the observations based on the image below.

right diagonal

From the above image we can clearly observe that every right diagonal can be represented as a sum of coordinates of the cells through which the diagonal passes.

left diagonal

From the above image we can observe that every left diagonal can be represented by difference of the coordinates of the cells lying on the diagonal. 

Thus using the same we can reduce our time by excluding the step for searching the whole diagonal using a loop instead we can create an array for left, right diagonal and columns to store if there exists a queen in them. 

Code for above optimization :

C++ Code

/*global vectors to store previously placed queens*/
vector<vector<int>> prevd;
vector<int> prevc;

/* Function to print solution */
void printBoard(vector<vector<int>> chess)
{
	int N = chess.size();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N;j++) {
			cout<<chess[i][j]<<" ";
		}
		cout<<endl;
	}
}

bool isValid(vector<vector<int>> chess, int r, int c)
{
	int N = chess.size();

	/* Check this column only upward */
	if(prevc[c] == 1) return false;

	/* Check upper diagonal on right side */
	if(prevd[r+c][0] == 1) return false;

	/* Check upper diagonal on left side */
	if(prevd[r-c+N-1][1] == 1) return false;

	return true;
}

/* Recursive function for N-Queen Problem*/
bool recurNqueen(vector<vector<int>> chess, int r,int N)
{
	/* if no queens are left to place
	we return true. */
	if (r >= N)
		return true;

	for (int i = 0; i < N; i++) {
		/*Check if placing queen to chess[r][i] is valid.*/
		if (isValid(chess, r, i)) {
			/* Place this queen in chess[r][i] and mark 
                  the respective column , right and left diagonal. */
			chess[r][i] = 1;
			prevc[i] = 1;
			prevd[r+i][0] = 1;
			prevd[r-i+N-1][1] = 1;
			
			/* move ahead for next row */
			if (recurNqueen(chess, r + 1,N))
				return true;

			/* Backtracking */
		chess[r][i] = 0;
			prevc[i] = 0;
			prevd[r+i][0] = 0;
			prevd[r-i+N-1][1] = 0;
		}
	}

	/* If the queen cannot be placed in any column for
	the given row we return false.*/
	return false;
}

void NQueen(int N)
{
	/* creating chess board of NxN and initialising it with 0*/
	vector<vector<int>> chess(N,vector<int>(N,0));
	
	/*creating and initializing global vector to store answers 
	for prev diagonals and columns.*/
	prevd.resize(2*N,vector<int> (2,0));
	prevc.resize(N,0);

	/*initialising the recursive function from 0th row*/
	if (recurNqueen(chess, 0, N) == 0) {
		/* if no solution exists the recursive function will end up 
		returning false.*/
		cout<<"Solution Do not exist for "<<N<<" Queens ";
		return;
	}
	/* else solution exists and printing out the solution*/
	printBoard(chess);
	return;
}

Java Code

/*global arrays to store previously placed queens*/
static int prevd[][];
static int prevc[];

/* Function to print solution */
static void printBoard(int chess[][],int N)
{
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			System.out.print(" " + chess[i][j] + " ");
        }
        System.out.println();
	}
}

static boolean isValid(int chess[][], int r, int c,int N)
{	
	/* Check this column only upward */
	if(prevc[c] == 1) return false;

	/* Check upper diagonal on right side */
	if(prevd[r+c][0] == 1) return false;

	/* Check upper diagonal on left side */
	if(prevd[r-c+N-1][1] == 1) return false;

	return true;

}

/* Recursive function for N-Queen Problem*/
static boolean recurNqueen(int chess[][], int r,int N)
{
	/* if no queens are left to place
	we return true. */
	if (r >= N)
		return true;

	for (int i = 0; i < N; i++) {
		/*Check if placing queen to chess[r][i] is valid.*/
		if (isValid(chess, r, i, N)) {
			/* Place this queen in chess[r][i] */
			chess[r][i] = 1;
			prevc[i] = 1;
			prevd[r+i][0] = 1;
			prevd[r-i+N-1][1] = 1;
			
			/* move ahead for next row */
			if (recurNqueen(chess, r + 1, N))
				return true;

		/* Backtracking */
			chess[r][i] = 0;
			prevc[i] = 0;
			prevd[r+i][0] = 0;
			prevd[r-i+N-1][1] = 0;
			 
		}
	}

	/* If the queen cannot be placed in any column for
	the given row we return false.*/
	return false;
}

static void NQueen(int N)
{
	/* creating chess board of NxN and initialising it with 0*/
	int chess[][] = new int[N+1][N+1];
    for(int i=0;i<N+1;i++){
        for(int j=0;j<N+1;j++){
            chess[i][j] = 0;
        }
    }

	prevd = new int[2*N][2];
	for(int i=0;i<2*N;i++){
		prevd[i][0] = 0;
		prevd[i][0] = 1;
	}

	prevc = new int[N];
	for(int i=0;i<N+1;i++){
		prevc[i] = 0;
	}
	/*initialising the recursive function from 0th row*/
	if (recurNqueen(chess, 0, N) == 0) {
		/* if no solution exists the recursive function will end up 
		returning false.*/
        System.out.print("Solution Do not exist for " + N + " Queens. ");
		return;
	}
	/* else solution exists and printing out the solution*/
	printBoard(chess, N);
	return;
}

Python Code

prevd = []
prevc = []

# Function to print solution 
def printBoard(chess,N) :
    for i in range(N):
        for j in range(N):
            print(chess[i][j],end=' ')
        print()

def isValid( chess, r, c, N) :	
	# Check this column only upward 
	if prevc[c] == 1: 
		return False

	# Check upper diagonal on right side 
	if prevd[r+c][0] == 1: 
		return False

	# Check upper diagonal on left side 
	if prevd[r-c+N-1][1] == 1: 
		return False

	return True

# Recursive function for N-Queen Problem
def recurNqueen( chess, r, N):
	# if no queens are left to place
	# we return true. 
	if r >= N:
		return True

	for i in range(N):
		# Check if placing queen to chess[r][i] is valid.
		if isValid(chess, r, i, N) == True: 
			# Place this queen in chess[r][i] 
			chess[r][i] = 1
			prevc[i] = 1	
			prevd[r+i][0] = 1 
prevd[r-i+N-1][1] = 1 

			# move ahead for next row 
			if recurNqueen(chess, r + 1, N):
				return True

			# Backtracking 
			chess[r][i] = 0 
			prevc[i] = 0	
			prevd[r+i][0] = 0 
			prevd[r-i+N-1][1] = 0 


	# If the queen cannot be placed in any column for
	# the given row we return false.
	return False

def NQueen():
    N = 8
	# creating chess board of NxN and initialising it with 0
    chess = [[0 for i in range(N+1)] for j in range(N+1)]
    prevd = [[0 for i in range(2*N)] for j in range(2)]
	prevc = [0 for i in range(N+1)]

	# initialising the recursive function from 0th row
    if recurNqueen(chess, 0, N) == 0:
		# if no solution exists the recursive function will end up 
		# returning false.
        print("Solution not found !!")
        return

    # else solution exists and printing out the solution*/
    printBoard(chess, N)
	

Practice Question

NQueens

FAQs

  • What is the algorithm used by the N- Queen problem?

To solve the N- Queen problem we use backtracking to reach the solution, however we can add some optimisations one such solution is as discussed above.

  • What is the Time Complexity of the N-Queen Problem?

Time complexity for the N-Queen problem solved using Backtracking is O(N!) where N denotes number of Queens and dimensions of the chess board.

Previous Post
Count to Infinity Problem

Count to Infinity Problem

Next Post
Knapsack Problem

0-1 Knapsack Problem

Total
0
Share