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

Reference

Optional

empty()

of(value)

get()

isPresent()

isEmpty()

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)

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