Shakashaka

Shakashaka is the puzzle of triangular halves. The grid is a rectangle of black and white cells; some black cells carry a clue digit in $\{0, 1, 2, 3, 4\}$. The solver fills a subset of white cells with an isosceles right triangle occupying half the cell (four orientations are available) so that two conditions hold: each clued black cell has exactly as many triangle-filled neighbours as its clue declares, and every connected region of remaining white area forms an axis-aligned rectangle or a $45^\circ$-rotated rectangle (a diamond). No L-shaped voids, no staircases, no rings are permitted.

The puzzle was published by Nikoli in the magazine Puzzle Communication Nikoli in $2008$, invented by Guten; the name is onomatopoeic, evoking the clattering sound of the triangles snapping into place. It is also known in translation as Proof of Quilt. Among Nikoli shading puzzles it is unusual: the state per cell is not binary but has five options (four triangle orientations plus empty), and the global constraint is geometric rather than connective.

The rectangle-or-diamond rule is the puzzle’s signature. It is a global shape constraint on an a priori unknown partition of the white cells, and it has real teeth: Demaine, Okamoto, Uehara and Uno proved Shakashaka NP-complete by reducing planar $3$-SAT to it, and showed that counting solutions is $\#\mathrm{P}$-complete. The integer-programming formulation in this chapter enforces the rectangle-or-diamond rule geometrically, by a local corner constraint at every grid vertex together with a single non-local rule against nested diamonds.

Rules and a small instance

A Shakashaka puzzle is a $R \times C$ grid of cells, each either black (optionally labelled with a clue in $\{0, 1, 2, 3, 4\}$) or white. A solution assigns to each white cell one of five states: empty, or filled by a triangle with its black right-angle at its NW, NE, SW or SE corner. A valid solution satisfies:

1. For every clued black cell with clue $k$, the number of triangle-filled cells among its four orthogonal neighbours whose triangle presents a full black edge to the clue is exactly $k$.

2. Every connected region of white non-triangle area is either an axis-aligned rectangle or a $45^\circ$-rotated rectangle (diamond). No other shape is permitted.

Figure 18.1 is a toy $7 \times 7$ Shakashaka in which eight black cells carry clues; the solution is unique.

The programming model

For every white cell $(r, c)$ define five Boolean variables, $$x_{r,c,\emptyset}, \ x_{r,c,\mathrm{NW}}, \ x_{r,c,\mathrm{NE}}, \ x_{r,c,\mathrm{SW}}, \ x_{r,c,\mathrm{SE}},$$ one per state. Black cells and cells outside the grid are not assigned variables; whenever a constraint references such a cell, every term is treated as the constant $0$. This is the Demaine boundary convention, and it is load-bearing: it lets every constraint be written uniformly, without special cases for the grid border.

Under this convention every triangle has its black right-angle at the corner indicated by its name and its hypotenuse between the two adjacent corners of the cell. The missing corner (the $45^\circ$ notch poking into the white half of the cell) is the diagonally opposite one.

Four constraint families

A. One state per cell. For every white cell $(r, c)$, $$x_{r, c, \emptyset} + x_{r, c, \mathrm{NW}} + x_{r, c, \mathrm{NE}} + x_{r, c, \mathrm{SW}} + x_{r, c, \mathrm{SE}} \;=\; 1.$$ This is the only equality in the model; every other constraint is an inequality.

B. Clues and wedge prohibition. A triangle in a neighbour of a black cell $B$ either presents a full black side to $B$ or leaves a $45^\circ$ wedge poking into $B$. The latter is forbidden because it would place a non-rectangular segment on the boundary of the white region adjoining $B$. For the upper neighbour $(r - 1, c)$ of $B$, the forbidden wedge orientations are NW and NE; the orientations contributing a black side to $B$ are SW and SE. Summing over all four axial neighbours and setting the sum equal to the clue $k$ yields the clue constraint; the wedge prohibition is a stronger inequality setting each wedge orientation to zero for every neighbour of every black cell.

C. The corner rule at every grid vertex. The boundary between white and non-white area is a union of straight cell edges and $45^\circ$ hypotenuses, and all of its turning happens at grid vertices. Walk around any white region: at each vertex the boundary either passes straight through ($180^\circ$ of white on one side) or makes a convex right-angle turn ($90^\circ$ of white). For the region to be a rectangle or a diamond, no other angle may occur. In particular a $270^\circ$ reflex angle (a concave notch), a lone $45^\circ$ wedge (the tip of an unclosed triangle), and a $135^\circ$ angle are all forbidden.

