The N Queens Problem. Place 4 Queens in 4*4 Chess Board such that none of them can hit any other in one move. OR How can N queens be placed on an NxN chessboard so that no two of them attack each other?

/*
  We can represent our chess board in 2d Array ie Matrix way, clean and simple.
  4*4 chess board can be represent as 

             y 
          0 1 2 3 
        0 _ _ _ _
        1 _ _ _ _
     x  2 _ _ _ _
        3 _ _ _ _

  So each cell is represented by (x,y) 
  x is row number and 
  y is column number.

  But same thing can be represent in 1d array for our problem
         y
     x _ _ _ _

  array[x] = y

  now in this case our x will represent a row but how to represent y, here is how we will manage, value placed inside array[x] will give us y coordinate.
  So, array[0] = 0, means placing a queen on 0th column of 0th row.
  So, array[1] = 3, means placing a queen on 3rd column of 1st row.


  We need to place N Queens in N*N chess board in such a way that no queens attack each other.
  This can be solved by placing a Queen in such a way that no other placed Queens is attacking it by checking,
  No Queens should be placed in same Column
  Placed Queens should not hit the queen we are trying to put diagonally.

  So, before placing a queen at row n, we need to check that no queens placed from row n to row n-1 is attacking it.

  So, if we observe, we have to place a queen in each row.
  How we will solve this problem is, start placing a queen at row 0, then at row 1 and so on.
  before placing a queen at row 1, we will make sure that queen placed in row 0 is not attacking it.
  before placing a queen at row 2, we will make sure that queen placed in row 0 and row 1 is not attacking it.


  1)  So how we will check for same column is very simple.

   before placing a queen in row 1, we will check in which column queen at row 0 is placed, this can be done by checking,
   array[n]==array[i]
   here n is the row at which we are trying to place a queen say 1 and i the loop from 0 to n-1, in our case it is 0
   and as per our protocol on 1d array that we are going to place our y coordinate in value of x coordinate. array[x] = y

   So by checking array[n]==array[i], if the value is same then we are trying to place in same column, which should be ignored.

  2)  How we will check diagonal,
      Also we don't need to check all the diagonals, but we can check all the queens instead. 
      Two queens are on the same diagonal by checking the differences between the rows and columns of the two Queens. 
      If the differences are the same, they're on the same diagonal. 
      Basically, if the slope of the line between the two queens is +-1, they're on the same diagonal.

       Let us take an example here. Assume that we already placed first queen in (2, 2) – 2nd queen is placed in 2nd column.  
       If we look at the diagonal cells (1,1), (1,3), (3,1), (3.3), we can observe that,

   So diagonal cells of array[2]=2 is,

   array[1]=1            array[1]=3
             \          /
              array[2]=2 
             /          \ 
   array[3]=1            array[3]=3

   |1-2| == |1-2| = 1 (for cell 1,1)
   |1-2| == |3-2| = 1 (for cell 1,3)
   |3-2| == |1-2| = 1 (for cell 3,1)
   |3-2| == |3-2| = 1 (for cell 3,3)

   (ColumnOfRow2 - ColumnOfRow1) == (Row2 - Row1) // for checking two queens are on same minor diagonal in our case it is array[1]=1
   (ColumnOfRow1 - ColumnOfRow2) == (Row2 - Row1) // for checking two queens are on same major diagonal in our case it is array[1]=3

    We don't need to check diagonals of 3rd row in our case ie for positions array[3]=1, array[3]=3 
    because when we are working for row 2 ie array[2]=2, 
    we need to check only row 1 as we are solving our problem row wise, and while working for Row 2, we will make sure 
    that Queen is already placed at Row 2 in safe place.  

    So by checking Column Difference and Rows Difference, we will come to know that Queen will be attacked diagonally by 
    other Queens or not.

 */

package backtracking;

public class NQueens {
 public static void main(String[] args) {

  int[] board = new int[4]; // Lets take example of 4*4
  new NQueens().placeAllQueens(board, 0);
 }

 
 private void placeAllQueens(int board[], int row){
  if(row==board.length){
   printBoard(board);
   System.exit(1);
  }else{
   for (int col = 0; col < board.length; col++) {
    board[row] = col;
    if(isPlacingSafe(board, row)){
     placeAllQueens(board, row+1);
    }
   }
  }
 }

 /***********************************************************************
  * Return true if queen placement board[currentRow] does not conflict with
  * other queens q[0] through board[currentRow-1]
  ***********************************************************************/
 private boolean isPlacingSafe(int[] board, int currentRow) {
  for (int previousRows = 0; previousRows < currentRow; previousRows++) {

   //Same Column Checking
   if(board[currentRow] == board[previousRows]){
    return false;
   }

   //Minor Diagonal Checking
   if( (board[currentRow] - board[previousRows]) == currentRow - previousRows){
    return false;
   }

   //Major Diagonal Checking
   if( (board[previousRows] - board[currentRow]) == currentRow - previousRows){
    return false;
   }

   //We can combine checking for Major and Minor Diagonal Checking
/*   if (Math.abs(board[currentRow] - board[previousRows]) == Math.abs(currentRow - previousRows)) {
    return false;
   }*/

  }
  return true;
 }

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

}