Crossword: 2016 FRQ 3

Numbering a crossword grid the way real puzzle books do turns out to be a neat little exercise in checking a 2D array's neighbors — this AP Computer Science A free-response question has you decide which squares deserve a number before building the whole labeled grid from scratch.

What This FRQ Tests

• AP CSA units: Unit 8 (2D Array) and Unit 4 (Iteration)
• Core skill: checking a cell's up and left neighbors in a 2D array without ever indexing off the edge of the grid
• Secondary skill: building an entire 2D array of objects while a counter keeps incrementing across nested loops
• Official category: "2D Array" — the category the modern fixed ordering assigns to FRQ 4, but the 2016 booklet prints this question as FRQ 3. Paired with this same year's FRQ 4 (StringFormatter, which tests Array/ArrayList — normally FRQ 3's slot), the two categories are effectively swapped relative to the modern pattern, the same kind of deviation documented for 2018.

The Setup

• A Square is built with Square(boolean isBlack, int num) — already implemented, not something you need to write.
• A Crossword holds private Square[][] puzzle, where puzzle[r][c] is the square at row r, column c.
• The crossword labeling rule: a square gets a positive number if and only if it's white, and it either has no white square directly above it, or no white square directly to its left (or both). Being in the top row counts as "no white square above"; being in the leftmost column counts as "no white square to the left."
• Labeled squares are numbered with consecutive positive integers in row-major order, starting at 1. Every other square (black squares, and white squares that don't qualify) gets the number 0.
• Two things to write: private boolean toBeLabeled(int r, int c, boolean[][] blackSquares) (part a), and the Crossword(boolean[][] blackSquares) constructor (part b).

Part (a): Writing toBeLabeled

The Rule, Broken Down

1. blackSquares[r][c] tells you whether square (r, c) is black — only white squares can ever be labeled.
2. "No white square above" is true when r == 0 (nothing is above the top row at all) or blackSquares[r - 1][c] is true.
3. "No white square to the left" is true when c == 0 or blackSquares[r][c - 1] is true.
4. The square is labeled when it's white and at least one of those two neighbor conditions holds.

Step-by-Step Approach

1. If the square itself is black, it can never be labeled — return false immediately, without even looking at its neighbors.
2. Otherwise, check whether there's no white square above.
3. Also check whether there's no white square to the left.
4. Return true if either of those two checks came back true.

The Code

private boolean toBeLabeled(int r, int c, boolean[][] blackSquares)
{
    if (blackSquares[r][c])
    {
        return false;
    }

    boolean noWhiteAbove = (r == 0) || blackSquares[r - 1][c];
    boolean noWhiteToLeft = (c == 0) || blackSquares[r][c - 1];

    return noWhiteAbove || noWhiteToLeft;
}

Why Each Piece Matters

• Returning false immediately for a black square means the rest of the method never has to reason about "what are a black square's neighbors" — black squares are simply excluded before that question is ever asked.
• (r == 0) || blackSquares[r - 1][c] relies on Java's short-circuit evaluation: || checks its left side first, and only evaluates the right side if the left side was false. Since r == 0 is checked first, blackSquares[r - 1][c] is never evaluated when r is 0 — which is exactly what avoids an ArrayIndexOutOfBoundsException from indexing row -1. The same logic protects blackSquares[r][c - 1] when c == 0.
• "No white square above" also covers a genuine black square directly above the same way it covers being in the top row — both mean nothing white is blocking a new labeled entry from starting there.

Tracing the Example

The official diagram illustrates the rule graphically rather than as a text table, so the exact grid isn't reproduced cell-by-cell here — but it includes four explicit callouts that exercise every branch of this method:

• Two squares are annotated "Labeled because no white square above and no white square to the left." For these, both noWhiteAbove and noWhiteToLeft are true at once, so the final || is true for two independent reasons simultaneously.
• One square is annotated "Labeled because no white square above" alone — meaning a white square does sit to its left (noWhiteToLeft is false there), but it's still labeled, since the || only needs one side to be true.
• One square is annotated "Labeled because no white square to the left" alone — the mirror case: a white square sits above it, but it's still labeled because of its left side.
• Two squares are annotated "Unlabeled." A square ends up unlabeled either because it's black (the very first check returns false before any neighbor is examined), or because it's white but has both a white square above it and a white square to its left (both noWhiteAbove and noWhiteToLeft come back false, so the || is false too). Either way, the method above correctly returns false for it.

Together, these four callouts confirm all three ways a square can end up labeled (above-only, left-only, or both) plus the exclusion of unqualified squares — and the method matches the documented result in every case.

Part (b): Writing the Crossword Constructor

The Rule, Broken Down

1. puzzle must end up with the exact same dimensions as blackSquares.
2. Every cell gets a new Square object built with the correct isBlack value.
3. White cells that satisfy toBeLabeled get consecutive positive numbers, starting at 1, assigned in row-major order.
4. Every other cell (black cells, and white cells that don't qualify) gets the number 0.

Step-by-Step Approach

1. Allocate puzzle as new Square[blackSquares.length][blackSquares[0].length] — matching dimensions exactly, rather than hardcoding any size.
2. Declare a running counter, nextNumber, starting at 1, outside both loops so it persists across the entire grid, not just one row.
3. Loop over every row r, then every column c within that row — nested loops naturally visit cells in row-major order.
4. For each cell: if it's black, create Square(true, 0). If it's white and toBeLabeled returns true, create Square(false, nextNumber) and then increment nextNumber. Otherwise, create Square(false, 0).
5. Store the new Square into puzzle[r][c].

The Code

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

    for (int r = 0; r < blackSquares.length; r++)
    {
        for (int c = 0; c < blackSquares[0].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, nextNumber);
                nextNumber++;
            }
            else
            {
                puzzle[r][c] = new Square(false, 0);
            }
        }
    }
}

