Chapter 17

Heyawake

Heyawake is the puzzle of dividing rooms. The grid is partitioned into rectangular rooms drawn with thick borders; some rooms carry a clue digit declaring the number of black cells the room must contain. The solver shades a subset of cells to satisfy four rules: the clue counts, no two black cells orthogonally adjacent, every white cell connected to every other white cell by a path of orthogonally adjacent white cells, and no straight horizontal or vertical line of consecutive white cells passes through more than two rooms.

The puzzle was published by Nikoli in $1992$ in the magazine Puzzle Communication Nikoli; heyawake translates literally as “rooms divided”, combining heya (“room”) and wake (“divided”). Among Nikoli shading puzzles it sits between Nurikabe and LITS in flavour: it shares Nurikabe’s connectivity register but operates on the complement, and like LITS it imposes a structural constraint linked to the room partition.

The white-line-spans-at-most-two-rooms rule is the puzzle’s signature constraint. It propagates information along entire row and column scans, often forcing black cells far from any clue; hand-solvers learn to spot triples of consecutive rooms that must therefore contain at least one shaded cell.

Rules and a small instance

A Heyawake puzzle is an $R \times C$ grid partitioned into rooms. A subset of rooms carry a positive integer clue. The solver shades a subset of cells subject to:

For every clued room, the count of shaded cells in the room equals the clue.
No two shaded cells share an edge.
All unshaded cells form one orthogonally connected region.
No row segment or column segment of consecutive unshaded cells passes through three or more rooms.

Figure 17.1 is puzzle $31$ from the janko.at Heyawake archive, a $6 \times 6$ instance by Abe Hajime, with seventeen rooms and no clue cells; the solution is forced by the geometry of the partition alone.

*A $6 \times 6$ Heyawake (Abe Hajime, via janko.at). No clue cells; the partition into seventeen rooms alone determines the unique shading.*

*The unique shading. Ten black cells, no two orthogonally adjacent, and every row and column run of whites stays within at most two rooms.*

The programming model

For each cell $(r, c)$ define a Boolean $b_{r, c}$ for shaded. The four rules become:

Room counts. For each clued room with cells $C_R$ and clue $k_R$ : $\sum_{(r, c) \in C_R} b_{r, c} = k_R$ .
Black non-adjacency. For each pair of orthogonally adjacent cells $(p, q)$ : $b_p + b_q \le 1$ .
White connectivity. Same BFS-distance pattern as Nurikabe (Chapter $13$ ), applied to the unshaded cells.
Three-room runs. For each row $r$ and starting column $s$ , find the smallest $e$ such that cells $r, c \in [s, e]$ touch at least three distinct rooms. Then $\sum_{c=s}^{e} b_{r, c} \ge 1$ . Same for columns.

The three-room-run constraint deserves a moment. For a fixed row $r$ , walk through the columns $0, 1, \ldots, C - 1$ . As you walk, maintain the set of distinct room IDs seen since position $s$ ; when this set first reaches size $3$ at some position $e$ , the window $[s, e]$ is a minimal run that touches three rooms. To keep that run from being entirely white, at least one of $b_{r, s}, \ldots, b_{r, e}$ must be $1$ . Repeating for every $s$ generates the full set of run-three-room constraints in $O(R \cdot C)$ time. Symmetric processing on columns completes the picture.

A solver in fifty lines

from ortools.sat.python import cp_model

def solve_heyawake(R, C, room_grid, rooms, clues):
    """rooms: room_id -> cell list.
       clues: cell -> black count of its room."""
    m = cp_model.CpModel()
    cells = [(r, c) for r in range(R) for c in range(C)]
    b = {k: m.NewBoolVar("") for k in cells}
    cpr = {room_grid[r][c]: v for (r, c), v in clues.items()}
    for rid, cs in rooms.items():
        if rid in cpr:
            m.Add(sum(b[c] for c in cs) == cpr[rid])
    for r, c in cells:
        for dr, dc in [(0, 1), (1, 0)]:
            nr, nc = r+dr, c+dc
            if 0 <= nr < R and 0 <= nc < C:
                m.Add(b[(r, c)] + b[(nr, nc)] <= 1)
    for r in range(R):
        for s in range(C):
            seen = set()
            for e in range(s, C):
                seen.add(room_grid[r][e])
                if len(seen) >= 3:
                    m.Add(sum(b[(r, k)]
                              for k in range(s, e+1)) >= 1)
                    break
    for c in range(C):
        for s in range(R):
            seen = set()
            for e in range(s, R):
                seen.add(room_grid[e][c])
                if len(seen) >= 3:
                    m.Add(sum(b[(k, c)]
                              for k in range(s, e+1)) >= 1)
                    break
    # White connectivity (Nurikabe pattern)
    d   = {k: m.NewIntVar(0, R*C-1, "") for k in cells}
    rho = {k: m.NewBoolVar("") for k in cells}
    w   = {k: m.NewBoolVar("") for k in cells}
    for k in cells:
        m.Add(b[k] == 0).OnlyEnforceIf(w[k])
        m.Add(b[k] == 1).OnlyEnforceIf(w[k].Not())
        m.Add(d[k] == 0).OnlyEnforceIf(rho[k])
        m.Add(w[k] == 1).OnlyEnforceIf(rho[k])
    m.Add(sum(rho.values()) == 1)
    def less_dist(p, q):
        bb = m.NewBoolVar("")
        m.Add(d[q] + 1 == d[p]).OnlyEnforceIf(bb)
        m.Add(d[q] + 1 != d[p]).OnlyEnforceIf(bb.Not())
        return bb
    for r, c in cells:
        cell = (r, c); sr = rho[cell]
        m.Add(d[cell] >= 1).OnlyEnforceIf(
            [w[cell], sr.Not()])
        preds = []
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r+dr, c+dc
            if not (0 <= nr < R and 0 <= nc < C):
                continue
            nb = (nr, nc)
            less = less_dist(cell, nb)
            p = m.NewBoolVar("")
            m.AddBoolAnd([w[nb], less]).OnlyEnforceIf(p)
            m.AddBoolOr([w[nb].Not(), less.Not()]
                        ).OnlyEnforceIf(p.Not())
            preds.append(p)
        if preds:
            m.AddBoolOr(preds).OnlyEnforceIf(
                [w[cell], sr.Not()])
    s = cp_model.CpSolver()
    s.Solve(m)
    return [[s.Value(b[(r, c)])
             for c in range(C)] for r in range(R)]

The toy of Figure 17.1 solves uniquely in about $20$ milliseconds.

A hard instance

Figure 17.3 is puzzle $297$ from the janko.at Heyawake archive, a $10 \times 18$ instance by Palmer Mebane (of mellowmelon), graded at the site’s level $7$ difficulty. Sparse clues sit on a partition of $36$ rooms; the three-room constraint does most of the lifting. CP-SAT returns the unique shading in about $340$ milliseconds.

*Heyawake $297$ from janko.at (Palmer Mebane), $10 \times 18$ with $36$ rooms and $16$ clues.*

*The unique shading, recovered in about $340$ ms. Black cells are non-adjacent, white cells are connected, and every row and column white-run stays inside at most two rooms.*

Sources. Heyawake was first published by Nikoli in $1992$ . The toy is puzzle $31$ from the janko.at Heyawake archive (Abe Hajime); the hard instance is puzzle $297$ (Palmer Mebane). Holzer and Ruepp ( $2007$ ) proved Heyawake NP-complete via a reduction from Hamiltonian Cycle in cubic planar graphs; the connectivity constraint and the three-room-run constraint together carry the encoding.