>  Blog

Eight Queens Problem: Part 2


Pradyumn Sharma

April 25, 2017


Recap

In Part 1 of this article, I had described an algorithm for the Eight Queens Problem, along with its implementation in Java. This problem requires placing eight queens on a chessboard in such a manner that no queen can capture another queen.

The algorithm presented in that article employs the techniques of recursion and backtracking, to print all the 92 solutions to the problem. The implementation provided in that article used a two-dimensional array of size 8x8. The algorithm finds and prints all 92 solutions to the problem.


Alternative Approach: Using a One-Dimensional Array

Let us now explore an alternative way to implement this algorithm. In this approach, instead of using a two-dimensional array of size 8 x 8, we'll manage with a single-dimensional array of size 8. We can use the array index as the row number on the chessboard, and the value as the column number in which a queen is placed in a given row.

For example, consider the following solution:




This solution can be represented in a single-dimensional array with the following values:

[0, 4, 7, 5, 2, 6, 1, 3]

It means that

  • In row = 0, queen is in column=0
  • In row = 1, queen is in column 4
  • . . .
  • In row = 7, queen is in column 3

Java Implementation

Here is the Java Implementation:

public class EightQueens {
	
	private static int [] board = new int [8];
	private static int solutionsCount = 0;	

	public static void solution () {
		tryQueenInRow (0);
	}

	private static void tryQueenInRow(int row) {
		
		for (int col = 0; col < 8; col++) {
			if (! attacksQueen (row, col)) {
				board [row] = col;
				if (row == 7)
					printSolution ();
				else
					tryQueenInRow (row + 1);
			}
		}
	}

	private static void printSolution() {
		solutionsCount ++;
		System.out.print("Solution " + solutionsCount + ": ");
		for (int i = 0; i <= 7; i++)
			System.out.print(board [i] + " ");
		System.out.println();
	}

	private static boolean attacksQueen(int row, int col) {
		if (attacksInSameColumn (row, col) ||
				attacksInLeftDiagonal (row, col) ||
				attacksInRightDiagonal (row, col))
			return true;
		else
			return false;
	}
	
	private static boolean attacksInRightDiagonal(int row, int col) {
		for (int i = 1; i <= row && i <= 7 - col; i++) {
			if (board [row - i] == col + i)
				return true;
		}
		return false;
	}

	private static boolean attacksInLeftDiagonal(int row, int col) {
		for (int i = 1; i <= row && i <= col; i++) {
			if (board [row - i] == col - i)
				return true;
		}
		return false;
	}

	private static boolean attacksInSameColumn(int row, int col) {
		for (int i = 0; i < row; i++) {
			if (board [i] == col)
				return true;
		}
		return false;
	}
}

    

And here is the output of the above program:

