Marupeke

Marupeke is the puzzle of circles and crosses. The grid is a rectangle of white cells and optional black blockers. Each white cell must be filled with either a circle $\bigcirc$ or a cross $\times$, subject to a single sweeping constraint: no three cells of the same symbol may appear consecutively along any row, column, or either diagonal. Some cells are pre-filled as clues; black blockers interrupt lines, so a sequence of three is counted only when none of its members is black.

The puzzle’s name combines maru (circle) and peke (cross), two ubiquitous marks in Japanese pencil puzzling: $\bigcirc$ for “correct” and $\times$ for “wrong.” Marupeke is a close relative of Takuzu (Chapter $5$), sharing the no-triple rule; the difference is that Marupeke has no balance constraint on row or column totals, but enforces the triple rule along both diagonals as well. This single change makes the flavour strikingly different: Marupeke solutions have no large-scale structure of equal-counts rows, only the local forbidden-pattern scaffolding threading every line of the grid.

The black blockers are load-bearing. Three cells in a line that straddle a blocker are not a triple, because the line segment is broken. Setters use blockers to seed a puzzle: a lattice of blockers carves the grid into many short runs, and the triple constraint then propagates tightly through each run.

Rules and a small instance

A Marupeke puzzle is an $R \times C$ grid. Each cell is either a white cell (possibly pre-filled with $\bigcirc$ or $\times$ as a clue) or a black blocker. The solver must fill every remaining white cell with $\bigcirc$ or $\times$ such that:

1. Every pre-filled clue is preserved.

2. No three consecutive cells along any row, column, NW-SE diagonal, or NE-SW diagonal carry the same symbol, where “consecutive” means three white cells in a straight line with no black blocker among them.

Figure 19.1 is a $6 \times 6$ Marupeke, puzzle $1$ from Alex Bellos’s Puzzle Ninja ($2017$), with three blockers and eight clues.

The programming model

Assign each white cell a Boolean $v_{r,c}$ with $0$ meaning $\bigcirc$ and $1$ meaning $\times$. Black blockers are not assigned variables; whenever a constraint references a black blocker, the triple through that cell is skipped entirely (unlike the Demaine boundary convention used for Shakashaka, here skipping rather than zero-treating is the natural encoding).

The constraint families reduce to a single clean template.

Clue preservation

For each pre-filled cell $(r, c)$ with clue $k \in \{0, 1\}$, $$v_{r, c} \;=\; k.$$

No-triple-same

For each direction $\vec{d} \in \{(0, 1), (1, 0), (1, 1), (1, -1)\}$ and each cell $(r, c)$ such that $(r, c)$, $(r + d_r, c + d_c)$, and $(r + 2 d_r, c + 2 d_c)$ all lie inside the grid and are all white (no blockers), let $$S \;=\; v_{r, c} + v_{r + d_r, c + d_c} + v_{r + 2 d_r, c + 2 d_c}.$$ The triple is forbidden from being all $\bigcirc$ ($S = 0$) and from being all $\times$ ($S = 3$), so the constraint becomes $$1 \;\le\; S \;\le\; 2.$$ This is tight: if $S = 1$ or $S = 2$, the triple contains at least one of each symbol, which is exactly what the rule demands.

A solver in thirty lines

from ortools.sat.python import cp_model

def solve_marupeke(board):
    """board: R x C with entries in {-1, 0, 1, None}
         -1 = black blocker
          0 = clue O (bigcirc)
          1 = clue X (times)
          None = empty white 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] != -1:
                v[(r, c)] = m.NewBoolVar("")
    # clue preservation
    for r in range(R):
        for c in range(C):
            if board[r][c] in (0, 1):
                m.Add(v[(r, c)] == board[r][c])
    # no-triple-same along four directions
    DIRS = [(0, 1), (1, 0), (1, 1), (1, -1)]
    for r in range(R):
        for c in range(C):
            if board[r][c] == -1: continue
            for dr, dc in DIRS:
                pts = [(r+i*dr, c+i*dc) for i in range(3)]
                inside = all(0 <= pr < R and 0 <= pc < C
                             for (pr, pc) in pts)
                if not inside: continue
                if any(board[pr][pc] == -1
                       for (pr, pc) in pts): continue
                S = sum(v[p] for p in pts)
                m.Add(1 <= S)
                m.Add(S <= 2)
    s = cp_model.CpSolver()
    s.Solve(m)
    return [[(None if board[r][c] == -1
              else int(s.Value(v[(r, c)])))
             for c in range(C)]
            for r in range(R)]

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

A hard instance

Figure 19.3 is a $10 \times 10$ Marupeke, puzzle $5$ from Alex Bellos’s Puzzle Ninja ($2017$). It has eighteen blockers arranged in an irregular lattice and seventeen clues. CP-SAT returns the unique solution in about $2$ milliseconds: the blocker lattice breaks the grid into so many short runs that each triple constraint is local and the solver’s propagation engine dispatches them immediately.

Sources. Marupeke is a Japanese pencil puzzle brought to English-language audiences via Alex Bellos’s Puzzle Ninja: Pit Your Wits Against the Japanese Puzzle Masters (Guardian Faber, $2017$). The toy instance of Figure 19.1 is puzzle $1$ from that collection, and the larger hard instance of Figure 19.3 is puzzle $5$; both are genuine puzzles from that collection. Like Takuzu (Chapter $5$), Marupeke is solvable in polynomial time at any fixed grid size once the blockers are seen as edges in a constraint graph, but for the unconstrained problem (arbitrary grids, variable blocker placement) the complexity question remains open in the literature.