What is N Queen Problem?

We are given N chess’s queens and is 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 4 Queens problem, we will have a 4×4 board. If a queen is placed at (2,2), then the places at which no queen can be placed is crossed by red line as shown in the figure:

N queen problem

N Queen Algorithm

Now the question is how to solve N Queen Problem?

There are two approaches to solve this problem:

Naive Algorithm

In this approach, we try the brute force method to find all possible solution to the problem by randomly choosing the position.

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). Then, we check the possible safe row to place 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. If found any then 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), then 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.

N Queen in C|Java

This C program gives all possible safe configuration for N Queen Problem as output by giving the value of N during program execution.

C

Java

Output

When N is 4:

There are total 92 safe configurations possible to place 8 queens in the 8×8 board, so it is not possible to show output here. Check the output yourself by giving the value of N during program execution. If you have any doubts then do comment below.

Leave a Reply

Close Menu