Walls

Walls is the puzzle of minimal strokes. The grid is a rectangle of white cells punctuated by black cells carrying clue integers. The solver fills every white cell with either a short horizontal segment or a short vertical segment, meeting edge-to-edge along adjacent cells to form continuous straight lines. Lines cannot pass through black cells; each line terminates at either a black cell, the grid boundary, or an adjacent perpendicular segment. The clue in a black cell equals the combined length, summed across all four directions, of the line segments terminating at that black cell.

Walls is a piece of puzzle minimalism: no shading, no symbols, no colour, just a lattice of horizontal and vertical strokes. The rules are sparse enough to fit on a single line, but solving a hard instance is a genuine struggle, because the combined-length clue is inherently non-local. The value in a black cell is determined by lines that may start anywhere along the ray from the black cell, and the ray can be arbitrarily long, constrained only by the other black cells and the grid boundary.

Among the solver-friendly logic puzzles, Walls sits on the challenging side of the constraint-modelling spectrum. The clue-to-combined-length rule does not reduce to a local window; it requires the model to count the length of a maximal run of same-type segments extending out from each black cell. Two families of constraints capture this cleanly: one forcing the run lengths to sum to the clue, and an auxiliary family that counts each directional run via a ladder of prefix-all-same indicators.

Rules and a small instance

A Walls puzzle is an $R \times C$ grid of cells. Each cell is either white (empty, to be filled) or black (with a non-negative integer clue). A solution assigns to every white cell one of two tokens: a horizontal segment $\ \texttt{-}\$ or a vertical segment $\ |\$. The solution satisfies:

1. Every black cell’s clue $k$ equals the sum, over the four axial directions, of the length of the maximal run of segments with matching orientation extending from the black cell in that direction (horizontal segments on the east-west axis, vertical segments on the north-south axis). A maximal run terminates at either a black cell, the grid boundary, or the first segment of the opposite orientation.

Figure 20.1 is a $4 \times 4$ Walls puzzle; five black cells carry clues summing to $11$, which fixes the fill of the remaining eleven white cells.

The programming model

For every white cell $(r, c)$ introduce two Boolean variables $h_{r, c}$ and $v_{r, c}$, with $$h_{r, c} + v_{r, c} \;=\; 1,$$ so every white cell hosts exactly one segment orientation. Black cells carry no variables.

The interesting machinery is the directional run length. For a black cell $(r, c)$ and a direction $\vec{d} \in \{(0, 1), (0, -1), (1, 0), (-1, 0)\}$, let $c_1, c_2, \ldots, c_{D}$ be the consecutive white cells extending from $(r, c)$ in direction $\vec{d}$ up to (but not including) the first black cell or the grid edge. The length of the run ending at $(r, c)$ from direction $\vec{d}$ is $$L \;=\; |\{ i \,:\, c_1, c_2, \ldots, c_i \text{ all carry the matching orientation} \}|.$$ Here “matching orientation” means $h = 1$ for the east-west directions, $v = 1$ for north-south.

To encode $L$ in CP-SAT, introduce for each $K \in \{1, 2, \ldots, D\}$ a Boolean indicator $b_K$ with $$b_K = 1 \iff s_1 + s_2 + \cdots + s_K = K,$$ where $s_i$ is the matching variable at $c_i$. In other words, $b_K$ asserts that the first $K$ cells along the ray all have the matching orientation. Then $$L \;=\; \sum_{K = 1}^{D} b_K,$$ because $b_K$ drops from $1$ to $0$ at exactly the index $K$ where the run first breaks.

For each black cell with clue $k$, the clue constraint is $$L^{\mathrm{right}} + L^{\mathrm{left}} + L^{\mathrm{up}} + L^{\mathrm{down}} \;=\; k.$$

A solver in forty-five lines

from ortools.sat.python import cp_model

def solve_walls(board):
    """board[r][c] = -1 for white cell,
       non-negative int for black clue."""
    R, C = len(board), len(board[0])
    m = cp_model.CpModel()
    h, v = {}, {}
    for r in range(R):
        for c in range(C):
            if board[r][c] == -1:
                h[(r, c)] = m.NewBoolVar("")
                v[(r, c)] = m.NewBoolVar("")
                m.Add(h[(r, c)] + v[(r, c)] == 1)
    def ray(r, c, dr, dc):
        cells = []
        nr, nc = r + dr, c + dc
        while (0 <= nr < R and 0 <= nc < C
               and board[nr][nc] == -1):
            cells.append((nr, nc))
            nr += dr; nc += dc
        return cells
    def run_len(cells, is_h):
        if not cells: return 0
        vs = [h[c] if is_h else v[c] for c in cells]
        bs = []
        for K in range(1, len(cells) + 1):
            b = m.NewBoolVar("")
            m.Add(sum(vs[:K]) >= K).OnlyEnforceIf(b)
            m.Add(sum(vs[:K]) <= K - 1
                 ).OnlyEnforceIf(b.Not())
            bs.append(b)
        return sum(bs)
    for r in range(R):
        for c in range(C):
            if board[r][c] == -1: continue
            k = board[r][c]
            m.Add(run_len(ray(r, c,  0,  1), True)
                 + run_len(ray(r, c,  0, -1), True)
                 + run_len(ray(r, c,  1,  0), False)
                 + run_len(ray(r, c, -1,  0), False)
                 == k)
    s = cp_model.CpSolver()
    s.Solve(m)
    return [[('h' if s.Value(h[(r, c)]) else 'v')
             if board[r][c] == -1 else board[r][c]
             for c in range(C)]
            for r in range(R)]

The toy of Figure 20.1 solves uniquely in about $3$ milliseconds.

A hard instance

Figure 20.3 is a $7 \times 7$ Walls with fourteen black clues, constructed in the style of Alex Bellos’s puzzles in Puzzle Ninja. CP-SAT returns the unique solution in about $22$ milliseconds.

Sources. Walls appears in Alex Bellos’s Puzzle Ninja: Pit Your Wits Against the Japanese Puzzle Masters (Guardian Faber, $2017$), where it is credited to Japanese pencil-puzzle tradition. The clue-as-combined-run-length rule generalises the directional-sum rule seen in Nurikabe and Heyawake variants, but the combined-length encoding via ladder indicators is specific to Walls and the family of “count what you can reach” puzzles. Complexity is open: the puzzle is clearly in NP; no polynomial-time algorithm is known.