N Queens Problem in Java - Backtracking

N Queens Problem in Java using Backtracking


N Queen problem is of placing N queens on an N×N chessboard so that no two queens attack each other.

Let us first understand what we want to achieve? what is the input and what is the expected output?

You are given a chess board of N * N size, you have to place N Queens on a chess board in such a way that no queens are attacking each other.

Note: Queens attacks on same row, on same column as well as diagonally.

Sample Input and output for 4 * 4 chess board


Algorithm


We will use Backtracking algorithm for placing N Queens on N*N chess board.
 
1.  Since Queens attack on same rows, so only one Queen per row can be set.
2.  Since Queens attack on same column, so only one Queen per column can be set.
3.  We can start placing Queens either column wise that is one column at a time or can start placing 
     Queens row wise that is one row at a time.
     We will be using Row wise placement. Start from Row 0, check the safe position to place on 
     Row 0 and place a queen on row 0. once queen is placed on Row 0, move to Row 1 and so on.
4.  Before placing a queen on any position in a row, we first check is there any other already 
     placed queens on prior rows attacking on this position.
     if no already placed queen is attacking, then only place a queen on position.

5.  So when we are working on say Row 2. and we are looking for safe position on Row 2,
     then we need to check the safe position on Row 2 against Row 1 and Row 0 as that are the rows

     where we already placed a Queens. 
6.  If queen placement is not leading to a solution, then backtrack and change the position of already 
     placed queen and retry.
 

  

Java Program to place N Queens on N*N Chess board.



package backtracking;


public class NQueens2DArray {
 public static void main(String[] args) {
  placeQueens(4); // Lets take example of 4*4
 }

 private static void placeQueens(int gridSize){
  
  //If Grid is 1*1 or 2*2 or 3*3 then solution is not possible as, 
  //In 1*1 or 2*2 grid, Queen placed in 1st row at any position will attack queen placed at all the positions in row 2. 
  //In 3*3 grid, Queen placed in 1st row and 2nd row for all combinations position will attack queen placed at all the positions in row 3. 
  if(gridSize<4){ 
   System.out.println("No Solution available");
  }else{
   int[][] board = new int[gridSize][gridSize]; 
   placeAllQueens(board, 0);
   printBoard(board);
  }
 }
 private static boolean placeAllQueens(int board[][], int row){
  if(row>=board.length){
   return true;
  }

  boolean isAllQueensPlaced = false;
  for (int j = 0; j < board.length; j++) {

   if(isSafe(board, row, j)){
    board[row][j] = 1;
    isAllQueensPlaced = placeAllQueens(board, row+1);
   }
   if(isAllQueensPlaced){
    break;
   }else{
    board[row][j] = 0;
   }
  }
  return isAllQueensPlaced;
 }

 private static boolean isSafe(int board[][], int row, int col){

  //Check Left Upper Diagonal
  for (int i = row-1, j = col-1; i >= 0 && j >= 0; i--, j--) {
   if(board[i][j] == 1){
    return false;
   }
  }

  //Check Right Upper Diagonal
  for (int i = row-1, j = col+1; i >= 0 && j < board.length; i--, j++) {
   if(board[i][j] == 1){
    return false;
   }
  }

  //Check in same Column
  for (int i = row-1; i >= 0; i--) {
   if(board[i][col] == 1){
    return false;
   }
  }

  return true;
 }

 private static void printBoard(int[][] board){
  for (int row = 0; row < board.length; row++) {
   for (int col = 0; col < board.length; col++) {
    if(board[row][col] == 1){
     System.out.print("Q ");
    }else{
     System.out.print("_ ");
    }
   }
   System.out.println();
  }
  System.out.println("");
 }

}





Output:
            _    Q   _    _
            _    _    _    Q
           Q    _    _    _
            _    _    Q   _



You may also like to see


N Queens Puzzle Optimized using 1D array.

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.

Post a Comment