Eight Queen Puzzle (likewise N Queen)

Problem

Write an algorithm to print all ways of arranging eight queens on a chess board so that none of them share the same row, column or diagonal.

(image courtesy)

Solution
This is a classic problem to implement using backtracking. It has 92 distinct solutions. If solutions that differ only by symmetry operations (rotations and reflections) of the board are counted as one, the puzzle has 12 fundamental solutions.Also, when we say N queen problem, we have a NXN board. so, here we have 8X8 board implicitly.

Method 1 - Backtracking
We will start from the first row and move down to the last row placing a queen at each row and checking that each queen satisfies the following two conditions:

• The column number must be different from the already placed queens.
• It should not share a diagonal with already placed queens. 

Here is the code in java

private static int BOARD_SIZE = 8;

public static void eightQueenProblem(int row, int[] columnForRow,
        int[][] solution) {
    if (row == BOARD_SIZE) {
  printBoard(solution);
    } else {
        for (int i = 0; i < solution[0].length; ++i) {
            columnForRow[row] = i;
            if (check(row, columnForRow)) {
                solution[row][i] = 1;
                eightQueenProblem(row + 1, columnForRow, solution);
                solution[row][i] = 0;
            }
            columnForRow[row] = -1;
        }
    }
}
 
private static boolean check(int row, int[] columnForRow) {
    for (int i = 0; i < row; ++i) {
        int diff = Math.abs(columnForRow[row] - columnForRow[i]);
        if (diff == 0 || diff == row - i)
            return false;
    }
    return true;
}

private static void printBoard(int[][] solution)
{
 for (int i = 0; i < solution.length; ++i) {
  for (int j = 0; j < solution[i].length; ++j) {
                System.out.print(solution[i][j]);
  }
            System.out.println();
    }
    count++;
    System.out.println();
}

Note :

• Use of columnForRow[] should be marked. It simplifies 2-D problem to 1-D.
• It is simply try and error approach with backtracking. It tries to assign position line by line therefore eliminating the duplicate solution. However, solutions are not unique in terms of rotations. 

Here is the pseudocode

1) Start in the leftmost column
2) If all queens are placed
    return true
3) Try all rows in the current column.  Do following for every tried row.
    a) If the queen can be placed safely in this row then mark this [row, 
        column] as part of the solution and recursively check if placing  
        queen here leads to a solution.
    b) If placing queen in [row, column] leads to a solution then return 
        true.
    c) If placing queen doesn't lead to a solution then umark this [row, 
        column] (Backtrack) and go to step (a) to try other rows.
3) If all rows have been tried and nothing worked, return false to trigger 
    backtracking.

Dry running the above code
(to come soon)
Here is  wikipedia image showing how it is solved:

Time complexity - exponential
You can refer the time complexities here. Of-course recursion take O(N!), which is really slow.

References
http://puddleofriddles.blogspot.in/2011/07/write-algorithm-to-print-all-ways-of.html
http://see.stanford.edu/materials/icspacs106b/H19-RecBacktrackExamples.pdf
http://en.literateprograms.org/Eight_queens_puzzle_%28C%29
http://en.wikipedia.org/wiki/Eight_queens_puzzle
http://www.geeksforgeeks.org/backtracking-set-3-n-queen-problem/
http://tianrunhe.wordpress.com/2012/03/28/eight-queen-puzzle/
http://stackoverflow.com/questions/17926069/puzzled-about-backtracking-in-eight-queen
http://www.chegg.com/homework-help/questions-and-answers/poor-man-s-n-queens-problemn-queens-arranged-n-x-n-chessboard-way-queen-checks-another-que-q1009394