Parallel N Queens Assignment - CSE231 Wiki Parallel N Queens Assignment From CSE231 Wiki Jump to: navigation, search Contents 1 Previous Group Warm Up 2 Motivation 3 Reference 3.1 Optional 4 Background 5 Code To Investigate 5.1 DefaultQueenLocations 5.1.1 DefaultQueenLocations(other, row, col) 5.1.2 isLocationThreatFree(row, col) 6 Code To Implement 6.1 Board State: DefaultImmutableQueenLocations 6.1.1 createNext(row,col) 6.1.2 boardSize() 6.1.3 columnOfQueenInRow(row) 6.1.4 candidateColumnsInRow(row) 6.2 ParallelNQueensSolutionCounter 6.2.1 ParallelNQueensSolutionCounter(queenLocationsCreator) 6.2.2 IntFunction queenLocationsCreator() 6.2.3 searchForSolutions(queenLocations, row) 6.2.4 countSolutions(boardSize) 7 Testing 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 Reference Optional empty() of(value) get() isPresent() isEmpty() 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 DefaultQueenLocations DefaultQueenLocations(other, row, col) This constuctor will prove useful for a method you will need to implement on DefaultQueenLocations. It constructs a new instance of DefaultQueenLocations from another instance of DefaultQueenLocations with an additional queen added to a row and column. private DefaultQueenLocations(DefaultQueenLocations other, int row, int col) {
if (other.isLocationThreatFree(row, col)) {
int boardSize = other.boardSize();
if (row < 0 || row >= boardSize) {
throw new IllegalArgumentException("row " + row + " is not in range [0, " + boardSize + ")");
}
if (col < 0 || col >= boardSize) {
throw new IllegalArgumentException("col " + col + " is not in range [0, " + boardSize + ")");
}
locations = new Optional[boardSize];
for (int r = 0; r < other.boardSize(); ++r) {
if (r == row) {
locations[row] = Optional.of(col);
} else {
locations[r] = other.columnOfQueenInRow(r);
}
}
} else {
throw new IllegalArgumentException(
"Not threat free: (row=" + row + ", column=" + col + ")\nOther board:\n" + other.toString());
}
}
isLocationThreatFree(row, col) This method is useful when determining where (if anywhere) an additional queen can be placed. @Override
public boolean isLocationThreatFree(int row, int col) {
int boardSize = this.boardSize();
for (int r = 0; r < boardSize; ++r) {
Optional columnOfQueenInRowR = this.columnOfQueenInRow(r);
if (columnOfQueenInRowR.isPresent()) {
int c = columnOfQueenInRowR.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;
}
Code To Implement Board State: DefaultImmutableQueenLocations class: DefaultQueenLocations.java methods: createNext getBoardSize getColumnOfQueenInRow getCandidateColumnsInRow package: nqueens.lab source folder: 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? boardSize() method: public int boardSize() (sequential implementation only) Note that we will refer to the standard 8x8 chessboard's size as 8 and not 64. columnOfQueenInRow(row) method: public Optional 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 Optional.of(1) columnOfQueenInRow(1) returns Optional.of(6) columnOfQueenInRow(2) returns Optional.of(4) columnOfQueenInRow(3) returns Optional.empty() columnOfQueenInRow(4) returns Optional.empty() columnOfQueenInRow(5) returns Optional.empty() columnOfQueenInRow(6) returns Optional.empty() columnOfQueenInRow(7) returns Optional.empty() candidateColumnsInRow(row) method: public List 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 isLocationThreatFree(row, col) method should be helpful. ParallelNQueensSolutionCounter class: ParallelNQueensSolutionCounter.java methods: constructor queenLocationsCreator searchForSolutions countSolutions package: nqueens.parallel.exercise source folder: src/main/java ParallelNQueensSolutionCounter(queenLocationsCreator) The constructor is passed a queenLocationsCreator. Hang onto it in an instance variable. IntFunction queenLocationsCreator() Simply return the value in the queenLocationsCreator instance variable. 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 createNext 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) Use the apply method on queenLocationsCreator 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: src/test/java class: _QueenLocationsTestSuite.java package: nqueens.parallel.exercise source folder: src/test/java class: _ParallelNQueensSolutionCountTestSuite.java package: nqueens.parallel.exercise source folder: src/test/java Retrieved from "https://classes.engineering.wustl.edu/cse231/core/index.php?title=Parallel_N_Queens_Assignment&oldid=3820" Navigation menu Personal tools English Log in Namespaces Page Discussion Variants Views Read View source View history More Search Navigation Main page Recent changes Random page Help General Initial Setup Office Hours Reference Fork Join Rosetta Stone Eclipse Tips Exercises and Warmups * Half & Half Nucleobase Count * Race Condition - Translation DoubleDeltaRange * Powers Of 2 Iterable * Ranges * Coarsening (N-Way Split) Nucleobase Count * Matrix Multiply +++ Matrix Multiply Divide and Conquer * Divide and Conquer Nucleobase Count Comparator Insertion Sort * Merge Sort +++ Merge Sort Parallel Combiner * Floodfill * Fibonacci * Thread and Executor Service * Higher Order Function: Filter * Hashtable * Int Sum MR Apps Card Only Sequential Map Reduce Framework * Reducer Word Count Only Parallel Map Reduce Framework * MutualFriends MR App * Bottleneck MapReduce Framework * Matrix MapReduce Framework * Cholera MR App * Windbag MR App * N-Queens * Sudoku * Centralized Work Queue Raytracer * Image Filters +++ Sudoku Advanced Constraint Propagation +++ Connect Four * Scan * Pack * Quicksort +++ Blelloch Scan * Atomicity Races * All Or Nothing Locks * Ordered Locks String Map K-Mer * K-mer Counting * ConcurrentHashTable * Iterative Averaging Fuzzy Iterative Averaging * Legged Races * Iced Cakes Pipeline Tools What links here Related changes Special pages Printable version Permanent link Page information Cite this page This page was last modified on 28 April 2022, at 12:20. Privacy policy About CSE231 Wiki Disclaimers
