The Queen Safety Problem asks you to determine if a square on a chess board is safe from capture given a configuration of chess queen pieces. To make this example more compelling we are going to solve a variant of the Queen Safety problem that has more practical life applications—The Velociraptor Safety Problem.

Source: XKCD.com

The Velociraptor Safety Problem is conceptually identical to the queen safety problem. The only difference is that the queen pieces have been replaced with velociraptors (a slightly more life threatening foe). The world is still an 8x8 grid and we are going to assume that a velociraptor—or raptor for short—moves in the same manner as a queen chess piece.

This larger example demonstrates the use of a grid of Boolean values—that is, a single declaration of a Grid<bool>—to maintain information on a board and the placement of velociraptors. The code relevant to the demonstration is presented here in this handout. See the library reference for grid. This handout is meant to help with Assignment 1 Fauxtoshop.

We want to use a two-dimensional Grid template to maintain information for all of the squares of a chessboard. Because our particular example only deals with velociraptors, we only need to store a true or false for each board location—true means a velociraptor is present, false means there’s no velociraptor. Ultimately, we are going to be interested in looking at an arbitrary position of the board and determine whether or not any of the velociraptors placed elsewhere can attack that position.

## Create the Board

The following function initRaptorBoard takes a Grid by reference and initializes every entry of the grid to be false. Note the use of a double-for loop to generate every pair of row and col that corresponds to a legal index. After this function gets called, the state of the board is very easily represented.

## Placing Velociraptors

Next, we want a function PlaceRandomRaptors that places some number of velociraptors on the board at random locations. We enter the function with an idea of exactly how many velociraptors need to be placed, and then repeatedly generate random coordinates on the board and place a velociraptors at that coordinate. Note the care taken to assign at most one velociraptor to each location—otherwise, the if (!board[row][col]) wouldn't be necessary.

If we are dealing with an 8x8 board, a call to placeRandomRaptors(board, 5) might produce the following configuration:

## Checking Safety

At this point, we want to determine whether each of the unoccupied squares (those that are blank in the above drawing) can be attacked by a velociraptor from one or more directions. Pretending for the moment that an isSafe predicate function already exists, we can easily label each of the empty locations as safe or not using the following code snippet:

To determine whether or not a particular location is safe from attack, we need to be able to search in all eight directions to see whether or not a raptor is present in one or more of them. At first glance, we might be interested in writing functions like IsSouthWestSafe, IsSouthSafe, IsSouthEastSafe, etc. and then implement a function IsSafe to simply return the conjunction of all of them. This is not the most elegant solution!

However, doing so requires the implementation of eight distinct helper functions, all of which are basically the same code block with a few minor differences. Just compare two of them (I omit the other six, because once you understand two, you really understand all eight.)

To illustrate, consider the call isSouthWestSafe(board, 5, 6), where the distribution of true and false in the board array corresponds to the placement of raptors in the graphic presented below. Notice that the specified location is circled, and that each of the locations positioned southwest of it are labeled by the order isSouthWestSafe would visit them. The isSouthWestSafe function would examine all squares along that direction until it hits the edge of the board, or until it references a location storing a raptor. For this call, we expect the algorithm to return true.

However, a call to isSouthWestSafe(board, 6, 5) would return false, because the (2, 1) location of the board is occupied by a velociraptor. Check out the following graphic to see:

This algorithm requires the implementation of eight distinct helper functions, all of which are basically the same code block with a few minor differences. Just compare two of them (I omit the other six, because once you understand two, you really understand all eight.)

## Elegant Solution

My major problem with this implementation is that all eight directional checks currently have their own function, but all eight are really doing the same thing (you've seen two, but you can imagine that the other six look pretty much the same.) The only difference between each is the manner in which we update the row and col variables to move in a particular direction:

 SouthWest row and col are each decremented with each move South row gets decremented with each move, but col remains the same SouthEast row gets decremented and col gets incremented with each move West row remains the same, but col gets decremented with each move East row remains the same, but col gets incremented with each move NorthWest row gets incremented and col gets decremented with each move North row gets incremented with each move, but col remains the same NorthEast row and col are each incremented with each move

We should generalize our notions of eight different functions to a single function, using delta x and delta y values to specify the direction. This is an elegant solution!

Need to search southwest from index (6,5)?
Call isDirectionSafe(board, 6, 5, -1, -1).

Need to search south from index (6,5)?
Call isDirectionSafe(board, 6, 5, -1, 0).

Need to search east from the origin?
Call isDirectionSafe(board, 0, 0, 0, 1).

This allows us to unify common functionality to a single helper function, not eight of them, and it also makes the implementation of the isSafe function (the one that checks all eight directions, not just one) more compact.