Code Pumpkin

N Queen Problem Using Recursive Backtracking

April 1, 2017
Posted by Pumpkin
Subscribe

Eight Queen Problem Solution

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 SolverSudoku CheckerSnake 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.

Four Queen Problem Solution

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 visual representation of above steps.
 


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.

Four Queen - Cells in a same row

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)

Four Queen - Cells in a same column

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.

N Queen Problem - Cells in a diagonal 1

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

N Queen Problem - Cells in a diagonal 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 recursive method which uses above logic to place the queen in 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

Main method calls getSolution() method with parameters n (nuber of queen or number of rows) and 0 (0th row).

If getSolution() returns true, it will print the Grid on console.

When we initialize NxN result Grid, there are all 0s. We will set 1 (Queen) in all the cells which are  present in 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) {
 
        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
    }
 
 
}

Time Complexity for this algorithm is exponential because of recusive calls and backtracking algorithm.

Space Complexity is O(n) because in the worst case, our recursion will be N level deep for an NxN board.

Download Complete Java Program »


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


Further Reading For interview Preparation

  1. Program To Find Unique Array Element
  2. Program To Check Whether A Number Is Prime Or Not
  3. Program To Check If A Given Number Is Power Of Two Or Not?
  4. Program To Find Number Of Set Bits In The Binary Number
  5. Sudoku Solver
  6. Trapping Rain Water
  7. Graph Search – Breadth First Search
  8. Graph Search – Depth First Search
  9. interface VS abstract class
  10. Access Modifiers (public, private, protected and default scope)
  11. HashMap vs Hashtable Vs SynchronizedMap Vs ConcurrentHashMap
  12. CountDownLatch Vs CyclicBarrier

Tags: , , , , , ,


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.

Total Post : 80
Subscribe
Contribute Your Articles

Interview Experiences

Related Books

Like Us On Facebook

Alexa Page Rank