Thursday, 3 September 2015

N Queen Problem : Placing N (natural number) Queens in a NXN chess board such that each queen is safe from the rest of the queens. | Java , Back tracking


Dear Friends,

I am here with you with another problem based upon back tracking. Its the Famous N Queen Problem.

Suppose we have a NXN matrix and we have N Queens. A Queen has a nature of attacking. If She is positioned at any cell then she can attack in all the four directions [Up,Bottom,Left,Right] and also can attack diagonally [Up-Left,Up-Right,Bottom-Left,Bottom-Right]

Friends if we have N Queens then we have solution for all the Natural numbers as values of N except 2 and 3.

Below is my solution to this problem. Code is in Java and its based upon Recursion and Back Tracking.


package com.study.backtracking;
/**
 * 
 * @author Krishna.k
 * 
 * Problem :N queen problem  :  Placing N queens on NXN chess board.
 * 
 * Solution exists for each natural number except for N = 2 and N = 3.
 * 
 * Solution is based on Back Tracking.
 *
 */
public class NQueenSolution {
    public static void main(String[] args) {
        int N = 5; // number of queens and the size of the board
        int[][] board = new int[N][N];
        NQueenSolution solution = new NQueenSolution();
        boolean isSolved = solution.solveNQueen(board, N, 0);
        
        if(isSolved){
            System.out.println("Solution exists");
            for(int i = 0 ; i < N ; i++){
                for(int j = 0; j < N ; j++){
                    System.out.print(board[i][j]+"  ");
                }
                System.out.println();
            }
        }
        else{
            System.out.println("Solution does not exists");
        }
    }
    

    public boolean solveNQueen(int[][] board, int N, int col) {
        if(col == N){
            return true; // all the queens have been placed successfully
        }
        for(int row = 0; row < N; row++){
            if(isSafeFromLeft(board, row, col) && isSafeFromBottomLeft(board, N, row, col) &&  isSafeFromTopLeft(board, row, col)){
                board[row][col] = 1;// this is a safe row and we proceed with next columns
                if(solveNQueen(board, N, col+1)){
                    return true; // returning true during back track with true as return type.
                }else{
                    board[row][col] = 0; // reseting the cell during back track with false as return type.
                }
            }
        }
        return false;
    }

    public boolean isSafeFromTopLeft(int[][] board, int row, int col) {
        int traverseRow = row - 1;
        int traverseCol = col - 1;
        while (traverseRow >= 0 && traverseCol >= 0) {
            if (board[traverseRow][traverseCol] == 1) {
                return false;
            }
            traverseRow = traverseRow - 1;
            traverseCol = traverseCol - 1;
        }
        return true;
    }

    public boolean isSafeFromLeft(int[][] board, int row, int col) {
        int traverseCol = col - 1;
        while (traverseCol >= 0) {
            if (board[row][traverseCol] == 1) {
                return false;
            }
            traverseCol = traverseCol - 1;
        }
        return true;
    }

    public boolean isSafeFromBottomLeft(int[][] board, int N, int row, int col) {
        int traverseRow = row + 1;
        int traverseCol = col - 1;
        while (traverseRow < N && traverseCol >= 0) {
            if (board[traverseRow][traverseCol] == 1) {
                return false;
            }
            traverseRow = traverseRow + 1;
            traverseCol = traverseCol - 1;
        }
        return true;
    }
}