Problem 522: Hilbert’s Blackout

Mathematical Foundation

Theorem (Hilbert Curve Bijection). For every $n \ge 1$, the order-$n$ Hilbert curve defines a bijection

such that consecutive indices map to grid-adjacent cells (sharing an edge).

Proof. We proceed by induction on $n$.

Base case ($n = 1$): The order-1 curve visits the four cells of a $2 \times 2$ grid in the order $(0,0) \to (0,1) \to (1,1) \to (1,0)$. Each consecutive pair is adjacent. The map is clearly a bijection on a 4-element set.

Inductive step: Assume $H_{n-1}$ is a bijection on the $(2^{n-1})^2$ grid with the adjacency property. Partition the $2^n \times 2^n$ grid into four $2^{n-1} \times 2^{n-1}$ quadrants. Define $H_n$ by traversing:

1. Bottom-left quadrant using $H_{n-1}$ reflected about the diagonal ($90^\circ$ CW rotation),
2. Top-left quadrant using $H_{n-1}$ (unmodified),
3. Top-right quadrant using $H_{n-1}$ (unmodified),
4. Bottom-right quadrant using $H_{n-1}$ reflected about the anti-diagonal ($90^\circ$ CCW rotation).

Each quadrant contributes $4^{n-1}$ cells, giving $4 \cdot 4^{n-1} = 4^n$ total. The junction points between quadrants are adjacent by construction (the exit of one quadrant neighbors the entry of the next). By induction, within each quadrant consecutive indices are adjacent. Hence $H_n$ is a bijection with the adjacency property. $\square$

Lemma (Self-Similar Counting). Let $C_n$ denote the count of surviving lights after the blackout operation on an order-$n$ grid. If the blackout condition respects the 4-fold recursive structure of the Hilbert curve (i.e., the condition on index $d$ depends only on $d \bmod 4^k$ for some fixed $k$), then $C_n$ satisfies a linear recurrence of the form

for constants $\alpha, \beta$ determined by the blackout rule applied to the quadrant junctions.

Proof. When the blackout condition depends only on $d \bmod 4^k$, the number of blackout positions in each quadrant of an order-$n$ curve is determined by the number of blackout positions in an order-$(n-1)$ curve, shifted by a fixed offset modulo $4^k$. Since the four quadrants tile the index space $[0, 4^n)$ into four contiguous blocks of size $4^{n-1}$, each block’s count depends on $C_{n-1}$ plus a bounded correction from the offset. The correction is constant in $n$ for $n > k$. $\square$

Editorial

Grid blackout puzzle on Hilbert curve grids. We base: enumerate all 4^k positions for small k. We then recursive: exploit self-similarity. Finally, determine counts for each quadrant transformation.

Pseudocode

Base: enumerate all 4^k positions for small k
Recursive: exploit self-similarity
Determine counts for each quadrant transformation
rotate quadrant

Complexity Analysis

• Time (direct enumeration): $O(4^n)$, since all positions are visited.
• Time (recursive, structure-respecting blackout): $O(n)$, since the recurrence has constant cost per level.
• Space: $O(n)$ for the recursion stack, or $O(4^n)$ for direct enumeration.

Answer

#include <bits/stdc++.h>
using namespace std;

// Hilbert curve coordinate conversion

pair<int,int> d2xy(int n, int d) {
    int x = 0, y = 0;
    for (int s = 1; s < (1 << n); s <<= 1) {
        int rx = (d & 2) ? 1 : 0;
        int ry = ((d & 1) ^ rx) ? 1 : 0;
        if (ry == 0) {
            if (rx == 1) {
                x = s - 1 - x;
                y = s - 1 - y;
            }
            swap(x, y);
        }
        x += s * rx;
        y += s * ry;
        d >>= 2;
    }
    return {x, y};
}

int xy2d(int n, int x, int y) {
    int d = 0;
    for (int s = (1 << n) >> 1; s > 0; s >>= 1) {
        int rx = (x & s) > 0 ? 1 : 0;
        int ry = (y & s) > 0 ? 1 : 0;
        d += s * s * ((3 * rx) ^ ry);
        if (ry == 0) {
            if (rx == 1) {
                x = s - 1 - x;
                y = s - 1 - y;
            }
            swap(x, y);
        }
    }
    return d;
}

int main() {
    int order;
    cout << "Enter Hilbert curve order: ";
    cin >> order;

    long long total = 1LL << (2 * order);
    cout << "Total cells: " << total << endl;

    // Example: count lights remaining after every k-th blackout
    for (int k : {2, 3, 5, 7}) {
        long long blacked = total / k;
        long long remaining = total - blacked;
        cout << "Blackout every " << k << ": " << remaining << " remaining" << endl;
    }

    // Verify coordinate mapping for small order
    if (order <= 4) {
        int side = 1 << order;
        cout << "\nHilbert curve path:" << endl;
        for (int d = 0; d < total; d++) {
            auto [x, y] = d2xy(order, d);
            int d2 = xy2d(order, x, y);
            if (d != d2) {
                cout << "ERROR: d=" << d << " -> (" << x << "," << y << ") -> " << d2 << endl;
            }
        }
        cout << "Coordinate mapping verified." << endl;
    }

    return 0;
}

"""
Problem 522: Hilbert's Blackout
Grid blackout puzzle on Hilbert curve grids.
"""

def hilbert_d2xy(n: int, d: int):
    """Convert Hilbert curve index d to (x, y) coordinates on 2^n x 2^n grid."""
    x = y = 0
    s = 1
    while s < (1 << n):
        rx = 1 if (d & 2) else 0
        ry = 1 if ((d & 1) ^ rx) else 0
        # Rotate
        if ry == 0:
            if rx == 1:
                x = s - 1 - x
                y = s - 1 - y
            x, y = y, x
        x += s * rx
        y += s * ry
        d >>= 2
        s <<= 1
    return x, y

def hilbert_xy2d(n: int, x: int, y: int):
    """Convert (x, y) coordinates to Hilbert curve index on 2^n x 2^n grid."""
    d = 0
    s = (1 << n) >> 1
    while s > 0:
        rx = 1 if (x & s) > 0 else 0
        ry = 1 if (y & s) > 0 else 0
        d += s * s * ((3 * rx) ^ ry)
        # Rotate
        if ry == 0:
            if rx == 1:
                x = s - 1 - x
                y = s - 1 - y
            x, y = y, x
        s >>= 1
    return d

def generate_hilbert_curve(order: int):
    """Generate all points along a Hilbert curve of given order."""
    n_points = 4 ** order
    points = [hilbert_d2xy(order, d) for d in range(n_points)]
    return points

def blackout_count(order: int, k: int):
    """
    Count lights remaining after blacking out every k-th position
    along the Hilbert curve of given order.
    """
    total = 4 ** order
    blacked = total // k
    return total - blacked

# Compute blackout counts
for order in range(1, 8):
    total = 4 ** order
    for k in [2, 3, 5]:
        remaining = blackout_count(order, k)
        print(f"Order {order} ({total} cells), blackout every {k}: {remaining} remaining")