N Queen Problem Using Recursive Backtracking
N Queen Problem is the problem of placing N chess 
queens on an NxN chessboard so that no two queens attack each other, for which solutions exist for all natural numbers n except n=2 and n=3.
A solution requires that no two queens share the same row, column, or diagonal.
It is more general form of inital Eight queens problem, where we need to find positions for 8 Queens on 8×8 chessboard.
If you are interested in java programs for other board games like Sudoku Solver, Sudoku Checker, Snake N Lader and Tic Tac Toe, you can check out my posts in Board Games section.
What is backtracking algorithm ?
In backtracking algorithms you try to build a solution one step at a time. If at some step it becomes clear that the current path that you are on cannot lead to a solution, you go back to the previous step (backtrack) and choose a different path. Briefly, once you exhaust all your options at a certain step you go back.
Think of a labyrinth or maze – how do you find a way from an entrance to an exit? Once you reach a dead end, you must backtrack. But backtrack to where? to the previous choice point. Backtracking is also known as Depth First Search.
Approach for solving N Queen Problem using recursive backtracking algorithm
Since our board is 4×4, our recursion will be 4 level deep.
At the 0th level recursion, we place the 0th Queen on the 0th row.
At the 1st level of recursion, we place 1st queen on the 1st row such that she does not attack the 0th queen.
At the 2nd level of recursion, we place 2nd queen on the 2nd row such that she does not attack the 1st and 0th queen and so on.
At any point of time if we cannot find a cell for a queen on that row, we return false to the calling funcion and that level of recursion will then try to place the queen on the next available cell of that row. If that doesn't work out then that function itself is going to return false to the calling function above it and so on.
Below slideshow contains
Java Program implementation
1) Create a Class to represent position of Queen
QueenPosition class has row and col fields to store the position of Queen on NxN Grid.
We will create N sized array of type QueenPosition to store positions of all placed queens.
class QueenPosition
{
int row;
int col;
public QueenPosition(int row, int col) {
super();
this.row = row;
this.col = col;
}
2) How do we find out if a cell is under attack from the queen or not?
Let us assume that we have 4×4 chessboard and queen is placed at cell (1,2) i.e. row 1 and column 2.
So all the cells which are having the same row value as Queen's row are under attack. i.e.
(1,0)
(1,1)
(1,3)
Similarly, all the cells which are having the same column value as Queen's column are under attack. i.e.
(0,2)
(2,2)
(3,2)
Cells on the two diagonals of the Queen are also under attack.
Diagonal 1 : Top left to bottom right (row – column)
Here for the Queen, (row – column) -> 1-2 = -1
So, Any cell for which (row – column) = -1 will be on the same diagonal and will be under attack by Queen. i.e.
(0,1) -> 0 – 1 = -1
(2,3) -> 2 – 3 = -1
Diagonal 2 : Bottom left to top right (row + column)
Here for Queen, (row + column) -> 1+2 = 3
So, any cell for which (row + column) = 3 will be on this diagonal and will be under attack by Queen. i.e.
(3,0) -> 3 + 0 = 3
(2,1) -> 2 + 1 = 3
(0,3) -> 0 + 3 = 3
3) getSoution(int n, int row) method
It is
public static boolean getSolution(int n, int row)
{
if(n==2 || n==3)
return false;
if(row==n)
return true;
for(int col=0; col < n;col++)
{
boolean isSafe = true;
p[row] = new QueenPosition(row,col);
for(int placedQueen=0; placedQueen < row;placedQueen++)
{
if(p[placedQueen].col == col ||
p[placedQueen].row-p[placedQueen].col == row - col ||
p[placedQueen].row+p[placedQueen].col == row + col)
{
isSafe = false;
}
}
if(isSafe)
{
if(getSolution(n, row+1))
return true;
}
}
return false;
}
4) Main Method
If getSolution() returns true, it will print the Grid on
When we initialize NxN result Grid, there are all 0s. We will set 1 (Queen) in all the cells which
package algorithm;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;
public class NQueenProblem {
public static PrintWriter out = new PrintWriter(System.out);
public static QueenPosition[] p;
public static void main(String[] args) {
System.out.println("Enter Number of Queens");
Scanner s = new Scanner(System.in);
int n = s.nextInt();
p = new QueenPosition[n];
if(getSolution(n,0))
{
int[][] result = new int[n][n];
Arrays.stream(p).forEach(po->result[po.row][po.col]=1);
out.println("Display using Stream API \n-----------------------");
Arrays.stream(result)
.forEach(rw -> {
Arrays.stream(rw)
.forEach(rw1-> out.print(rw1 + " "));
out.println();
});
out.println("\n\nDisplay using normal For loop \n---------------------------");
for(int i=0;i < n;i++)
{
for(int j=0;j < n;j++)
{
out.print(result[i][j] + " ");
}
out.println();
}
}
else
{
out.println("Solution not available.");
}
out.flush();
}
public static boolean getSolution(int n, int row)
{
// method body
}
}Download Complete Java Program »
Time Complexity for this algorithm is exponential because of
Space Complexity is O(n) because in the worst case, our recursion will be
You can also check the other articles on sorting and searching such as selection sort, binary search, fibonacci search, merge sort etc. you can also go through our other articles on different algorithms and data structures.
That's all for this topic. If you guys have any suggestions or queries, feel free to drop a comment. We would be happy to add that in our post. You can also contribute your articles by creating contributor account here.
Happy Learning 🙂
If you like the content on CodePumpkin and if you wish to do something for the community and the planet Earth, you can donate to our campaign for planting more trees at CodePumpkin Cauvery Calling Campaign.
We may not get time to plant a tree, but we can definitely donate ₹42 per Tree.
About the Author
Tags: Backtracking, BoardGame, Chess, Game, Java, Puzzle, Recursion
Comments and Queries
If you want someone to read your code, please put the code inside <pre><code> and </code></pre> tags. For example:<pre><code class="java"> String foo = "bar"; </code></pre>For more information on supported HTML tags in disqus comment, click here.
