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 Implement

Sequential Warm Up

	public static int countSolutions(int boardSize) {
		MutableInt count = new MutableInt();
		int[] board = new int[boardSize];
		Arrays.fill(board, EMPTY);
		search(count, board, 0);
		return count.intValue();
	}

class:	SequentialNQueens.java
methods:	search
package:	nqueens.warmup
source folder:	student/src/main/java

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