# Crossword FRQ Solution

The third free response question on the 2016 AP Computer Science exam has you working with a matrix of an arbitrary class. In this case it was a class called `Square`. When put into a matrix these `Square` references formed a crossword puzzle.

You were given a shell of the `Square` class. When you are given arbitrary classes on the AP exam you will certainly use them somewhere in your solution.

``````public class Square {
public Square(boolean isBlack, int num) {
// Implementation not shown
}
}
``````

Note that there is no implementation in `Square`. They are giving you the constructor signature so that you can create new `Square` instances in your code.

## Part A - toBeLabeled

The first part of this problem has you implementing a method called `toBeLabeled`. `toBeLabeled` should return `true` if the following 2 criteria are met.

• The square must be white
• The square does not have a white square immediately above, to the left, or both
``````public boolean toBeLabeled(int r, int c, boolean[][] blackSquares) {
return (!(blackSquares[r][c]) && (r==0 || c==0 || blackSquares[r-1][c] || blackSquares[r][c-1]));
}
``````

We’re given a boolean matrix called `blackSquares` that we’ll use to check if a square is black.

To decide if we should label a square the code first looks to see that it’s not black. Since there’s only two options, that means it’s a white square.

Once we know it’s a white square we’ll look and see if it’s in row or column 0. If it is, the square is labeled. If not we’ll look at the row above and column to the left. If either is white, the current square is not labeled.

## Part B - Constructor

The constructor should take a boolean matrix identifying black squares and store a matrix of `Square` references in the instance variable `puzzle`.

``````public Crossword(boolean[][] blackSquares) {
puzzle = new Square[blackSquares.length][blackSquares.length];
int num = 1;
for (int r=0; r<blackSquares.length; r++) {
for (int c=0; c<blackSquares[r].length; c++) {
if (blackSquares[r][c]) {
puzzle[r][c] = new Square(true, 0);
} else {
if (toBeLabeled(r, c, blackSquares)) {
puzzle[r][c] = new Square(false, num);
num++;
} else {
puzzle[r][c] = new Square(false, 0);
}
}
}
}
}
``````

First step is to instantiate `puzzle` so that it is a 2d array of Square references. It should be the same size as the `blackSquares` parameter. Since this is an AP-A free response we can assume that the matrix is rectangular. All rows will have the same number of columns as row 0.

We also need a variable to keep track of the label number. In the example I call it `num`.

Now we iterate through all of the cells using a nest for loop.

If the square is black, we know it won’t be labeled. So we’ll create a new instance of a black square with a label of `0`.

If the square is white we need to check if it should be labeled. Do that by calling the `toBeLabeled` method created in Part A. If it should be labeled then create a new `Square` instance with a label equal to `num` and then increment `num` for next time. If it should not be labeled use `0` as the label.

## Complete Crossword Class

This is the same code as the examples above, but all together in one file.

``````public class Crossword {

private Square[][] puzzle;

private boolean toBeLabeled( int r, int c, boolean[][] blackSquares ) {
return (!(blackSquares[r][c]) &&
( r == 0 || c == 0 || blackSquares[r-1][c] || blackSquares[r][c-1] );
}

public Crossword(boolean[][] blackSquares) {
puzzle = new Square[blackSquares.length][blackSquares.length];
int num = 1;

for (int r=0; r<blackSquares.length; r++) {
for (int c=0; c<blackSquares[r].length; c++) {
if (blackSquares[r][c]) {
puzzle[r][c] = new Square(true, 0);
}
else {
if (toBeLabeled(r, c, blackSquares) {
puzzle[r][c] = new Square(false, num);
num++;
}
else {
puzzle[r][c] = new Square(false, 0);
}
}
}
}
}
``````
This site contains affiliate links. If you click an affiliate link and make a purchase we may get a small commission. It doesn't affect the price you pay, but it is something we must disclose.