# 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.

** N Queen Problem** can be solved using a

**recursive backtracking algorithm.**For other Backtracking algorithms, check my posts under tag Backtracking.

####
**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 **QueenPosition **array.

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**

**getSolution() **method with parameters n (

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 **QueenPosition **array**.**

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.

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.