Sequential N Queens Assignment
Contents
Motivation
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.
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
BoardStateUtils
BoardStateUtils.EMPTY
public static final int EMPTY = -1;
BoardStateUtils.isSafeToAddQueenAt(boardState, row, col)
Determine if a queen can be safely placed in a specified (row, col) location.
public static boolean isSafeToAddQueenAt(int[] boardState, int row, int col) {
for (int r = 0; r < boardState.length; ++r) {
if (boardState[r] != EMPTY) {
int c = boardState[r];
// 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;
}
SequentialNQueensSolutionCounter
createBoard(size)
Creates an empty board state. The board is represented by an array of ints. As such this method fills the array with BoardStateUtils.EMPTY.
private static int[] createBoard(int boardSize) {
int[] board = new int[boardSize];
Arrays.fill(board, BoardStateUtils.EMPTY);
return board;
}
countSolutions(boardSize)
Creates an empty board and passes it to search which will perform the lion's share of the work.
public int countSolutions(int boardSize) {
int[] board = createBoard(boardSize);
return search(board, 0);
}
Code To Implement
search
class: | SequentialNQueensSolutionCounter.java | |
methods: | search | |
package: | nqueens.sequential.group | |
source folder: | student/src/main/java |
method: private static int search(int[] board, int row)
(sequential implementation only)
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?
Testing
class: | _SequentialNQueensTestSuite.java | |
package: | nqueens.group | |
source folder: | testing/src/test/java |