Blog
0

Eight Queens Problem: Part 1

  • Pradyumn Sharma
  • April 4, 2017

Tags:

Eight Queens Problem: Part 1

Pradyumn Sharma

April 4, 2017

The Eight Queens Problem is an interesting one for the students of computer algorithms. It illustrates the use of two techniques: recursion and backtracking.

This problem requires placing eight queens on a chessboard in such a manner that no queen can capture another queen.

To solve this problem, you don’t need to know the rules of playing chess (but if you want to, here is one such place).

All that you really need to know is that:

  • A chessboard is an 8 x 8 grid
  • If a queen finds another piece in the same row, same column, or either of the two diagonals, it can capture it. The following diagrams shows all the positions where a queen can capture.

It turns out that there are 92 solutions to this problem. If you like, you may give it a shot to manually look for a solution. But it may not be easy, and it involves a lot of trial-and-error. You may have great intuition or get lucky and find a solution quickly. Or you may spend many frustrating hours and still not find any solution.

Actually it will not be a bad idea to try to find a solution manually. Even if you don’t find one, but if you observe your own search process carefully, you may get some useful ideas for a suitable algorithm for a computer program. {Spoiler alert: one solution is shown at the end of the next section.}

Manual Search Approach

This is how I would manually try to find one solution.
1. Place a queen in the first row, first column.
2. Go to the next row, and try placing a queen, one-by-one, in each of the columns until I can find a place where this queen does not capture     an earlier queen.
a. If I can find any such a position, I’ll place a queen there, and repeat from repeat step 2 for the next row.
b. If I cannot find any such position in a row, then I’ll go back to the previous row, and remove the queen and try the remaining columns.

How do I know when I have found a solution? When I am able to successfully place a queen in the last row.

Does the above sound confusing? I suggest you try this out on your own using a chessboard and eight pieces (or a makeshift one), and get a hang of it. But here is one solution:

(As you can see, I have numbered the rows from 0 to 7 from top to down, and columns from 0 to 7 from left to right, though the world of chess players uses a different nomenclature, but that does not matter for our purposes.)

An Algorithm Based on the Above (Manual Search Approach)

Here is one algorithm that mimics the manual search approach described earlier. This algorithm uses recursion and backtracking, and finds all 92 solutions. We’ll look for improvements to this approach later.

Let us use a two-dimensional array of size 8 x 8 to represent a chessboard.

[I am using here a convenient combination of programming language syntax and natural language text to describe the algorithm]

