## Eight queen puzzle

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.

My initial thoughts:

• Base case: 0 queens to put on the board, then print out the solution.
• Recursion: put 1 queen in valid position, then put the other $n-1$ queens.

My initial codes:

```	public static void eightQueenProblem(int n, Set<Pair<Integer>> blocks,
int[][] solution) {
if (n == 0) {
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();
}
System.out.println();
return;
} else {
for (int i = 0; i < solution.length; ++i) {
for (int j = 0; j < solution[i].length; ++j) {
if (!blocks.contains(new Pair<Integer>(i, j))) {
solution[i][j] = 1;

Set<Pair<Integer>> backup = new HashSet<Pair<Integer>>();

// same row
for (int k = 0; k < solution[i].length; ++k)
// same column
for (int k = 0; k < solution.length; ++k)

// diagonal
int x = i;
int y = j;
while (++x < solution.length
&& ++y < solution[i].length)
x = i;
y = j;
while (++x < solution.length && --y >= 0)
x = i;
y = j;
while (--x >= 0 && ++y < solution[i].length)
x = i;
y = j;
while (--x >= 0 && --y >= 0)

eightQueenProblem(n - 1, blocks, solution);

blocks = backup;
solution[i][j] = 0;
}
}
}
}
}

Way too many duplicate solutions because there is no ordering of assigning positions.
Solution:
public static void eightQueenProblem(int row, int[] columnForRow,
int[][] solution) {
if (row == 8) {
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();
} 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;
}

Use of columnForRow[] should be marked. It simplifies 2-D problem to 1-D.
It is simply try & 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.

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5c910d742fc58', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5c910d742fc97',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5c910d742fc9a',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});