This is a purely local statement. Each interior grid vertex is surrounded by four cells, and the small disc around the vertex is partitioned by those cells’ states into white and non-white circular sectors. The rule is then: every maximal white sector around every grid vertex spans exactly $90^\circ$ or exactly $180^\circ$ (or the vertex is wholly interior, $360^\circ$, or wholly outside, $0^\circ$). Two regions may still touch at a vertex, each contributing its own $90^\circ$ sector; what is excluded is a single sector of $45^\circ$, $135^\circ$, $225^\circ$ or $270^\circ$.

Because the white sectors at a vertex are a function only of the (at most four) incident cells’ states, the rule is compiled to a Boolean clause per offending local pattern: for each grid vertex we enumerate the $5^{4}$ state assignments of its incident white cells, compute the sector angles geometrically, and for every assignment that produces a forbidden sector we forbid that exact combination, $$\bigvee_{(r,c)\in N(v)} \neg\, x_{r,c,\,s_{r,c}},$$ where $N(v)$ is the set of white cells touching vertex $v$ and $s_{r,c}$ is the state of cell $(r,c)$ in the offending assignment. This single family replaces the brittle edge-chaining and concave-corner bookkeeping of earlier formulations, and it is exact: checked against an independent region tracer on tens of thousands of random fillings, the clause set admits a filling if and only if every white region is a rectangle or a diamond, save for one residual case treated next.

