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 twodimensional array of size 8x8. The algorithm finds and prints all 92 solutions to the problem.
Alternative Approach: Using a OneDimensional Array
Let us now explore an alternative way to implement this algorithm. In this approach, instead of using a twodimensional array of size 8 x 8, we'll manage with a singledimensional 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 singledimensional array with the following values:
[0, 4, 7, 5, 2, 6, 1, 3]
It means that
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 TwoDimensional Array Approach
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 
90^{o} clockwise rotation of earlier, original solution 
180^{o} clockwise rotation of earlier, original solution 
270^{o} clockwise rotation of earlier, original solution 

Mirror image of the earlier, original solution 
90^{o} clockwise rotation of earlier, mirror image solution 
180^{o} clockwise rotation of earlier, mirror solution 
270^{o} 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 180^{o} are the same. 
90^{o} clockwise rotation and also 270^{o} are the same. 

Mirror image of the original and also the 180^{o} rotation are the same. 
90^{o} rotation and also the 270^{o} 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.