N Queens Puzzle.

The N Queen is the problem of placing N Chess 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 will be the expected output?

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

Sample Input and output for 4 * 4 chess board

Remember, Queens attacks on same row, on same column as well as diagonally.

Algorithm

---

In the last post we saw Optimized N Queens Puzzle.
We will use Backtracking algorithm approach for placing N Queens on N*N chess board. 

1. Since Queens attack on same rows, only one Queen per row can be set.
2. Since Queens attack on same column, 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 javabypatel.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.

Given an array of integers. All numbers occur thrice except one number which occurs once. Find the number in O(n) time & constant extra space. 

Count number of Bits to be flipped to convert A to B 

Count number of Set Bits in Integer. 

Check if number is Power of Two. 

Find all subsets of a set (Power Set). 

Skyline Problem in Java. 

Find Minimum length Unsorted Subarray, Sorting which makes the complete array sorted 

Count trailing zeros in factorial of a number 

When to use SOAP over REST Web Service. Is REST better than SOAP? 

Tower Of Hanoi Program in Java. 

Enjoy !!!! 

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