Sequential N Queens Assignment

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.

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.

Representation

We need to represent the state of the board. Whatever data structure we choose, we will need to support:

1. placing a queen on the board
2. removing a queen from the board
3. determining if a board location is threat free from any of the queens currently on the board

Image

Taken to the ludicrous extreme we could choose to represent the board state as a image of the board. We could even use an open source tool that leverages a convolutional neural network to extract the queen locations from our generated image. Would this be overkill? Absolutely. Would it be cool? Absolutely. Do we have better things to do with our time? Maybe.

Forsyth–Edwards Notation

Since the image recognizer produces the standard string representation of a chessboard, namely Forsyth–Edwards Notation (FEN), we could decide to save a lot of work and just use FEN as our board notation.

String board = "5Q2/3Q4/6Q1/Q7/7Q/1Q6/4Q3/2Q5 w - - 0 1";

Queen-only Notation

Since we do not need to represent pieces other than the queen (and we certainly do not need to support information like the availability of castling and en passant), we could simply store the locations of the queens in any of a number of formats.

chess player friendly:

String board = "c1 e2 b3 h4 a5 g6 d7 f8";

computer scientist friendly:

String board = "[0][2], [1][4], [2][1], [3][7], [4][0], [5][6], [6][3], [7][5]";

or even pictorially:

String board = "   + - - - - - - - - +\n" +
               "r7 | *   *   * Q *   |\n" +
               "r6 |   *   Q   *   * |\n" +
               "r5 | *   *   *   Q   |\n" +
               "r4 | Q *   *   *   * |\n" +
               "r3 | *   *   *   * Q |\n" +
               "r2 |   Q   *   *   * |\n" +
               "r1 | *   *   Q   *   |\n" +
               "r0 |   * Q *   *   * |\n" +
               "   + - - - - - - - - +";

Matrix of Booleans

All of this generating Strings and parsing them seems like a lot of unnecessary work. The chessboard is 2d. Why not just have a matrix of booleans to represent whether each square has a queen on it or not?

boolean[][] board = new boolean[8][8];
board[0][2] = true;
board[1][4] = true;
board[2][1] = true;
board[3][7] = true;
board[4][0] = true;
board[5][6] = true;
board[6][3] = true;
board[7][5] = true;

Array of Integers

Since there is no way to have two queens in the same row or column, we can represent the board as a 1d array if ints. We simply need to choose whether represent the row or the column as the index. We will choose to have the row serve as the index. The value held at that array index will be the column the queen is in. We will use -1 to represent an empty row.

int[] board = new int[8];
board[0] = 2;
board[1] = 4;
board[2] = 1;
board[3] = 7;
board[4] = 0;
board[5] = 6;
board[6] = 3;
board[7] = 5;

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