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)

	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)

	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