Why Each Piece Matters

• new Square[blackSquares.length][blackSquares[0].length] copies blackSquares's exact dimensions instead of assuming any particular size, so the constructor works for a grid of any shape.
• nextNumber is declared before both loops, not reset inside either one — if it were reinitialized inside the outer (row) loop, every row would incorrectly restart numbering at 1 instead of continuing across the whole grid.
• else if (toBeLabeled(...)) only runs for cells already known to be white — since black cells are handled in the first branch, this skips a redundant re-check of blackSquares[r][c] that toBeLabeled would otherwise repeat internally.
• The nested loop structure itself is row-major order — every column of one row finishes before the next row starts, so no separate sorting step is ever needed to satisfy that requirement.

Common Mistakes to Avoid

• Declaring int nextNumber = 1 inside the outer (row) loop instead of before it — this resets numbering back to 1 at the start of every row instead of continuing it across the whole grid.
• Using blackSquares.length for the number of columns instead of blackSquares[0].length — grid dimensions are rows-then-columns, and mixing these up is common enough that it's one of the official 2016 scoring guideline's named penalties ("Uses array[].length instead of array[num].length").
• Forgetting to increment nextNumber after creating a labeled Square — every labeled square from that point on would incorrectly get the same number.
• Calling toBeLabeled on a square already known to be black and trusting its result without ever checking blackSquares[r][c] directly — this still works (since toBeLabeled returns false for black squares), but skips the more direct, more efficient check.

Key Takeaways

• Checking edge conditions (r == 0, c == 0) before indexing a neighboring cell, using short-circuit || or &&, is the standard way to avoid an ArrayIndexOutOfBoundsException when examining a 2D array's neighbors.
• A counter that has to persist across an entire nested loop — like row-major numbering across a whole grid — must be declared outside both loops, never reset anywhere inside them.
• Splitting "does this square qualify" into its own method (toBeLabeled) and calling it from inside the constructor keeps the labeling rule's logic in exactly one place, even while it's being used to build an entire 2D array of objects.