Searchlights

Searchlights is the puzzle of seeing through a row. The grid is a rectangle of white cells and black cells; each black cell carries a non-negative integer clue. The solver places “lights” in a subset of white cells. Each clue counts the number of lights visible from its black cell looking in the four orthogonal directions (up, down, left, right, but not diagonally), where a light is visible through other lights but not through black cells: a black cell terminates the ray.

Searchlights belongs to the family of line-of-sight puzzles that also includes Akari (Chapter $11$) and the lesser-known Karesansui. All three work with the same geometric primitive, an unobstructed row or column segment bounded by black cells, and give the solver a different kind of task on each segment. Akari asks about illumination (every white cell seen from at least one light); Searchlights asks about counting (each clue equals the number of lights in its four-way view cone). The line-of-sight model makes Searchlights naturally linear: every clue is a single linear sum of Boolean light variables over a fixed set of cells.

Among the puzzles in this volume, Searchlights has the simplest constraint structure, but the deductive work to solve by hand is non-trivial. Tight clues like $0$ and the maximum “all four rays full” force lights into predictable positions, but intermediate clues leave parity and placement ambiguities that must be triangulated against several other rays. The solver handles this combinatorial triangulation in a millisecond; by hand it is an hour.

Rules and a small instance

A Searchlights puzzle is an $R \times C$ grid of cells. Each cell is either white or black with a non-negative integer clue. A solution assigns to every white cell the status light or empty such that:

1. Every black clue $k$ equals the number of lights in the accessible cells of the clue: all white cells lying in the same row or column as the clue, between the clue and the first obstruction (another black cell or the grid boundary) in each of the four orthogonal directions.

2. Every white cell either holds at most one light or is empty.

Figure 23.1 is a $4 \times 4$ Searchlights with six black clues. The lights are marked by filled circles in the solution.

The programming model

For every white cell $(r, c)$ introduce a Boolean $v_{r, c}$, with $v_{r, c} = 1$ meaning “light at $(r, c)$.”

For every black cell at $(r, c)$ with clue $k$, compute its accessible set $A(r, c)$: the union over the four axial directions of the white cells from the neighbour of $(r, c)$ in that direction up to (but not including) the first black cell or the grid edge, whichever comes first.

The clue constraint is a single linear equation: $$\sum_{(r', c') \in A(r, c)} v_{r', c'} \;=\; k.$$

That is the entire model. No at-most-one-per-cell constraint is needed because each $v$ is already Boolean (0 or 1); the “at most one light per cell” phrasing in the rules is a natural consequence of the domain $\{0, 1\}$.

A solver in twenty lines

from ortools.sat.python import cp_model

def solve_searchlights(board):
    """board[r][c] = 0 for empty white cell,
       or a positive integer clue for a black cell."""
    R, C = len(board), len(board[0])
    m = cp_model.CpModel()
    v = {}
    for r in range(R):
        for c in range(C):
            if board[r][c] == 0:
                v[(r, c)] = m.NewBoolVar("")
    def accessible(r, c):
        out = []
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nr, nc = r + dr, c + dc
            while (0 <= nr < R and 0 <= nc < C
                   and board[nr][nc] == 0):
                out.append((nr, nc))
                nr += dr; nc += dc
        return out
    for r in range(R):
        for c in range(C):
            if board[r][c] != 0:
                A = accessible(r, c)
                m.Add(sum(v[p] for p in A)
                      == board[r][c])
    s = cp_model.CpSolver()
    s.Solve(m)
    return [[(s.Value(v[(r, c)]) if board[r][c] == 0
              else -board[r][c])
             for c in range(C)]
            for r in range(R)]

The toy of Figure 23.1 solves uniquely in about $14$ milliseconds.

A hard instance

Figure 23.3 is a $9 \times 9$ Searchlights from Alex Bellos’s Puzzle Ninja, puzzle $4$. Twenty-one black clues dominate the grid with clue values ranging from $1$ to $4$; the remaining $60$ white cells accommodate the unique light placement. CP-SAT returns the solution in about $3$ milliseconds.

Sources. Searchlights appears in Alex Bellos’s Puzzle Ninja: Pit Your Wits Against the Japanese Puzzle Masters (Guardian Faber, $2017$); the toy of Figure 23.1 is a small instance of the same family. The line-of-sight primitive is shared with Akari (Chapter $11$, Bijutsukan) and with Leah Goldberg’s academic puzzle Art Gallery that underlies the NP-completeness proofs for visibility-based pencil puzzles. Searchlights, unlike Akari, has no uniqueness-of-light constraint inside a line: multiple lights may share a ray, and only their count against a clue matters.