Difficulty: Intermediate | Prerequisites: 2D arrays, boolean expressions, basic OOP (classes, constructors, instance variables)
This is Free-Response Question 3 from the 2016 AP Computer Science A exam. It sits in the 2D arrays and object-oriented design portion of the course. The problem asks you to model a crossword puzzle grid using two classes, Square and Crossword, and to implement logic that decides which white squares get labelled with a number. If you are comfortable with nested loops and boundary-condition checks on arrays, this one is approachable. If you are not, work through basic 2D array traversal first.
The question tests two skills that appear on nearly every AP CS A exam: writing a method that inspects neighbours in a 2D array (Part A), and writing a constructor that builds one 2D structure from another while applying a rule to each element (Part B).
You are given a 2D boolean array where true means a square is black. A white square gets a label number when it has no white neighbour directly above it, or no white neighbour directly to its left, or both. Part A asks you to write the method that checks this rule. Part B asks you to write a constructor that builds the full Square[][] grid, assigning label numbers in row-major order.
Crossword labeling rule
The rule that decides which white squares in a crossword grid receive a positive number. A white square is labelled if it has no white square immediately above it, or no white square immediately to its left, or both. In simple terms, a square earns a label whenever it could be the start of an Across or Down word.
Square (class)
A class representing one cell in the crossword grid. Its constructor takes a boolean (isBlack) and an int (num). The boolean records the colour. The int holds the label number, or 0 if the square is unlabelled.
Crossword (class)
A class representing the entire crossword grid. It stores a 2D array of Square objects (private Square[][] puzzle). Its constructor receives a boolean[][] blackSquares and builds the grid from it.
boolean[][] blackSquares
The input parameter for both the toBeLabeled method and the Crossword constructor. Each element is true when that position is a black square and false when it is white.
Row-major order
Traversing a 2D array by going across each row from left to right, top row first. This is the order in which label numbers are assigned: the first qualifying square gets 1, the next gets 2, and so on.
Boundary checking (edge cases in a 2D array)
Checking whether a given row or column index is at the edge of the array before trying to access a neighbour. A square in row 0 has no row above it. A square in column 0 has no column to its left. Forgetting these checks causes an ArrayIndexOutOfBoundsException.
A white square receives a positive label number when at least one of these conditions is true:
The square is in the top row (row 0), so there is nothing above it.
The square is in the leftmost column (column 0), so there is nothing to its left.
The square directly above it (row - 1, same column) is black.
The square directly to its left (same row, column - 1) is black.
If the square itself is black, it never gets a label, regardless of its neighbours.
Labels are assigned as consecutive integers starting at 1, in row-major order (left to right across each row, top to bottom).
The method signature is:
private boolean toBeLabeled(int r, int c, boolean[][] blackSquares)It returns true if the square at position (r, c) should receive a label. The precondition guarantees that r and c are valid indices.
Solution:
private boolean toBeLabeled(int r, int c, boolean[][] blackSquares) {
if (blackSquares[r][c]) {
return false;
}
if (r == 0 || c == 0) {
return true;
}
if (blackSquares[r - 1][c] || blackSquares[r][c - 1]) {
return true;
}
return false;
}Walkthrough:
First check: if the square itself is black, return false immediately. Black squares are never labelled.
Second check: if the square is in row 0 or column 0, it must be white (we already ruled out black). A white square on the top edge or left edge always qualifies, because there is no white neighbour above or to the left.
Third check: if the neighbour above is black, or the neighbour to the left is black, this white square starts a new word, so return true.
If none of these conditions fire, the square is white but has white neighbours on both sides that matter, so it does not start a new word. Return false.
A common alternative is to combine the conditions into a single return statement:
private boolean toBeLabeled(int r, int c, boolean[][] blackSquares) {
if (blackSquares[r][c]) {
return false;
}
return r == 0 || c == 0
|| blackSquares[r - 1][c]
|| blackSquares[r][c - 1];
}Both forms earn full marks.
The constructor signature is:
public Crossword(boolean[][] blackSquares)It must initialise the puzzle array to the same dimensions as blackSquares, fill every element with a Square object, and assign label numbers using toBeLabeled.
Solution:
public Crossword(boolean[][] blackSquares) {
puzzle = new Square[blackSquares.length][blackSquares[0].length];
int labelNum = 1;
for (int r = 0; r < blackSquares.length; r++) {
for (int c = 0; c < blackSquares[0].length; c++) {
if (toBeLabeled(r, c, blackSquares)) {
puzzle[r][c] = new Square(blackSquares[r][c], labelNum);
labelNum++;
} else {
puzzle[r][c] = new Square(blackSquares[r][c], 0);
}
}
}
}Walkthrough:
Allocate puzzle with the same row and column counts as blackSquares.
Keep a running counter (labelNum) starting at 1.
Traverse in row-major order (outer loop on rows, inner loop on columns).
For each position, call toBeLabeled. If it returns true, create the Square with the current label number and increment the counter. If it returns false, create the Square with 0.
The colour of the square comes directly from blackSquares[r][c].
Boundary checking in 2D arrays is the same logic used in image processing (checking neighbouring pixels), game boards (chess, minesweeper, Conway's Game of Life), and pathfinding algorithms on grids. Any time you need to look at the cells around a given position and handle edges gracefully, you are doing exactly what toBeLabeled does.
Students often forget to check whether the square itself is black before inspecting its neighbours. The method should return false immediately for any black square, regardless of what surrounds it.
Students sometimes check r > 0 and c > 0 but then use && (AND) instead of || (OR) when combining neighbour checks. The labeling rule says "no white above OR no white to the left," which means you label the square if either neighbour is missing or black, not only when both are.
Some students try to access blackSquares[r-1][c] without first confirming that r > 0. The order of checks matters: test for edge position before accessing a neighbour, or combine them with short-circuit evaluation (r == 0 || blackSquares[r-1][c]).
A less obvious mistake is incrementing the label counter even when the square is not labelled, which throws off every subsequent number.
This question tests two patterns that appear on nearly every AP CS A exam:
Writing a helper method that checks conditions on a 2D array element and its neighbours, with proper boundary handling.
Writing a constructor that builds a new data structure from a raw input array, applying logic per element.
The AP rubric awards separate points for: correctly returning false for black squares, correctly handling edge rows and columns, correctly checking neighbours, and correctly using toBeLabeled inside the constructor with a running label counter.
True or false: a black square can receive a label number if it is in row 0.
False. Black squares are never labelled, regardless of position.
Fill in the blank: label numbers are assigned in ______ order, starting at ______.
Row-major order, starting at 1.
True or false: if a white square has a white neighbour above it AND a white neighbour to its left, it does not get a label.
True. It would not start any new Across or Down word.
True or false: the Crossword constructor should call toBeLabeled to decide each square's number.
True. The question requires you to use toBeLabeled.
Fill in the blank: puzzle is initialised with dimensions blackSquares.______ by blackSquares[0].______.
length by length.
Q: What value does toBeLabeled(0, 3, blackSquares) return if blackSquares[0][3] is false (white)?
A: true. The square is white and sits in row 0, so there is no white square above it. It qualifies for a label.
Q: What value does toBeLabeled(2, 2, blackSquares) return if blackSquares[2][2] is false, blackSquares[1][2] is false, and blackSquares[2][1] is false?
A: false. The square is white, it is not on an edge, and both its upper and left neighbours are also white. It does not start a new word.
Q: In the Crossword constructor, what happens if you initialise labelNum to 0 instead of 1?
A: Every label number would be off by one. The first labelled square would get 0 instead of 1, and all subsequent labels would be one less than they should be. The postcondition requires positive numbers starting at 1.
Q: Why must the constructor pass blackSquares[r][c] (not false or true) as the first argument to the Square constructor?
A: Because some squares are black and some are white. The colour of each square comes from the input array. Hard-coding false would make every square white, violating the postcondition.
Q: A student writes if (blackSquares[r-1][c]) without first checking r > 0. What exception will this cause when r is 0?
A: ArrayIndexOutOfBoundsException, because blackSquares[-1][c] is not a valid index.
This problem connects to the broader topic of 2D array traversal, which appears in questions about image manipulation (e.g., rotating or filtering a 2D pixel array) and game boards. The boundary-checking pattern in toBeLabeled is the same pattern you use in any "check the neighbours" problem, such as counting adjacent mines in Minesweeper.
The constructor in Part B is a good example of the "build one structure from another" pattern. You will see similar constructors in questions that ask you to create an ArrayList from an array, or populate an object graph from raw data.
The use of a helper method (toBeLabeled) inside a constructor also demonstrates separation of concerns, a design principle tested in the AP CS A curriculum under object-oriented design.
AP CS A 2016 FRQ 3, crossword puzzle grid, crossword labeling rule, 2D array traversal, boolean 2D array, boolean[][], Square class, Crossword class, toBeLabeled, row-major order, boundary checking, edge case, ArrayIndexOutOfBoundsException, neighbour checking in arrays, constructor from array, AP Computer Science A free-response, Java 2D array, grid labeling, nested for loop