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 balance and no-triples rules are identical to the chosen variant in Chapter $5$. Distinct rows and columns are an extra condition in some binary-puzzle variants, but neither chapter imposes it. Here different symbols and examples illustrate the same linear-sum and sliding-window encoding.

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 CP-SAT solver

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()
    status = s.Solve(m)
    if status not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        raise RuntimeError(
            "no solution: " + s.StatusName(status))
    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. Binary-puzzle variants differ in whether they require distinct rows and columns; the version here omits that condition. No complexity conclusion for this variant follows merely by dropping constraints from a harder one. 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.