solution {

tryPlacingAQueen (in row = 0)
}
tryPlacingAQueen (int row) {
for every column between 0 and 7
can we place a queen at (row, column) so that it cannot capture an earlier queen?
if yes, then
place a queen in (row, column)
have we reached row = 7?
if yes,
// it means that we have a solution, so
print the solution
else
// we need to continue trying to place a queen in the next row,
// so we make a recursive call to try placing a queen in the next row
tryPlacingAQueen (row + 1)
endif
// regardless of whether the queen placed in this (row, column) position
// led to a final solution or not, we need to explore the next column in the
// same row, so we first remove the last queen placed
remove queen from (row, column)
// and the for loop will now try the next column position anyway
else (queen cannot be placed at this position)
// so nothing to do, the for loop will try the next column position
end-for
// we have tried all column values for the input row, so we backtrack
// what do we need to do to backtrack? nothing actually, as we’ll exit the recursive call
// to return to the previous row.

How do we know when a solution is found? As mentioned in the comments above, when we successfully find a position for a queen in row = 7, then it means that we have a solution.

Does the algorithm find only one solution, or all 92? It finds all 92, because even after finding one solution, we keep continuing our algorithm.

When does the algorithm end? When we have finished trying all the eight columns for the first row.

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
package eightQueensWithTwoDimensionalArray;
 
public class EightQueens {
 
    private static boolean [][] board = new boolean [8][8];
    private static int solutionsCount = 0;
     
    public static void solution () {
        tryQueenInRow (0);
    }
 
    private static void tryQueenInRow(int row) {
        for (int column = 0; column < 8; column++) {
            if (! capturesAnotherQueen (row, column)) {
                placeQueenIn (row, column);
                if (row == 7
)
                    printSolution ();
                else
                    tryQueenInRow (row + 1);
                removeQueenFrom (row, column);
            }
        }
    }
 
    private static void placeQueenIn(int row, int column) {
        board [row][column] = true;
    }
 
    private static void removeQueenFrom(int row, int column) {
        board [row][column] = false;
    }
 
    private static boolean capturesAnotherQueen(int row, int column) {
        if (capturesInSameColumn (row, column) ||
                capturesInLeftDiagonal (row, column) ||
                capturesInRightDiagonal (row, column))
            return true;
        else
            return false;
    }
 
    private static boolean capturesInSameColumn(int row, int column) {
        for (int checkRow = row - 1, checkColumn = column + 1;
                checkRow >= 0 && checkColumn <= 7;
                checkRow --, checkColumn ++) {
            if (isThereQueenIn(checkRow, checkColumn))
                return true;
        }
        return false;
    }
 
    private static boolean capturesInLeftDiagonal(int row, int column) {
        for (int checkRow = row - 1, checkColumn = column - 1;
                checkRow >= 0 && checkColumn >= 0;
                checkRow --, checkColumn --) {
            if (isThereQueenIn(checkRow, checkColumn))
                return true;
        }
        return false;
    }
 
    private static boolean capturesInRightDiagonal(int row, int column) {
        for (int checkRow = 0; checkRow < row; checkRow ++) {
            if (isThereQueenIn(checkRow, column))
                return true;
        }
        return false;
    }
 
    private static boolean isThereQueenIn(int row, int column) {
        return (board [row][column]);
    }
 
    private static void printSolution() {
        solutionsCount ++;
        System.out.println("Solution " + solutionsCount + ":");
        for (int row = 0; row < 8; row ++) {
            for (int column = 0; column < 8; column ++) {
                if (isThereQueenIn (row, column))
                    System.out.print("Q  ");
                else
                    System.out.print("_  ");
            }
            System.out.println();
        }
        System.out.println();
    }
}

Full List of Solutions:

Here is the output of the above program (showing all the 92 solutions):

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

(and Win a Prize)

Let us explore an alternative way to implement this algorithm. In this, instead of using a two-dimensional array of size 8 x 8, we can 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 can be represented by the following values 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

Got it? I’ll present the code for this variation in another post in about four weeks’ time. But meanwhile, you may try to implement it yourself, using a single-dimensional array as shown above.

You may submit your code in any of the mainstream programming languages.(clickhere to submit the code) or email to pradyumn.sharma@pragatisoftware.com. The criteria for evaluation will be: (a) correctness of the output, (b) readability of your code (clean code).

From among the submissions received by me by the end of April 19, 2017, I’ll give away a gift voucher for Rs 500 to the best implementation. And your code may feature in my next post on this algorithm.

All the best! And enjoy!

40 responses to “Eight Queens Problem: Part 1”

  1. john newmann says:

    BOjHg9 My brother suggested I might like this website. He was entirely right. This post truly made my day. You cann at imagine simply how much time I had spent for this information! Thanks!

  2. prony bony says:

    gBWrim This is the perfect website for anybody who wishes to find out about

  3. visit says:

    Really appreciate you sharing this post. Really Great.

  4. Thank you for your post.Really looking forward to read more. Fantastic.

  5. Perfect work you have done, this internet site is really cool with superb info.

  6. Wow! Thank you! I always wanted to write on my site something like that. Can I include a fragment of your post to my website?

  7. Souls in the Waves Very good Early morning, I just stopped in to visit your site and believed I would say I enjoyed myself.

  8. Thanks-a-mundo for the blog article.Much thanks again. Great.

  9. Woh I enjoy your content , saved to bookmarks!

  10. I was suggested this web site by way of my cousin. I am now not sure whether this post is written via him as no one else recognise such certain about my trouble. You are amazing! Thank you!|

  11. wonderful points altogether, you simply received a logo new reader. What might you suggest in regards to your submit that you made some days ago? Any positive?

  12. This is a really good tip especially to those fresh to the blogosphere. Simple but very accurate info Appreciate your sharing this one. A must read article!

  13. Im grateful for the article post.Really thank you! Cool.

  14. information with us. Please stay us up to date like this.

  15. Thank you for sharing this first-class piece. Very interesting ideas! (as always, btw)

  16. It as really a great and helpful piece of info. I am glad that you shared this helpful info with us. Please keep us up to date like this. Thanks for sharing.

  17. Utterly indited articles , Really enjoyed looking through.

  18. name says:

    Pretty! This has been a really wonderful post. Many thanks for providing these details.

  19. name says:

    Lululemon Canada Factory Outlet Sale Online WALSH | ENDORA

  20. Your style is very unique in comparison to other people I have read stuff from. I appreciate you for posting when you ave got the opportunity, Guess I all just bookmark this page.

  21. Im obliged for the article post.Really looking forward to read more.

  22. Im obliged for the post.Really thank you! Cool.

  23. Many thanks for sharing this excellent write-up. Very inspiring! (as always, btw)

  24. sex toys says:

    This page certainly has all of the information I needed concerning this subject and didn at know who to ask.

  25. sex toys says:

    Right now it sounds like BlogEngine is the preferred blogging platform available right now. (from what I ave read) Is that what you are using on your blog?

  26. sex toys says:

    Tumblr article I saw a writer talking about this on Tumblr and it linked to

  27. sex toys says:

    You need to take part in a contest for one of the highest quality blogs online. I most certainly will highly recommend this site!

  28. lingerie says:

    Is it just me or does it look like some of the remarks appear

  29. lingerie nyc says:

    There as definately a lot to find out about this subject. I like all of the points you made.

  30. nyc lingerie says:

    Wow, wonderful blog layout! How long have you been blogging for? you made blogging look easy. The overall look of your site is magnificent, let alone the content!

  31. nyc lingerie says:

    Thank you for your article post.Really looking forward to read more. Cool.

  32. nyc sex toys says:

    Way cool! Some extremely valid points! I appreciate you writing this write-up and the rest of the website is really good.

  33. Thanks so much for the blog post. Really Cool.

  34. Thank you, I have recently been searching for information about this topic for ages and yours is the greatest I ave discovered till now. But, what about the bottom line? Are you sure about the source?

  35. I relish, result in I found exactly what I used to be looking for. You have ended my four day long hunt! God Bless you man. Have a great day. Bye

  36. When June arrives to the airport, a man named Roy (Tom Cruise) bumps into her.

  37. Dispensary says:

    Very neat article post.Thanks Again. Cool.

  38. Dispensary says:

    Simply wanna remark that you have a very decent web site , I enjoy the design and style it actually stands out.

  39. Google says:

    Google
    The time to study or stop by the material or web-sites we have linked to beneath.

  40. Google says:

    Google
    One of our guests a short while ago advised the following website.

Leave a Reply

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

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

Enquiry

Pragatisoftware