BlockNumber

BlockNumber is the puzzle of counting up each region. The grid is partitioned into irregular regions (the “blocks”), and every block carries an implicit local counter: a block of size $n$ must be filled with the numbers $1, 2, \ldots, n$, each exactly once. Some cells inside blocks are pre-filled as clues. A single further rule knits the blocks together: no two cells that are adjacent in the king-move sense (orthogonally or diagonally) may hold the same number, even across a block boundary.

The king-move constraint is the puzzle’s signature. Where Sudoku forbids repetition along rows, columns, and regions, BlockNumber forbids repetition in every $3 \times 3$ neighbourhood around every cell. This makes solving feel like threading a low-collision schedule: small blocks (size $1$ or $2$) are forced by their neighbours’ values, and the force propagates outward through the king-move contact graph.

BlockNumber is one of the younger Japanese pencil puzzles collected in Alex Bellos’s Puzzle Ninja anthology. The block partition is hand-designed so that the combination of “count $1$ to block size” and the king-move constraint yields a unique solution. Variants of the puzzle run under different English names (Fillomino-with-bounds, LITS-counter, etc.), but the core rule set is stable.

Rules and a small instance

A BlockNumber puzzle is an $R \times C$ grid of cells, partitioned into disjoint connected blocks $B_1, B_2, \ldots, B_m$ covering every cell. Some cells carry pre-filled positive-integer clues. A solution assigns to every cell a positive integer such that:

1. For every block $B_i$ of size $n_i$, the values assigned to its cells are exactly $\{1, 2, \ldots, n_i\}$, each occurring once.

2. For every pair of cells $(r, c)$ and $(r', c')$ with $\max(|r - r'|, |c - c'|) = 1$ (i.e. king-move adjacent), the values assigned are different.

3. Every pre-filled clue is preserved.

Figure 22.1 is a $4 \times 4$ BlockNumber with four blocks of sizes $3, 4, 4, 5$ and two clues.

The programming model

Assign each cell $(r, c)$ an integer variable $v_{r, c}$. If the cell belongs to a block of size $n$, its domain is $\{1, 2, \ldots, n\}$.

Block domains and uniqueness

For every block $B = \{(r_1, c_1), \ldots, (r_n, c_n)\}$ of size $n$, $$v_{r_i, c_i} \in \{1, 2, \ldots, n\} \qquad \text{and} \qquad \operatorname{AllDifferent}(v_{r_1, c_1}, \ldots, v_{r_n, c_n}).$$ Together these assert that $B$’s values are a permutation of $\{1, 2, \ldots, n\}$.

King-move no-equal

For every cell $(r, c)$ and each of its eight king-move neighbours $(r + \delta_r, c + \delta_c)$ with $\max(|\delta_r|, |\delta_c|) = 1$ lying inside the grid: $$v_{r, c} \;\ne\; v_{r + \delta_r, c + \delta_c}.$$ Because the relation is symmetric, the constraint is posted only for ordered pairs $((r, c), (r', c'))$ with $(r, c) < (r', c')$ lexicographically.

Clue preservation

For every pre-filled cell $(r, c)$ with clue $k$, $$v_{r, c} \;=\; k.$$

A CP-SAT solver

from ortools.sat.python import cp_model

def solve_blocknumber(blocks, R, C):
    """blocks: list of dicts {(r,c): clue or ""};
       each dict is one block."""
    m = cp_model.CpModel()
    v = {}
    for block in blocks:
        n = len(block)
        for (r, c) in block:
            v[(r, c)] = m.NewIntVar(1, n, "")
    # Clue preservation
    for block in blocks:
        for (r, c), clue in block.items():
            if isinstance(clue, int):
                m.Add(v[(r, c)] == clue)
    # Block all-different
    for block in blocks:
        m.AddAllDifferent([v[c] for c in block])
    # King-move no-equal
    for (r, c) in v:
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                if (dr, dc) == (0, 0): continue
                nb = (r + dr, c + dc)
                if nb in v and nb > (r, c):
                    m.Add(v[(r, c)] != v[nb])
    s = cp_model.CpSolver()
    status = s.Solve(m)
    if status not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        raise RuntimeError(
            "no solution: " + s.StatusName(status))
    return {c: s.Value(v[c]) for c in v}

The toy of Figure 22.1 solves uniquely in about $15$ milliseconds.

A hard instance

Figure 22.3 is a $7 \times 7$ BlockNumber with twelve blocks of mixed sizes (ranging from $2$ to $5$), a single clue, and $49$ cells to fill. The block partition is visible from the thick boundary lines. CP-SAT returns the unique solution in about $4$ milliseconds.

Sources. BlockNumber is a contemporary Japanese pencil-puzzle kind collected in Alex Bellos’s Puzzle Ninja: Pit Your Wits Against the Japanese Puzzle Masters (Guardian Faber, $2017$), where the style is sometimes attributed to the Puzzle Communication Nikoli tradition of irregular-region fillers. The king-move constraint distinguishes BlockNumber from its closer relative Fillomino (Chapter $16$), which forbids only orthogonal equal neighbours and has no fixed block sizes. Compu­tational complexity of BlockNumber is open; like most region filler puzzles, it is likely NP-complete under suitable complexity-theoretic reductions, but no published proof is known.