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 and Sudoku in parallel.

N-Queens in particular can be used to explain the call stack as the chessboard *IS* the call stack.

In this assignment, you will implement solutions to both the N-Queens and Sudoku problems.

N-Queens

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.

Roadmap to Victory

1. (Warm Up) SequentialNQueens
2. DefaultImmutableQueenLocations
3. FirstAvailableRowSearchAlgorithm
4. ParallelNQueens

The Core Questions

• What are the tasks?
• What is the data?
• Is the data mutable?
• If so, how is it shared?

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)

Parallel Studio

Board State: DefaultImmutableQueenLocations

class:	DefaultQueenLocations.java
methods:	createNext getBoardSize getColumnOfQueenInRow getCandidateColumnsInRow
package:	nqueens.lab
source folder:	student/src/main/java

createNext(row,col)

method: public DefaultQueenLocations createNext(int row, int col) (sequential implementation only)

There are two constructors for this class. A public one which creates a fresh new board state with no queens yet placed. and a private one which creates a new board with the state of a given board which is further constrained by a new queen in the next row. You need to create a new instance using one of these two constructors. Which one is it?

Consider this example program which creates a valid 4-queens solution:

		int boardSize = 4;
		QueenLocations board0 = new DefaultQueenLocations(boardSize);
		QueenLocations board1 = board0.createNext(0, 1);
		QueenLocations board2 = board1.createNext(1, 3);
		QueenLocations board3 = board2.createNext(2, 0);
		QueenLocations board4 = board3.createNext(3, 2);
		System.out.println(board4);

Which board is used to create the next board?

getBoardSize()

method: public int getBoardSize() (sequential implementation only)

Note that we will refer to the standard 8x8 chessboard's size as 8 and not 64.

getColumnOfQueenInRow(row)

method: public Optional<Integer> getColumnOfQueenInRow(int row) (sequential implementation only)

For an 8x8 board with queens placed in (row=0, col=1), (row=1, col=6), and (row=2, col=4)

• getColumnOfQueenInRow(0) returns Optional.of(1)
• getColumnOfQueenInRow(1) returns Optional.of(6)
• getColumnOfQueenInRow(2) returns Optional.of(4)
• getColumnOfQueenInRow(3) returns Optional.empty()
• getColumnOfQueenInRow(4) returns Optional.empty()
• getColumnOfQueenInRow(5) returns Optional.empty()
• getColumnOfQueenInRow(6) returns Optional.empty()
• getColumnOfQueenInRow(7) returns Optional.empty()

getCandidateColumnsInRow(row)

method: public List<Integer> getCandidateColumnsInRow(int row) (sequential implementation only)

For an 8x8 board with a single queen placed in (row=0, col=4)

• getCandidateColumnsInRow(0) returns []
• getCandidateColumnsInRow(1) returns [0,1,2,6,7]
• getCandidateColumnsInRow(2) returns [0,1,3,5,7]
• getCandidateColumnsInRow(3) returns [0,2,3,5,6]
• getCandidateColumnsInRow(4) returns [1,2,3,5,6,7]
• getCandidateColumnsInRow(5) returns [0,1,2,3,5,6,7]
• getCandidateColumnsInRow(6) returns [0,1,2,3,5,6,7]
• getCandidateColumnsInRow(7) returns [0,1,2,3,5,6,7]

The provided isLocationThreatFree(row, col) method should be helpful.

Search Order: FirstAvailableRowSearchOrder

This class will provide methods that will allow us to implement a clean and efficient parallel solution in the final step.

class:	FirstAvailableRowSearchOrder.java
methods:	selectedNextUnplacedRow
package:	nqueens.lab
source folder:	student/src/main/java

method: public Optional<Integer> selectedNextUnplacedRow(QueenLocations queenLocations) (sequential implementation only)

For an 8x8 board with queens placed at (row=0, col=0), (row=1, col=3), (row=2, col=6), and (row=6, col=7):

• selectedNextUnplacedRow(queenLocations) returns Optional.of(3)

---

For a board with no unplaced rows, for example, a solution:

• selectedNextUnplacedRow(queenLocations) returns Optional.empty()

---

Warning:Do NOT skip empty rows simply because they have no candidate columns

In cases where a row does not have a queen placed in it, but has no valid candidate columns, for example a 3x3 board with a queen placed at (row=0, col=1):

It is critical that

• selectedNextUnplacedRow(queenLocations) returns Optional.of(1)

When searching for solutions we do not want to avoid dead rows. If anything, we want to move them to the front of the line, so that search can cease the current fruitless path.

ParallelNQueens

Searching for solutions like n-queens can be done in parallel without the need to finish at each level. As such, forasync is preferable to forall. However:

Warning:Ensure that you complete all of your tasks by enclosing them a single finish.

class:	ParallelNQueens.java
methods:	searchForSolutions countSolutions
package:	nqueens.lab
source folder:	student/src/main/java

method: public static int countSolutions(QueenLocations queenLocations, RowSearchOrder rowSearchOrder) (parallel implementation required)

Warning:FinishAccumulators must be registered with their finish statement

Instead of using a MutableInt in order to count the number of solutions we have found, we want to use a Finish Accumulator.

Creating a new instance of FinishAccumulator is done via on of the many static methods on the V5 class (the same class we get async and finish from).

Refer to the syntax page in order to see the syntax for properly setting up the accumulator.

method: private static void searchForSolutions(FinishAccumulator<Integer> accumulator, QueenLocations queenLocations, RowSearchOrder rowSearchOrder) (parallel implementation required)