FRQ 2016 #3: Crossword Puzzle Labeling

Complete Solution with Detailed Explanation

Problem Overview

A crossword puzzle grid is a 2D array where some squares are black (blocked) and some are white (playable). Only certain white squares get labeled with positive numbers according to the Crossword Labeling Rule.

Crossword Labeling Rule

A white square is labeled if and only if:

  • The square is white (not black), AND
  • At least one of these is true:
    • No white square immediately above (top row or square above is black)
    • No white square immediately to the left (left column or square to left is black)

Numbers are assigned consecutively in row-major order starting at 1.

Example Grid

[B W W]    [BLACK 1 2]
[W W B] → [3     0 BLACK]
[W W W]    [4     5 6]

Where B = black, W = white, 0 = unlabeled white square

Part (a): toBeLabeled Method - 3 points

What It Does

Returns true if the square at position [r][c] should be labeled according to the crossword labeling rule.

The Logic (Step by Step)

  1. Check if white: !blackSquares[r][c]
  2. Check top/left boundary:
    • r == 0 → In first row (nothing above)
    • c == 0 → In first column (nothing to left)
    • blackSquares[r-1][c] → Square above is black
    • blackSquares[r][c-1] → Square to left is black

If the square is white AND at least one boundary condition is true → labeled

Key Insight

The four conditions in the OR check cover all ways a white square can be the start of a clue:

  • First row always starts a down clue
  • First column always starts an across clue
  • Black square above means start of a down clue
  • Black square to left means start of an across clue
// PART (a) SOLUTION - toBeLabeled
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]));
}

/* Scoring (3 points):
 * +1 Checks blackSquares[r][c]
 * +1 Checks for a black square or grid border above and to the left (no bounds errors)
 * +1 Returns correct boolean result
 */

Part (b): Crossword Constructor - 6 points

What It Does

Creates a crossword puzzle grid with:

  1. Same dimensions as the blackSquares input
  2. Each cell contains a Square object with correct color and number
  3. Only squares that satisfy toBeLabeled() get positive numbers (1, 2, 3, …)
  4. All other squares get 0

Algorithm Overview

Step 1: Initialize puzzle grid with correct dimensions

puzzle = new Square[blackSquares.length][blackSquares[0].length];

Step 2: Loop through ALL cells in row-major order (ensures consecutive numbering)

for (int r = 0; r < blackSquares.length; r++)
  for (int c = 0; c < blackSquares[r].length; c++)

Step 3: For each cell, check if it should be labeled

  • If toBeLabeled() returns true → Create Square with current label (then increment)
  • Otherwise → Create Square with label 0

Step 4: All squares get a Square object (whether labeled or not)

Key Points for Full Credit

Initialize puzzle with blackSquares.length and blackSquares[0].length se toBeLabeled() to determine labeling ssign correct color based on blackSquares[r][c] umbers increment: 1, 2, 3, … (only for labeled squares) Every cell gets a Square object Row-major order for numbering

// PART (b) SOLUTION - Crossword Constructor
public Crossword(boolean[][] blackSquares)
{
    // Initialize puzzle with correct dimensions (+1 point)
    puzzle = new Square[blackSquares.length][blackSquares[0].length];
    int label = 1;
    
    // Access all locations in puzzle (+1 point)
    for (int r = 0; r < blackSquares.length; r++)
    {
        for (int c = 0; c < blackSquares[r].length; c++)
        {
            // Call toBeLabeled correctly (+1 point)
            if (toBeLabeled(r, c, blackSquares))
            {
                // Create Square with consecutive label starting at 1 (+2 points)
                puzzle[r][c] = new Square(blackSquares[r][c], label);
                label++;
            }
            else
            {
                // Create Square with 0 if not labeled (+1 point)
                puzzle[r][c] = new Square(blackSquares[r][c], 0);
            }
        }
    }
}

/* Scoring (6 points):
 * +1 Initializes puzzle with correct dimensions
 * +1 Accesses all locations in puzzle
 * +1 Calls toBeLabeled correctly
 * +1 Creates and assigns Square objects
 * +1 Labels squares consecutively in row-major order starting at 1
 * +1 Final grid has correct color and numbers
 */

// COMPLETE WORKING SOLUTION WITH TEST CASES

class Square {
    private boolean isBlack;
    private int num;

    public Square(boolean isBlack, int num) {
        this.isBlack = isBlack;
        this.num = num;
    }

    public String toString() {
        return isBlack ? "BLACK" : String.valueOf(num);
    }
}

public class Crossword {
    private Square[][] puzzle;

