N Queen Problem Using Backtracking Algorithm

Given a chess board of size n*n find all the place n queens so that they don’t attach each other.

Attach Conditions, Queen at (i,j) and (x,y)

• i == x (for same row)
• j == y (for same column)
• |i-x| == |j -y| (for same diagonal)

Solution:

• Same as {@link GraphColoring} with the help of backtracking

Algorithm:

1. Base case: check all queen based or not
2. If all queens placed then
   1. return true
3. Iterate all rows (i) one by one
   1. Iterate all cols (j) one by one
      1. If safe place queen in cell (i,j) then
         1. reserve cell (i, j) for this queue
         2. recursively call this method to place next queen
         3. If next queen also placed properly then
            1. return true
         4. Else
            1. reset reserved cell (i, j)
4. return false

Video

Latest Source Code:
Github: NQueenProblem.java

Output:

 Queen - Position
0	(0,2)
1	(1,0)
2	(2,3)
3	(3,1)