Sequential N Queens Assignment

Motivation

Backtracking is a powerful technique which can be readily parallelized. We will gain experience with backtracking by solving the N-Queens problem sequentially and in parallel.

N-Queens in particular can be used to explain the call stack as the chessboard *IS* the call stack.

Example solution of N-Queens when n equals 8

Background

The n-queens problem is a fundamental coding puzzle which asks: how can N queens be placed on an NxN chessboard so that they cannot attack each other? In chess, a queen can attack horizontally, vertically, and diagonally across the board. Thus, to solve the n-queens problem, we must effectively figure out how to place the queens in such a way that no two of them occupy the same row, column, or diagonal. We will be building a method that finds the total number of solutions for n-queens for any given n.

Representation

Image

Taken to the ludicrous extreme we could choose to represent the board state as a image of the board. We could even use an open source tool that leverages a convolutional neural network to extract the queen locations from our generated image. Would this be overkill? Absolutely. Would it be cool? Absolutely. Do we have better things to do with our time? Maybe.

Forsyth–Edwards Notation

We could use the standard string representation of a chessboard is Forsyth–Edwards Notation (FEN).

String board = "5Q2/3Q4/6Q1/Q7/7Q/1Q6/4Q3/2Q5 w - - 0 1";

Queen-only Notation

Since we do not need to represent pieces other than the queen (and we certainly do not need to support information like the availability of castling and en passant), we could simply store the locations of the queens in any of a number of formats.

Chess player friendly:

String board = "c1 e2 b3 h4 a5 g6 d7 f8";

Computer scientist friendly:

String board = "[0][2], [1][4], [2][1], [3][7], [4][0], [5][6], [6][3], [7][5]";

Pictorially:

Code To Investigate

BoardStateUtils

BoardStateUtils.EMPTY

public static final int EMPTY = -1;

BoardStateUtils.isSafeToAddQueenAt(boardState, row, col)

Determine if a queen can be safely placed in a specified (row, col) location.

public static boolean isSafeToAddQueenAt(int[] boardState, int row, int col) {
	for (int r = 0; r < boardState.length; ++r) {
		if (boardState[r] != EMPTY) {
			int c = boardState[r];
			// is in same row
			if (r == row) {
				// note: we do not check if it is the same column, we return false
				return false;
			}
			// is in same column
			if (c == col) {
				return false;
			}
			// is in same diagonal A
			if (row - r == c - col) {
				return false;
			}
			// is in same diagonal B
			if (row - r == col - c) {
				return false;
			}
		}
	}
	return true;
}

SequentialNQueensSolutionCounter

createBoard(size)

Creates an empty board state. The board is represented by an array of ints. As such this method fills the array with BoardStateUtils.EMPTY.

private static int[] createBoard(int boardSize) {
	int[] board = new int[boardSize];
	Arrays.fill(board, BoardStateUtils.EMPTY);
	return board;
}

countSolutions(boardSize)

Creates an empty board and passes it to search which will perform the lion's share of the work.

public int countSolutions(int boardSize) {
	int[] board = createBoard(boardSize);
	return search(board, 0);
}

Code To Implement

search

class:	SequentialNQueensSolutionCounter.java
methods:	search
package:	nqueens.sequential.group
source folder:	student/src/main/java

method: private static int search(int[] board, int row) (sequential implementation only)

Employ backtracking to search for all possible solutions.

All good recursive algorithms need conditions at which to stop. Backtracking has two: 1) when a solution is found and 2) when the space has constrained to the point of hopelessness. How will you handle each of these conditions?

Testing

class:	_SequentialNQueensTestSuite.java
package:	nqueens.group
source folder:	testing/src/test/java