Sequential N Queens Assignment

Motivation

Not everything in the world should be divided and conquered. 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

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;
	}

isLocationThreatFree(board, row, col)

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

	private static boolean isLocationThreatFree(Optional<Integer>[] board, int row, int col) {
		for (int r = 0; r < board.length; ++r) {
			if (board[r].isPresent()) {
				int c = board[r].get();
				// 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;
	}

countSolutions(boardSize)

	@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)

Testing

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