Solution 1: 0 4 7 5 2 6 1 3 
Solution 2: 0 5 7 2 6 3 1 4 
Solution 3: 0 6 3 5 7 1 4 2 
Solution 4: 0 6 4 7 1 3 5 2 
Solution 5: 1 3 5 7 2 0 6 4 
Solution 6: 1 4 6 0 2 7 5 3 
Solution 7: 1 4 6 3 0 7 5 2 
Solution 8: 1 5 0 6 3 7 2 4 
Solution 9: 1 5 7 2 0 3 6 4 
Solution 10: 1 6 2 5 7 4 0 3 
Solution 11: 1 6 4 7 0 3 5 2 
Solution 12: 1 7 5 0 2 4 6 3 
Solution 13: 2 0 6 4 7 1 3 5 
Solution 14: 2 4 1 7 0 6 3 5 
Solution 15: 2 4 1 7 5 3 6 0 
Solution 16: 2 4 6 0 3 1 7 5 
Solution 17: 2 4 7 3 0 6 1 5 
Solution 18: 2 5 1 4 7 0 6 3 
Solution 19: 2 5 1 6 0 3 7 4 
Solution 20: 2 5 1 6 4 0 7 3 
Solution 21: 2 5 3 0 7 4 6 1 
Solution 22: 2 5 3 1 7 4 6 0 
Solution 23: 2 5 7 0 3 6 4 1 
Solution 24: 2 5 7 0 4 6 1 3 
Solution 25: 2 5 7 1 3 0 6 4 
Solution 26: 2 6 1 7 4 0 3 5 
Solution 27: 2 6 1 7 5 3 0 4 
Solution 28: 2 7 3 6 0 5 1 4 
Solution 29: 3 0 4 7 1 6 2 5 
Solution 30: 3 0 4 7 5 2 6 1 
Solution 31: 3 1 4 7 5 0 2 6 
Solution 32: 3 1 6 2 5 7 0 4 
Solution 33: 3 1 6 2 5 7 4 0 
Solution 34: 3 1 6 4 0 7 5 2 
Solution 35: 3 1 7 4 6 0 2 5 
Solution 36: 3 1 7 5 0 2 4 6 
Solution 37: 3 5 0 4 1 7 2 6 
Solution 38: 3 5 7 1 6 0 2 4 
Solution 39: 3 5 7 2 0 6 4 1 
Solution 40: 3 6 0 7 4 1 5 2 
Solution 41: 3 6 2 7 1 4 0 5 
Solution 42: 3 6 4 1 5 0 2 7 
Solution 43: 3 6 4 2 0 5 7 1 
Solution 44: 3 7 0 2 5 1 6 4 
Solution 45: 3 7 0 4 6 1 5 2 
Solution 46: 3 7 4 2 0 6 1 5 
Solution 47: 4 0 3 5 7 1 6 2 
Solution 48: 4 0 7 3 1 6 2 5 
Solution 49: 4 0 7 5 2 6 1 3 
Solution 50: 4 1 3 5 7 2 0 6 
Solution 51: 4 1 3 6 2 7 5 0 
Solution 52: 4 1 5 0 6 3 7 2 
Solution 53: 4 1 7 0 3 6 2 5 
Solution 54: 4 2 0 5 7 1 3 6 
Solution 55: 4 2 0 6 1 7 5 3 
Solution 56: 4 2 7 3 6 0 5 1 
Solution 57: 4 6 0 2 7 5 3 1 
Solution 58: 4 6 0 3 1 7 5 2 
Solution 59: 4 6 1 3 7 0 2 5 
Solution 60: 4 6 1 5 2 0 3 7 
Solution 61: 4 6 1 5 2 0 7 3 
Solution 62: 4 6 3 0 2 7 5 1 
Solution 63: 4 7 3 0 2 5 1 6 
Solution 64: 4 7 3 0 6 1 5 2 
Solution 65: 5 0 4 1 7 2 6 3 
Solution 66: 5 1 6 0 2 4 7 3 
Solution 67: 5 1 6 0 3 7 4 2 
Solution 68: 5 2 0 6 4 7 1 3 
Solution 69: 5 2 0 7 3 1 6 4 
Solution 70: 5 2 0 7 4 1 3 6 
Solution 71: 5 2 4 6 0 3 1 7 
Solution 72: 5 2 4 7 0 3 1 6 
Solution 73: 5 2 6 1 3 7 0 4 
Solution 74: 5 2 6 1 7 4 0 3 
Solution 75: 5 2 6 3 0 7 1 4 
Solution 76: 5 3 0 4 7 1 6 2 
Solution 77: 5 3 1 7 4 6 0 2 
Solution 78: 5 3 6 0 2 4 1 7 
Solution 79: 5 3 6 0 7 1 4 2 
Solution 80: 5 7 1 3 0 6 4 2 
Solution 81: 6 0 2 7 5 3 1 4 
Solution 82: 6 1 3 0 7 4 2 5 
Solution 83: 6 1 5 2 0 3 7 4 
Solution 84: 6 2 0 5 7 4 1 3 
Solution 85: 6 2 7 1 4 0 5 3 
Solution 86: 6 3 1 4 7 0 2 5 
Solution 87: 6 3 1 7 5 0 2 4 
Solution 88: 6 4 2 0 5 7 1 3 
Solution 89: 7 1 3 0 6 4 2 5 
Solution 90: 7 1 4 2 0 6 3 5 
Solution 91: 7 2 0 5 1 4 6 3 
Solution 92: 7 3 0 2 5 1 6 4

Comparison with the Two-Dimensional Array Approach

  • Less memory required
  • Improved performance
  • More compact
  • Slightly harder to read

Distinct Solutions

Even though there are 92 solutions to the Eight Queens Problem, in reality there are only 12 distinct solutions. Consider, for example, the board for the first solution found by our code. As shown in the following diagram, if you rotate the board clockwise by 90, 180 and 270 degrees, you get three other solutions; and for each of these four solutions, if you take the mirror images, you get four more solutions, for a total of eight.


An original solution
90o clockwise rotation of earlier, original solution
180o clockwise rotation of earlier, original solution
 
270o clockwise rotation of earlier, original solution
 
Mirror image of the earlier, original solution
90o clockwise rotation of earlier, mirror image solution
180o clockwise rotation of earlier, mirror solution
 
270o clockwise rotation of earlier, mirror solution

But then, there ought to be 96 solutions (12 distinct solutions ✕ 8), but I said that there are 92. The reason for this is that there is one solution such that its 180 degrees rotation is the same as the original. Similarly, its 90 degree and 270 degree rotations are also the same as each other. The same, naturally, applies to their mirror images also. The following diagram shows the 4 combinations for this solution:


Original solution, and its 180o are the same.
90o clockwise rotation and also 270o are the same.
 
 
Mirror image of the original and also the 180o rotation are the same.
90o rotation and also the 270o clockwise rotation of earlier, mirror image.
 

Thus, we have (11 ✕ 8 + 1 ✕ 4 = ) 92 solutions.

Challenge Yourself?

Do you want to try this out yourself? Modify the code so that it prints only the 12 distinct solutions.

I'll give away a few gift vouchers for some of the best submissions (criteria: correct behavior, clean code). Submission deadline: May 2, 2017. Send your submission (only source files) to pradyumn.sharma@pragatisoftware.com.

I'll present my implementation, along with a few other variations, in another article, in a few weeks' time.