Shikaku

Shikaku is the puzzle of partitioning a rectangle into rectangles. The grid is rectangular; certain cells carry positive integers. The solver must cut the grid into a set of non-overlapping axis-aligned rectangles such that every cell is contained in exactly one rectangle, every rectangle contains exactly one numbered cell, and that number equals the rectangle’s area in cells.

The puzzle was published by Nikoli in $1995$, going by the names Shikaku ni kire ("divide into rectangles") in Japanese and Sikaku in transliteration. It has the cleanest combinatorial structure of any puzzle in this book: the solution is a partition, the constraint is a set-cover, and the entire problem fits naturally into an exact-cover framework. Knuth’s Algorithm X (Dancing Links) was famously applied to Shikaku and its cousin Pentominoes; CP-SAT solves the same problem with the same speed and a tenth as much code.

Rules and a small instance

A Shikaku puzzle is an $R \times C$ grid. A subset of cells carries a positive integer clue $k$. The solver’s task is to partition the entire grid into a set of axis-aligned rectangles satisfying three conditions.

1. Every rectangle is axis-aligned and consists of one or more whole cells.

2. Every cell of the grid is contained in exactly one rectangle.

3. Every rectangle contains exactly one clue cell, and that clue’s value equals the rectangle’s area.

The clues’ values must therefore sum to the total cell count $R \cdot C$ (a useful sanity check on any candidate puzzle). The puzzle is well-formed if there is exactly one such partition.

Figure 12.1 is puzzle $1$ from the janko.at Sikaku archive, a $10 \times 10$ instance by Hirofumi Fujiwara with twenty-six clues.

The programming model

The natural encoding is enumeration. For each clue cell $(r, c)$ with area $k$, enumerate every axis-aligned rectangle of area $k$ that contains $(r, c)$ and contains no other clue; collect these as the candidate rectangles for that clue.

For an $R \times C$ grid, a clue of area $k$ admits at most $\sigma_0(k) \cdot k$ rectangles centred on $(r, c)$ (one per divisor pair $(h, w)$ with $h \cdot w = k$, then a translation window of dimensions $h \times w$). For typical $k \le 25$ this is a handful per clue.

Introduce a Boolean $x_{c, R}$ for each clue $c$ and each of its candidate rectangles $R$. The model:

1. For each clue $c$, $\sum_{R \in \text{cand}(c)} x_{c, R} = 1$ (exactly one rectangle is chosen).

2. For each grid cell $(r, c)$, $\sum_{(c, R) : (r, c) \in R} x_{c, R} = 1$ (each cell is covered by exactly one chosen rectangle).

The first family ensures each clue is matched; the second ensures the chosen rectangles partition the grid. CP-SAT solves the system as a set-partitioning ILP.

A solver in thirty lines

from ortools.sat.python import cp_model

def candidate_rects(R, C, clue, area, all_clues):
    """Area-k rects in R x C with 'clue' alone inside."""
    out = []
    cr, cc = clue
    for h in range(1, R+1):
        if area % h: continue
        w = area // h
        if w > C: continue
        for r1 in range(max(0, cr-h+1),
                        min(cr, R-h)+1):
            for c1 in range(max(0, cc-w+1),
                            min(cc, C-w)+1):
                r2, c2 = r1+h-1, c1+w-1
                if all((p, q) == clue or not
                       (r1 <= p <= r2 and c1 <= q <= c2)
                       for (p, q) in all_clues):
                    out.append((r1, c1, r2, c2))
    return out

def solve_shikaku(R, C, clues):
    """clues: {(r, c): area}."""
    cands = {c: candidate_rects(R, C, c, k, clues)
             for c, k in clues.items()}
    m = cp_model.CpModel()
    x = {(c, rect): m.NewBoolVar("")
         for c in cands for rect in cands[c]}
    for c, rs in cands.items():
        m.Add(sum(x[(c, r)] for r in rs) == 1)
    for r in range(R):
        for c in range(C):
            cov = [x[k] for k in x
                   if k[1][0] <= r <= k[1][2]
                   and k[1][1] <= c <= k[1][3]]
            m.Add(sum(cov) == 1)
    s = cp_model.CpSolver()
    s.Solve(m)
    return {c: rect for (c, rect) in x
            if s.Value(x[(c, rect)])}

The toy of Figure 12.1 solves uniquely in about $25$ milliseconds.

A hard instance

Figure 12.3 is puzzle $50$ from the janko.at Sikaku archive, a $14 \times 18$ instance by Hirofumi Fujiwara graded at the site’s top difficulty tier. With $68$ clues over $252$ cells, the candidate-rectangle space is dense enough that hand-solving takes considerable time; CP-SAT returns the unique partition in about $3$ milliseconds.

Sources. Shikaku was published by Nikoli in $1995$ in the magazine Puzzle Communication Nikoli; the Japanese name Shikaku ni kire translates as “divide into rectangles”. The exact-cover formulation used here goes back to Knuth’s Dancing Links ($2000$), which Knuth applied to the closely related pentomino-tiling problem. Toy and hard instances are puzzles $1$ and $50$ from the janko.at Sikaku archive (Hirofumi Fujiwara).