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 8×8. 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:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

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

Eight Queens Problem, Part 2

Recent Posts

Technology Trends That Will Dominate 2019

Why Businesses Must Invest in IT Training?

An Introduction to NoSQL