Summary: In this tutorial, we will learn what N Queen Problem is and how to solve N Queen Problem using the Backtracking algorithm in C and Java.

What is N Queen Problem?

We are given N chess’s queens and asked to place them in the chessboard of size NxN so that no two queens attack/eliminate each other.

A queen can only attack if another queen is either on:

  • Same Row
  • Same Column
  • Same Diagonal (left or right)

Example: For the 4 Queens problem, we have a 4×4 board. If a queen is placed at (2,2), then the places where no queen should be placed are crossed by the red lines as shown in the figure:

N queen problem

Solution for N Queen Problem

Now the question is how to solve N Queen Problem?

There are two approaches to solve this problem:

Naïve Algorithm

In this approach, we use the brute force method by randomly choosing the position to find all possible solutions.

This approach is not efficient because it test all possible configuration which repeats same queens placements repeatedly.

Backtracking Algorithm

In this approach, we place a queen in one column, and then we proceed to the next column (since a single column cannot contain more than one queen).

We then check the possible safe row position to place the next queen, so that we can proceed to the next column.

n queen backtracking algorithm

If there is no safe row in the current column, we go back to the previous column and change the queen’s position to the next possible safe row position. If have any, we proceed to the next column again, else we go back further and repeat the same task.

All solution of n queen problem

If we reached the last column and found the possible safe position (i.e. row), we print the configuration of queens (i.e. solution), else if we came back to the first column and none of the position (i.e. row) is safe then we assume that there is no possible solution.

So, In backtracking, if no further solution is possible, we go one step back and proceed with next available option.

Check N-Queens Visualizer to get visual working of backtrack algorithm.

Here is the implementation of the algorithm in C and Java:

C

Java

Output

When N is 4:

In the above program, the solveColumn(int col) is the recursive function implementing the backtracking algorithm.

The function checks whether it is possible or not to place a queen in the specific column. If yes it proceeds to the next recursive call i.e. solveColumn(col+1) else the execution returns back to the last recursive call to check for the next safe position to place the queens.

There are 92 safe configurations possible for 8 queens in the 8×8 chessboard, so it is not possible to show output here.

Check the output yourself by giving the value of N during program execution.

In this tutorial, we learned what is N Queen Problem and how to solve N queen problem using backtracking algorithm in C and Java programming languages.

This Post Has 3 Comments

  1. saurav rajput

    wow,so helpful
    thank you so much for saving me.

  2. saurav rajput

    one request sir
    how to solve sum of subsets problem using backtracking.
    please help 👨‍🦱

    1. Adarsh Kumar

      Check out I have posted the solution of Subset problem.

Leave a Reply