N Queens Problem

Problem Statement: 
    Given a chess board of N x N , find all ways to place N queens so that they don't each other.

 Solution:

  They problem demands for placement of the N queens  on N*N chessboard such that none of them attack each other.
Eight Queens puzzle was first published in 1848 and its solution in 1950, which was then later extended to N- Queen puzzle.


Below is sample case for 4 x 4 matrix displaying attacking and non- attacking case.

Multiple solution can exist for N x N matrix . For  Eight Queens puzzle 12 unique solutions exist.
 Suppose two queens Q1 and Q2 are placed at (r1,c1) and (r2,c2) respectively. Now the two queens can attack only if any of these cases satisfies.

Case 1: Lies in the same row if

                 r1 = r2    

Case 2 : Lies in the same Column if

                 c1 = c2

Case 3 : Lies in the same Diagonal if absolute values are equal for x-coordinate and y-coordinate

                 | ( r1 - r2) | = | (c1 - c2 ) |               

     We will use two methods, one for placing the queen and the other for checking of the queen can be placed or not.

Algorithm: 

We will make a sol[] array which will hold the column number for
 every row in the matrix, at which Queen is to be placed.
This 1-D array will be overwritten while backtracking.

Method1 :

solve(givenRow , matrixSize)
   for( column =0 to matrizSize )
        if( matrix(given Row, currentColumn) is Valid(givenRow , currentColumn ))
              sol array [givenRow] = currentColumn

              if(givenRow has reached size of matrix)
                   print sol[] array

             else
                 solve(nextRow, matrixSize )


Method 2:

isValid(givenRow, givenColumn)
  if(case 2 or case 3 is satisfied)
      queen cant be placed, return false;
else
     return true

Refer to full Source Code

As defined above the two methods are given below.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

/** * Check if Queen can be placed for a given row,col * @return true if queen can be placed */ private boolean isValidPlacement(int[][] chess, int givenRow , int givenCol) { for(int currentRow=0;currentRow < givenRow ; currentRow ++) { // column check if (sol[currentRow]==givenCol) return false; //diagonal check condition if(Math.abs(sol[currentRow ] - givenCol) == Math.abs(currentRow - givenRow)) return false; } return true; } /** * Iterates over the a given row , for all columns * @param chess : input chess board * @param givenRow * @param size : length or breadth of matrix for a N x N matrix */ private void solveNQueen(int chess[][] , int givenRow , int size) { for(int currentCol=0;currentCol < size ; currentCol ++) { if(isValidPlacement(chess, givenRow , currentCol) == true) { sol[givenRow] = currentCol ; if(givenRow == size - 1) // this was the last row , print soln printSolution(sol); else // proceed with next row { int nextRow=givenRow + 1 ; solveNQueen(chess, nextRow, size) ; } } } }