Parallel N Queens Assignment

From CSE231 Wiki
Jump to navigation Jump to search

Previous Group Warm Up

Sequential N-Queens

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<Integer> 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 Java.png
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.svg (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.svg (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.svg (sequential implementation only)

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

Queens in rows 012.png

getCandidateColumnsInRow(row)

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

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

Queen r0 c4.png

  • 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.

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:

Attention niels epting.svg Warning:Ensure that you complete all of your tasks by enclosing them a single finish.
class: ParallelNQueens.java Java.png
methods: searchForSolutions
countSolutions
package: nqueens.lab
source folder: student/src/main/java

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

Attention niels epting.svg 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.svg (parallel implementation required)


Testing

class: __NQueensTestSuite.java Junit.png
package: nqueens.parallel.exercise
source folder: testing/src/test/java
class: _QueenLocationsTestSuite.java Junit.png
package: nqueens.parallel.exercise
source folder: testing/src/test/java
class: _ParallelNQueensSolutionCountTestSuite.java Junit.png
package: nqueens.parallel.exercise
source folder: testing/src/test/java