3-in-a-Row

The 3-in-a-Row puzzle is the sibling of Takuzu. The grid is a square with an even side length $N$. The solver fills every cell with one of two symbols, conventionally a filled square and an open circle, subject to three rules: each row and each column contains exactly $N / 2$ of each symbol, and no three consecutive cells in a row or column share the same symbol. Some cells are pre-filled as clues.

The rule set is almost identical to Takuzu (Chapter $5$), and for most puzzles the two are interchangeable. The one distinction is that Takuzu adds a fourth rule, that all rows are mutually distinct and all columns are mutually distinct; 3-in-a-Row omits it. In practice the distinction rarely matters: a typical hand-designed instance is uniquely solvable under the three rules alone, because the balance and no-three constraints together are very sharp once a handful of clues are placed.

3-in-a-Row circulates widely in the English-language puzzle press as a beginner-friendly pencil puzzle, but its deeper lineage traces through Japanese Tentai Show and allied variants that appeared in Puzzle Communication Nikoli during the $2000$s. In the constraint-programming setting, the puzzle is one of the purest instances of a linear-sum-plus-window-constraint encoding: every rule reduces to a small integer-programming statement, and the CP-SAT solver handles an entire grid in a few milliseconds.

Rules and a small instance

A 3-in-a-Row puzzle is an $N \times N$ grid of cells, with $N$ even. Some cells carry pre-filled symbols drawn from $\{0, 1\}$ (conventionally $1$ rendered as a filled square, $0$ as an open circle). A solution assigns a symbol to every cell such that:

1. Every pre-filled clue is preserved.

2. Each row contains exactly $N / 2$ zeros and $N / 2$ ones.

3. Each column contains exactly $N / 2$ zeros and $N / 2$ ones.

4. No three consecutive cells in any row have the same symbol.

5. No three consecutive cells in any column have the same symbol.

Figure 25.1 is a $6 \times 6$ 3-in-a-Row with eight clues; the solution is unique.

The programming model

For every cell $(r, c)$ introduce a Boolean $x_{r, c} \in \{0, 1\}$.

Row and column balance

For each row $r \in \{0, 1, \ldots, N - 1\}$, $$\sum_{c = 0}^{N - 1} x_{r, c} \;=\; \frac{N}{2}.$$ Symmetrically for each column $c$, $$\sum_{r = 0}^{N - 1} x_{r, c} \;=\; \frac{N}{2}.$$

No three consecutive same

For each row $r$ and each starting column $c \in \{0, 1, \ldots, N - 3\}$, the three cells $(r, c), (r, c + 1), (r, c + 2)$ cannot all be $0$ and cannot all be $1$. Since each variable is Boolean, the sum is in $\{0, 1, 2, 3\}$, and the rule is exactly $$1 \;\le\; x_{r, c} + x_{r, c + 1} + x_{r, c + 2} \;\le\; 2.$$ Symmetrically for every column and starting row.

Clue preservation

For every pre-filled cell $(r, c)$ with clue $k$, $$x_{r, c} \;=\; k.$$

A solver in twenty-five lines

from ortools.sat.python import cp_model

def solve_threeinarow(N, clues):
    """N x N grid (N even); clues = list of (r, c, v)."""
    m = cp_model.CpModel()
    x = [[m.NewBoolVar("") for _ in range(N)]
         for _ in range(N)]
    for r, c, v in clues:
        m.Add(x[r][c] == v)
    for r in range(N):
        m.Add(sum(x[r]) == N // 2)
    for c in range(N):
        m.Add(sum(x[r][c] for r in range(N))
              == N // 2)
    for r in range(N):
        for c in range(N - 2):
            s = x[r][c] + x[r][c+1] + x[r][c+2]
            m.Add(1 <= s); m.Add(s <= 2)
    for c in range(N):
        for r in range(N - 2):
            s = x[r][c] + x[r+1][c] + x[r+2][c]
            m.Add(1 <= s); m.Add(s <= 2)
    s = cp_model.CpSolver()
    s.Solve(m)
    return [[s.Value(x[r][c]) for c in range(N)]
            for r in range(N)]

The toy of Figure 25.1 solves uniquely in about $15$ milliseconds.

A hard instance

Figure 25.3 is a $10 \times 10$ 3-in-a-Row with thirty-one clues spread across the grid. CP-SAT returns the unique solution in about $5$ milliseconds.

Sources. 3-in-a-Row appears under various names in the English-language puzzle press: Binairo, Tango, Takuzu, and Binary Puzzle are all cognate. The closest Japanese-published form is Takuzu (Chapter $5$), published in Puzzle Communication Nikoli, which adds the row-and-column uniqueness rule; the version here is the lightly-rule-set variant that omits uniqueness. Both versions are NP-complete to decide (Pedro, $2013$, treated the Takuzu version directly; the same reduction works for 3-in-a-Row by dropping the uniqueness constraint). For this chapter, the toy of Figure 25.1 is the small benchmark distributed with the Solving Logic Puzzles Python tooling; the hard instance of Figure 25.3 was generated to test CP-SAT’s propagation on a scale-up of the same rule system.