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>>();
						backup.addAll(blocks);

						// same row
						for (int k = 0; k < solution[i].length; ++k)
							blocks.add(new Pair<Integer>(i, k));
						// same column
						for (int k = 0; k < solution.length; ++k)
							blocks.add(new Pair<Integer>(k, j));

						// diagonal
						int x = i;
						int y = j;
						while (++x < solution.length
								&& ++y < solution[i].length)
							blocks.add(new Pair<Integer>(x, y));
						x = i;
						y = j;
						while (++x < solution.length && --y >= 0)
							blocks.add(new Pair<Integer>(x, y));
						x = i;
						y = j;
						while (--x >= 0 && ++y < solution[i].length)
							blocks.add(new Pair<Integer>(x, y));
						x = i;
						y = j;
						while (--x >= 0 && --y >= 0)
							blocks.add(new Pair<Integer>(x, y));

						eightQueenProblem(n - 1, blocks, solution);

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

Comments after running:
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;
	}

Comments:

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: