Blog
0

Eight Queens Problem, Part 2

  • Pradyumn Sharma
  • April 25, 2017

Tags:

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

21 responses to “Eight Queens Problem, Part 2”

  1. prony bony says:

    RTBCKY Well I definitely enjoyed studying it. This subject provided by you is very constructive for proper planning.

  2. LOUIS VUITTON PURSES LOUIS VUITTON PURSES

  3. Marvelous, what a blog it is! This web site provides helpful information to us, keep it up.

  4. Well I sincerely liked reading it. This tip provided by you is very effective for proper planning.

  5. I’а†ve recently started a web site, the information you provide on this website has helped me tremendously. Thanks for all of your time & work.

  6. Wow, great blog.Much thanks again. Fantastic.

  7. If you are concerned to learn Web optimization techniques then you should read this article, I am sure you will obtain much more from this article concerning SEO.

  8. I was just wondering what computer software you would need to make business cards or labels from a home computer. Is is easy or even worth the time or money..

  9. name says:

    This very blog is really educating as well as amusing. I have picked up many helpful tips out of this source. I ad love to return again soon. Thanks a bunch!

  10. Usually I do not learn post on blogs, however I would like to say that this write-up very forced me to check out and do it! Your writing style has been surprised me. Thanks, quite nice post.

  11. Thanks for sharing, this is a fantastic blog post.Really thank you! Great.

  12. It as not that I want to replicate your web page, but I really like the pattern. Could you tell me which style are you using? Or was it especially designed?

  13. sex toys says:

    Passion in one as true talent is impressive. Writers today usually have little passion about what they write, but you are a unique and great writer. I am glad to see that writers like you exist.

  14. lingerie says:

    It as not that I want to duplicate your web page, but I really like the design. Could you let me know which design are you using? Or was it tailor made?

  15. lingerie nyc says:

    There as definately a great deal to know about this topic. I really like all of the points you ave made.

  16. nyc lingerie says:

    This website was how do you say it? Relevant!! Finally I have found something that helped me. Thank you!

  17. nyc sex toys says:

    We stumbled over here different website and thought I may as well check things out. I like what I see so i am just following you. Look forward to exploring your web page yet again.

  18. Thanks a lot for the article.Much thanks again. Cool.

  19. Simply a smiling visitant here to share the love (:, btw great design.

  20. ugg australia bailey button boot bomber jacket chestnut

  21. Dispensary says:

    Really appreciate you sharing this blog post.Much thanks again. Really Cool.

Leave a Reply

Your email address will not be published. Required fields are marked *

© 2017 Pragati Software Pvt. Ltd. All Rights Reserved.

Enquiry

Pragatisoftware