>  Blog  >  Pradyumn's Blog

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

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!