Chapter 213

How Many Crossword Puzzles Can You Make?

Riddler Express

Given a two-character, seven-segment display (the kind on a microwave clock), how many numbers can you make that are not ambiguous if the display happens to be upside down? For example, $81$ would not fit this criterion: upside-down it shows $18$ . The number $71$ is fine: upside-down it appears as something like “ $1\mathrm{L}$ ”, not a number.

The Riddler, FiveThirtyEight, January 18, 2019(original post)

Solution

The display shows two characters drawn with the standard seven-segment alphabet. When the display is rotated $180^{\circ}$ , two things happen at once: (i) each individual digit is rotated $180^{\circ}$ , and (ii) the order of the two positions swaps (the right digit becomes the left and vice versa).

The digit-flip table. Rotated $180^{\circ}$ , the standard seven-segment digits are $0 \to 0, \quad 1 \to 1, \quad 2 \to 2, \quad 5 \to 5, \quad 8 \to 8, \quad 6 \to 9, \quad 9 \to 6,$ and $3, 4, 7$ each rotate into a shape that is not any digit (a backwards $\mathrm{E}$ , an $\mathrm{h}$ -like glyph, an $\mathrm{L}$ ). Write $D = \{0, 1, 2, 5, 8, 6, 9\}$ for the seven digits that survive a flip as a digit, and $N = \{3, 4, 7\}$ for the three that flip to non-digits.

When is the display ambiguous? A two-character display $ab$ is read by another viewer (looking at it upside down) as $\mathrm{flip}(b)\mathrm{flip}(a)$ , where $\mathrm{flip}(\cdot)$ is the rotation of a single character. The display is ambiguous when the flipped reading is a different valid two-digit number, that is, when $\mathrm{flip}(a)$ and $\mathrm{flip}(b)$ are both digits and $\mathrm{flip}(b)\mathrm{flip}(a) \ne ab$ . Equivalently, the display is not ambiguous in either of two disjoint cases:

Flip is not a number. At least one of $a$ or $b$ is in $N = \{3, 4, 7\}$ , so the flipped display contains a non-digit glyph and cannot be read as any number.
Flip is the same number. Both $a$ and $b$ are in $D$ , and $\mathrm{flip}(b)\mathrm{flip}(a) = ab$ , that is, $\mathrm{flip}(b) = a$ and $\mathrm{flip}(a) = b$ . The pairs satisfying $\mathrm{flip}(a) = b$ , $\mathrm{flip}(b) = a$ for $a, b \in D$ are $\{(0,0), (1,1), (2,2), (5,5), (8,8), (6,9), (9,6)\}$ , seven pairs.

Counting. The total number of two-character displays is $10^{2} = 100$ . The count of ambiguous displays is easier than the unambiguous: a display is ambiguous iff both $a, b \in D$ and the flip is a different number. The number of $(a, b)$ with both in $D$ is $7^{2} = 49$ , and the seven self-mapping pairs above are the ones that flip to themselves; the remaining $49 - 7 = 42$ flip to a different valid two-digit number, hence are ambiguous. So the unambiguous count is $100 - 42 \;=\; 58.$

