**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.

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.

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

## 0 comments:

## Post a Comment