    // Part (a): Check if square should be labeled
    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]));
    }

    // Part (b): Constructor
    public Crossword(boolean[][] blackSquares)
    {
        puzzle = new Square[blackSquares.length][blackSquares[0].length];
        int label = 1;
        
        for (int r = 0; r < blackSquares.length; r++)
        {
            for (int c = 0; c < blackSquares[r].length; c++)
            {
                if (toBeLabeled(r, c, blackSquares))
                {
                    puzzle[r][c] = new Square(blackSquares[r][c], label);
                    label++;
                }
                else
                {
                    puzzle[r][c] = new Square(blackSquares[r][c], 0);
                }
            }
        }
    }

    // Display the puzzle grid
    public void displayGrid() {
        for (int r = 0; r < puzzle.length; r++) {
            for (int c = 0; c < puzzle[r].length; c++) {
                System.out.print(puzzle[r][c] + "\t");
            }
            System.out.println();
        }
    }

    // Test cases
    public static void main(String[] args) {
        // Test 1: 3x3 grid (from problem statement)
        System.out.println("TEST 1: 3x3 Grid");
        System.out.println("Input: {[T,F,F], [F,F,T], [F,T,F]}");
        boolean[][] test1 = {
            {true, false, false},
            {false, false, true},
            {false, true, false}
        };
        
        Crossword cw1 = new Crossword(test1);
        System.out.println("Output:");
        cw1.displayGrid();
        System.out.println("Expected: [BLACK, 1, 2] / [3, 0, BLACK] / [4, BLACK, 5]\n");

        // Test 2: All white (no black squares)
        System.out.println("TEST 2: All White 2x2");
        System.out.println("Input: {[F,F], [F,F]}");
        boolean[][] test2 = {
            {false, false},
            {false, false}
        };
        
        Crossword cw2 = new Crossword(test2);
        System.out.println("Output:");
        cw2.displayGrid();
        System.out.println("Expected: [1, 2] / [3, 0]\n");

        // Test 3: Larger grid with mixed black/white
        System.out.println("TEST 3: 4x4 Mixed Grid");
        System.out.println("Input: {[F,F,T,F], [T,F,F,F], [F,F,T,F], [F,T,F,F]}");
        boolean[][] test3 = {
            {false, false, true, false},
            {true, false, false, false},
            {false, false, true, false},
            {false, true, false, false}
        };
        
        Crossword cw3 = new Crossword(test3);
        System.out.println("Output:");
        cw3.displayGrid();
        System.out.println();
    }
}

// Run tests
Crossword.main(new String[]{});

TEST 1: 3x3 Grid
Input: {[T,F,F], [F,F,T], [F,T,F]}
Output:
BLACK	1	2	
3	0	BLACK	
4	BLACK	5	
Expected: [BLACK, 1, 2] / [3, 0, BLACK] / [4, BLACK, 5]

TEST 2: All White 2x2
Input: {[F,F], [F,F]}
Output:
1	2	
3	0	
Expected: [1, 2] / [3, 0]

TEST 3: 4x4 Mixed Grid
Input: {[F,F,T,F], [T,F,F,F], [F,F,T,F], [F,T,F,F]}
Output:
1	2	BLACK	3	
BLACK	4	5	0	
6	0	BLACK	7	
8	BLACK	9	0

Detailed Walkthrough: Test Case 1

Given grid:

Input:  {[T,F,F],     Output: [BLACK, 1,   2  ]
         [F,F,T],              [3,    0,   BLACK]
         [F,T,F]}              [4,    BLACK, 5  ]

Step-by-Step Execution

Iteration through row-major order:

r,c Value toBeLabeled? Reason Result
0,0 T (black) N/A Black square Square(true, 0)
0,1 F (white) YES r==0 (top row) Square(false, 1), label→2
0,2 F (white) YES r==0 (top row) Square(false, 2), label→3
1,0 F (white) YES c==0 (left col) Square(false, 3), label→4
1,1 F (white) NO [0,1]&[1,0] both white Square(false, 0)
1,2 T (black) N/A Black square Square(true, 0)
2,0 F (white) YES c==0 (left col) Square(false, 4), label→5
2,1 T (black) N/A Black square Square(true, 0)
2,2 F (white) YES [2,1] is black Square(false, 5), label→6

Notice: position [1,1] is NOT labeled because:

  • Position above [0,1] is WHITE
  • Position to left [1,0] is WHITE
  • So it’s NOT the start of any clue

Summary: What Earns Full 9 Points

Part (a) - 3 points:

  • Checks if square is white ✓
  • Checks boundaries correctly without causing IndexOutOfBoundsException ✓
  • Returns correct boolean ✓

Part (b) - 6 points:

  • Initializes puzzle with right dimensions ✓
  • Accesses all cells (double loop) ✓
  • Calls toBeLabeled() appropriately ✓
  • Creates Square objects properly ✓
  • Numbers are consecutive (1,2,3,…) in row-major order ✓
  • Final grid matches expected output ✓