$\boxed{\#\{\text{unambiguous displays}\} \;=\; 58.}$

The computation

Encode the problem directly: enumerate all $100$ two-character displays $\{00, 01, \ldots, 99\}$ , apply the digit-flip table to each character, swap order, and count how many displays are not ambiguous in the sense of the prompt.

Build the digit-flip table.
For each display $ab$ , compute the flipped reading.
Mark the display unambiguous if the flipped reading is not a valid number or equals $ab$ .
Print the unambiguous count.

FLIP = {'0': '0', '1': '1', '2': '2', '5': '5', '8': '8',
        '6': '9', '9': '6'}  # 3, 4, 7 are absent: not digits

def flipped_reading(s):
    return ''.join(FLIP.get(c, '?') for c in s[::-1])

count = 0
for n in range(100):
    s = f"{n:02d}"
    f = flipped_reading(s)
    if '?' in f or f == s:
        count += 1
print(f"Unambiguous two-character displays: {count}")

The script prints $58$ , matching the boxed answer.

Riddler Classic

Crossword grids obey a few rules. They are $15 \times 15$ and rotationally symmetric (the grid looks the same when turned upside down). All maximal horizontal and vertical runs of white squares (“words”) are at least three squares long. Every white square is part of an across word and a down word. The grid is entirely connected: no islands of white squares separated from the rest by black squares. First question: how many such grids are there? Second question: how many are there with no “cheater squares”, that is, no black squares whose removal would not change the total word count? Extra credit: the Sunday $21 \times 21$ grid, with and without cheater squares.

The Riddler, FiveThirtyEight, January 18, 2019(original post)

Solution

The puzzle is a counting problem with no known closed form at $N = 15$ . The right setup is to state the constraints precisely, count exhaustively for small $N$ (where the answers are known), and then explain why the same enumeration becomes intractable at $N = 15$ . The puzzle’s official write-up confirms that $N = 15$ remains an open problem as of January 2019; the largest published exact count is Jim Ferry’s $N = 13$ result, $40{,}575{,}832{,}476$ .

The constraints, formally. Let $G \in \{0, 1\}^{N \times N}$ encode the grid, with $0$ for white and $1$ for black. Then $G$ is a valid crossword grid iff

Rotational symmetry. $G(r, c) = G(N - 1 - r, N - 1 - c)$ for all $r, c$ .
Word length. Every maximal run of $0$ s in any row or column has length $\ge 3$ .
Connectivity. The white squares form a single $4$ -connected component.

The third constraint “every white square is part of an across word and a down word” is implied by the word-length constraint: if a white square is in any row run, that row run has length $\ge 3$ , so the square is part of an across word; same for columns.

Small cases. Because of $180^{\circ}$ symmetry, a grid is determined by the cells in a representative half. For odd $N$ , that half has $(N^{2} + 1)/2$ cells. For $N = 7$ this is $25$ , well within exhaustive reach: $2^{25} \approx 3.4 \cdot 10^{7}$ symmetric layouts, of which only those satisfying word-length and connectivity survive. The brute count is $W_{7} \;=\; 397,$ which matches Laurent Lessard’s published enumeration in the official solution. The same brute approach handles small $N$ , but the search space doubles every two cells of the representative half: from $W_{7} = 397$ , the count climbs into the millions by $N = 11$ and the billions by $N = 13$ . Direct exhaustive enumeration at $N = 15$ is far out of reach (one representative half has $113$ cells; $2^{113}$ symmetric layouts), and even the cleverest dynamic-programming approaches reported in the official did not pin down the exact $15 \times 15$ count.

The headline. The exact count $W_{15}$ (with or without cheater squares) is open. The largest exact value the official cites is the $N = 13$ count from Jim Ferry, $W_{13} \;=\; 40{,}575{,}832{,}476.$ The puzzle’s question is therefore best answered by reporting the small- $N$ enumeration that the computation below performs in full, and stating the open status at $N = 15$ .

The computation

Encode the rules directly: iterate over all $180^{\circ}$ -symmetric black/white assignments on a representative half, reconstruct the full grid, check word-length and connectivity, and count valid grids. Run it up to $N = 7$ for an exact match against the published total; the same code handles $N = 9$ in seconds and stops being feasible past $N = 11$ .

Enumerate the orbits of the cell positions under $180^{\circ}$ rotation; each orbit is set black or white as a single bit.
For each bitmask, fill in the full grid using the orbit map.
Check that every maximal white run in every row and every column has length $\ge 3$ .
Check that the white cells form one $4$ -connected component.
Tally the valid grids and print.

from collections import deque

def count_grids(N):
    orbits, seen = [], set()
    for r in range(N):
        for c in range(N):
            if (r, c) in seen:
                continue
            ro, co = N - 1 - r, N - 1 - c
            orbit = {(r, c), (ro, co)}
            for p in orbit:
                seen.add(p)
            orbits.append(tuple(orbit))
    M = len(orbits)

    def valid(g):
        for r in range(N):
            run = 0
            for c in range(N):
                if g[r][c] == 0:
                    run += 1
                else:
                    if 0 < run < 3:
                        return False
                    run = 0
            if 0 < run < 3:
                return False
        for c in range(N):
            run = 0
            for r in range(N):
                if g[r][c] == 0:
                    run += 1
                else:
                    if 0 < run < 3:
                        return False
                    run = 0
            if 0 < run < 3:
                return False
        whites = [(r, c) for r in range(N)
                  for c in range(N) if g[r][c] == 0]
        if not whites:
            return False
        seen_w = {whites[0]}
        q = deque([whites[0]])
        while q:
            r, c = q.popleft()
            for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                nr, nc = r + dr, c + dc
                if (0 <= nr < N and 0 <= nc < N
                        and g[nr][nc] == 0
                        and (nr, nc) not in seen_w):
                    seen_w.add((nr, nc))
                    q.append((nr, nc))
        return len(seen_w) == len(whites)

    total = 0
    for mask in range(1 << M):
        g = [[0] * N for _ in range(N)]
        for i in range(M):
            if (mask >> i) & 1:
                for r, c in orbits[i]:
                    g[r][c] = 1
        if valid(g):
            total += 1
    return total

for N in (3, 5, 7):
    print(f"N={N}: {count_grids(N)} valid grids")

The script prints $W_{3} = 1$ (the empty all-white grid), $W_{5} = 15$ , $W_{7} = 397$ . The $N = 7$ value matches Laurent Lessard’s published count and confirms the encoding; larger $N$ are handled by the same code (a faster dynamic-programming variant is needed past $N \approx 9$ ).