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.

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 Optional Integers. As such this method fills the array with Optional.empty().

private static Optional<Integer>[] createBoard(int boardSize) {
	@SuppressWarnings("unchecked")
	Optional<Integer>[] board = new Optional[boardSize];
	Arrays.fill(board, Optional.empty());
	return board;
}

countSolutions(boardSize)

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

@Override
public int countSolutions(int boardSize) {
	Optional<Integer>[] 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(Optional<Integer>[] 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