Parallel N Queens Assignment
Contents
Previous Group Warm Up
Be sure to complete Sequential NQueens 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 NQueens problem sequentially and in parallel.
NQueens in particular can be used to explain the call stack as the chessboard *IS* the call stack.
Background
The nqueens 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 nqueens 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 nqueens 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 4queens 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:  nqueenspledgeacknowledgmentscitations.txt 
More info about the Honor Pledge