Akari

Akari is a puzzle of darkness and lamplight. The grid is a rectangle of cells, some white, some black. Black cells either carry a clue digit between $0$ and $4$ or are unmarked. The solver places lamps on a subset of white cells. A lamp illuminates every white cell in its row and column out to the next black cell. Three constraints govern the placement.

1. Every white cell is illuminated by at least one lamp.

2. No lamp illuminates another lamp: no two lamps share a row or a column without a black cell between them.

3. Every numbered black cell has exactly that many lamps among its four orthogonal neighbours.

The puzzle was published by Nikoli in $2001$ under the name Akari (Japanese for “light”), and is sometimes marketed in English as Light Up or Bijutsukan. It joins the shading-puzzle family alongside Nurikabe and Heyawake, but with a constraint of physical-light propagation rather than combinatorial connectivity.

The CP-SAT model is direct: a Boolean variable per white cell indicating “lamp here”, three families of constraints matching the three rules. The rules together are tight enough that the solver returns in milliseconds for puzzles up to $20 \times 20$.

Rules and a small instance

An Akari puzzle is an $R \times C$ grid. Each cell is one of three kinds: white (the candidate lamp positions), black with no clue (impassable), or black with a clue $k \in \{0, 1, 2, 3, 4\}$.

Figure 11.1 is puzzle $101$ from the janko.at Akari archive, a $10 \times 10$ instance with twenty-four black cells of which sixteen carry clues.

The programming model

For each white cell $(r, c)$ define a Boolean $L_{r, c} \in \{0, 1\}$, with $L_{r, c} = 1$ if a lamp is placed in that cell. Black cells carry no variable.

Illumination

For a white cell $(r, c)$, write $\mathcal S(r, c)$ for the set of white cells in its row and column reaching outward until the nearest black cell in each direction (and $(r, c)$ itself). The illumination constraint says some lamp must lie in this segment: $$\sum_{(r', c') \in \mathcal S(r, c)} L_{r', c'} \;\ge\; 1 \quad \text{for every white cell.}$$

No two lamps see each other

For each maximal run of white cells in a row (a sequence of consecutive white cells bounded by black cells or the grid edge), the run holds at most one lamp: $$\sum_{(r, c) \in \text{row run}} L_{r, c} \;\le\; 1, \qquad \sum_{(r, c) \in \text{column run}} L_{r, c} \;\le\; 1.$$

A row of length $w$ with no black cell contributes a single inequality $\sum_c L_{r, c} \le 1$; black cells split the row into independent runs each with its own inequality.

Numbered black cells

For each black cell carrying a clue $k$, the count of lamp neighbours in its four orthogonal cells equals $k$: $$\sum_{(r', c') \text{ orth. nbr}} L_{r', c'} \;=\; k.$$

A clue of $0$ forbids any of the four neighbours from being a lamp; a clue of $4$ forces all four to be lamps. Intermediate clues constrain the count of lamp positions among the at-most four candidates.

A solver in thirty-five lines

from ortools.sat.python import cp_model

def solve_akari(R, C, grid):
    """grid[r][c]: None (white), 'x' (black), or int."""
    m = cp_model.CpModel()
    is_w = lambda r, c: (0 <= r < R and 0 <= c < C
                         and grid[r][c] is None)
    is_b = lambda r, c: (0 <= r < R and 0 <= c < C
                         and grid[r][c] is not None)
    L = {(r, c): m.NewBoolVar("")
         for r in range(R) for c in range(C) if is_w(r, c)}

    def segment(r, c):
        seg = [(r, c)]
        for cc in range(c-1, -1, -1):
            if is_b(r, cc): break
            seg.append((r, cc))
        for cc in range(c+1, C):
            if is_b(r, cc): break
            seg.append((r, cc))
        for rr in range(r-1, -1, -1):
            if is_b(rr, c): break
            seg.append((rr, c))
        for rr in range(r+1, R):
            if is_b(rr, c): break
            seg.append((rr, c))
        return seg

    for (r, c) in L:
        m.Add(sum(L[s] for s in segment(r, c)) >= 1)

    def runs(line, is_blocker):
        out, buf = [], []
        for i, here in enumerate(line):
            if is_blocker(i):
                if buf: out.append(buf); buf = []
            else:
                buf.append(here)
        if buf: out.append(buf)
        return out

    for r in range(R):
        for run in runs(range(C), lambda c: is_b(r, c)):
            m.Add(sum(L[(r, c)] for c in run) <= 1)
    for c in range(C):
        for run in runs(range(R), lambda r: is_b(r, c)):
            m.Add(sum(L[(r, c)] for r in run) <= 1)

    NBR = [(-1,0),(1,0),(0,-1),(0,1)]
    for r in range(R):
        for c in range(C):
            if isinstance(grid[r][c], int):
                nb = [L[(r+dr, c+dc)] for dr, dc in NBR
                      if is_w(r+dr, c+dc)]
                m.Add(sum(nb) == grid[r][c])

    s = cp_model.CpSolver()
    s.Solve(m)
    return {pos for pos in L if s.Value(L[pos])}

The toy of Figure 11.1 solves uniquely in about $23$ milliseconds.

A hard instance

Figure 11.3 is puzzle $876$ from the janko.at Akari archive, a $16 \times 16$ instance by Sakuhina at the site’s top difficulty tier. The clue density is sparse, and the illumination constraint propagates only weakly through cells far from clues; the same solver code returns the unique solution (thirty-three lamps) in about $6$ milliseconds.

Sources. Akari was published by Nikoli in $2001$, and is also known as Light Up or Bijutsukan. The toy is puzzle $101$ from the janko.at Akari archive (Warai Kamosika), and the hard instance is puzzle $876$ (Sakuhina). McPhail and Boucher established the NP-completeness of Akari in $2007$ in a Concordia University technical report; the proof reduces from $3$-SAT via gadgets that encode each clause as a localised lighting puzzle.