Parallel N Queens Assignment

Previous Group Warm Up

Be sure to complete Sequential N-Queens before attempting this exercise.

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 and Implement

QueenLocations

class:	QueenLocations.java
methods:	constructors boardSize columnOfQueenInRow candidateColumnsInRow
package:	nqueens.parallel.exercise
source folder:	student/src/main/java

constructors

There are two constructors for this class. One which creates a fresh new board state with no queens yet placed and another which creates a new board with the state of a given board which is further constrained by a new queen in the next row.

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

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

QueenLocations createNext Output
+ - - - - + r3 | * Q | r2 | Q * * | r1 | * * Q | r0 | Q * | + - - - - +

QueenLocations(int boardSize)

QueenLocations createNext
public QueenLocations(int boardSize) { throw new NotYetImplementedException(); }

QueenLocations(QueenLocations other, int row, int col)

QueenLocations createNext
public QueenLocations(QueenLocations other, int row, int col) { if (BoardStateUtils.isSafeToAddQueenAt(other.locations, row, col)) { locations = Arrays.copyOf(other.locations, other.locations.length); locations[row] = col; } else { throw new IllegalArgumentException(); } }

boardSize()

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

Clarification: we refer to the standard 8x8 chessboard's size as 8 and not 64.

columnOfQueenInRow(row)

method: public int columnOfQueenInRow(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)

• columnOfQueenInRow(0) returns 1
• columnOfQueenInRow(1) returns 6
• columnOfQueenInRow(2) returns 4
• columnOfQueenInRow(3) returns BoardStateUtils.EMPTY
• columnOfQueenInRow(4) returns BoardStateUtils.EMPTY
• columnOfQueenInRow(5) returns BoardStateUtils.EMPTY
• columnOfQueenInRow(6) returns BoardStateUtils.EMPTY
• columnOfQueenInRow(7) returns BoardStateUtils.EMPTY

candidateColumnsInRow(row)

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

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

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

Note: the provided BoardStateUtils.isSafeToAddQueenAt(locations, row, col) method should be helpful.

ParallelNQueensSolutionCounter

class:	ParallelNQueensSolutionCounter.java
methods:	searchForSolutions countSolutions
package:	nqueens.parallel.exercise
source folder:	student/src/main/java

searchForSolutions(queenLocations, row)

method: private static int searchForSolutions(QueenLocations queenLocations, int row) (parallel implementation required)

Note: as QueenLocations is immutable, you will need to create a new instance of the object whenever you move on from one row to the next. This is where the appropriate QueenLocations constructor comes in.

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?

What can be performed in parallel?

countSolutions(boardSize)

Create a new instance of DefaultQueenLocations to create a new board.

Pass that board along with the appropriate row to begin your search to searchForSolutions to solve this problem.

Testing

class:	__NQueensTestSuite.java
package:	nqueens.parallel.exercise
source folder:	testing/src/test/java

Pledge, Acknowledgments, Citations

file:

n-queens-pledge-acknowledgments-citations.txt

More info about the Honor Pledge