D. Nested-diamond exclusion. The corner rule of $C$ guarantees that every white region has a locally correct boundary with only $90^\circ$ and $180^\circ$ angles, but it cannot by itself see a ring: an annular region whose outer and inner boundaries are both valid diamonds, with a separate diamond floating inside the hole. Every vertex of such a ring is locally fine, yet the region is neither a rectangle nor a diamond. The fix is a non-local inequality on pairs of cells sharing a diagonal: two $\mathrm{SE}$ triangles at $(r, c)$ and $(r + k, c + k)$ either lie on the same diamond boundary or have some $\mathrm{NW}$ triangle strictly between them breaking the nesting, $$x_{r, c, \mathrm{SE}} + x_{r + k, c + k, \mathrm{SE}} \;\le\; \sum_{0 < k' < k} x_{r + k', c + k', \mathrm{NW}} + 1 \qquad (k \ge 2).$$ Three rotations cover the other three diagonal cases.

A solver in sixty lines

import math, itertools
from ortools.sat.python import cp_model

S = ["E", "NW", "NE", "SW", "SE"]
# white half of a cell, in coords local to one
# of its corners; used to test a sample point.
BOX = {"NW": ((-1,0),(0,1)), "NE": ((0,1),(0,1)),
       "SW": ((-1,0),(-1,0)), "SE": ((0,1),(-1,0))}
def white_at(pos, state, p):
    (X0,X1),(Y0,Y1) = BOX[pos]
    if state is None: return False
    if state == "E":
        return X0-1e-9<=p[0]<=X1+1e-9 and \
               Y0-1e-9<=p[1]<=Y1+1e-9
    cor = {"NW":(X0,Y1),"NE":(X1,Y1),
           "SW":(X0,Y0),"SE":(X1,Y0)}
    adj = {"NW":["NE","SW"],"NE":["NW","SE"],
           "SW":["NW","SE"],"SE":["NE","SW"]}
    opp = {"NW":"SE","NE":"SW","SW":"NE","SE":"NW"}
    a,b = cor[adj[state][0]], cor[adj[state][1]]
    d = cor[opp[state]]
    def side(u,v,q):
        return (q[0]-v[0])*(u[1]-v[1]) \
             - (u[0]-v[0])*(q[1]-v[1])
    s1,s2,s3 = side(a,b,p),side(b,d,p),side(d,a,p)
    return not ((s1<-1e-9 or s2<-1e-9 or s3<-1e-9)
            and (s1>1e-9 or s2>1e-9 or s3>1e-9))

def vertex_ok(s4):  # s4: {pos -> state or None}
    N, eps, w = 720, 0.12, []
    for i in range(N):
        a = 2*math.pi*i/N
        p = (eps*math.cos(a), eps*math.sin(a))
        w.append(any(white_at(pos, s4[pos], p)
                     for pos in BOX))
    if all(w) or not any(w): return True
    k = w.index(False); seq = w[k:] + w[:k]
    runs, i = [], 0
    while i < len(seq):
        if seq[i]:
            j = i
            while j < len(seq) and seq[j]: j += 1
            runs.append(j-i); i = j
        else: i += 1
    tol = N//40
    return all(abs(r-N//4)<=tol or abs(r-N//2)<=tol
               for r in runs)

VPOS = {"NW":(-1,-1),"NE":(-1,0),
        "SW":(0,-1),"SE":(0,0)}

def solve_shakashaka(R, C, black, clues):
    """black: set of (r,c) black cells.
       clues: {(r,c) -> int} for clued cells."""
    m = cp_model.CpModel()
    x = {}
    for r in range(R):
        for c in range(C):
            if (r, c) in black: continue
            for s in S:
                x[(r, c, s)] = m.NewBoolVar("")
    def v(r, c, s):
        if not (0 <= r < R and 0 <= c < C): return 0
        if (r, c) in black: return 0
        return x[(r, c, s)]
    # (A) one state per white cell
    for r in range(R):
        for c in range(C):
            if (r, c) in black: continue
            m.Add(sum(x[(r, c, s)] for s in S) == 1)
    # (B) wedge prohibition and clue counts
    WEDGE = {(-1, 0): ("NW", "NE"),
             ( 1, 0): ("SW", "SE"),
             ( 0,-1): ("NW", "SW"),
             ( 0, 1): ("NE", "SE")}
    FACE  = {(-1, 0): ("SW", "SE"),
             ( 1, 0): ("NW", "NE"),
             ( 0,-1): ("NE", "SE"),
             ( 0, 1): ("NW", "SW")}
    for (r, c) in black:
        for (dr, dc), fb in WEDGE.items():
            nr, nc = r+dr, c+dc
            for s in fb:
                if v(nr, nc, s) != 0:
                    m.Add(x[(nr, nc, s)] == 0)
    for (r, c), k in clues.items():
        ts = [v(r+dr, c+dc, s)
              for (dr, dc), fa in FACE.items()
              for s in fa]
        m.Add(sum(ts) == k)
    # (C) corner rule: forbid every local pattern
    #     that makes a bad white sector at a vertex
    for vr in range(R+1):
        for vc in range(C+1):
            rel = []
            for pos, (dr, dc) in VPOS.items():
                rr, cc = vr+dr, vc+dc
                if 0 <= rr < R and 0 <= cc < C \
                   and (rr, cc) not in black:
                    rel.append((pos, rr, cc))
            if not rel: continue
            for combo in itertools.product(
                    S, repeat=len(rel)):
                s4 = {p: None for p in VPOS}
                for (pos, rr, cc), st in zip(rel, combo):
                    s4[pos] = st
                if not vertex_ok(s4):
                    m.AddBoolOr([
                        x[(rr, cc, st)].Not()
                        for (pos, rr, cc), st
                        in zip(rel, combo)])
    # (D) nested-diamond exclusion (4 diagonals)
    NEST = [("SE","NW", 1, 1), ("NW","SE", 1, 1),
            ("SW","NE", 1,-1), ("NE","SW", 1,-1)]
    for gA, gB, dr, dc in NEST:
        for r in range(R):
            for c in range(C):
                if v(r, c, gA) == 0: continue
                k = 2
                while (0 <= r+k*dr < R
                       and 0 <= c+k*dc < C):
                    far = v(r+k*dr, c+k*dc, gA)
                    if far == 0:
                        k += 1; continue
                    sep = [v(r+kp*dr, c+kp*dc, gB)
                           for kp in range(1, k)]
                    m.Add(x[(r, c, gA)] + far
                          <= sum(t for t in sep
                                 if t != 0) + 1)
                    k += 1
    s = cp_model.CpSolver()
    s.Solve(m)
    return {(r, c): next(st for st in S
                         if s.Value(x[(r, c, st)]))
            for (r, c, _) in x}

The toy puzzle of Figure 18.1 solves in about $10$ milliseconds.

A hard instance

Figure 18.3 is a $20 \times 20$ Shakashaka with $76$ black cells and $25$ clues. Building the corner clauses and solving takes under two seconds; the search itself, once the model is constructed, returns the unique $192$-triangle solution in under a tenth of a second.

Sources. Shakashaka was first published by Nikoli in $2008$. The toy instance of Figure 18.1 is adapted from Puzzle Communication Nikoli; the hard instance of Figure 18.3 was generated for this book and checked for a unique solution by the solver above, cross-validated against an independent region tracer. Demaine, Okamoto, Uehara and Uno (Computational Geometry, $2013$) proved Shakashaka NP-complete via a reduction from planar $3$-SAT; the rectangle-or-diamond rule is enforced here by the local corner constraint developed above rather than by their original formulation.