Takuzu

Takuzu is the puzzle of balanced coin flips. The grid is a square of even side $n$, each cell shaded or unshaded (heads or tails, black or white, $0$ or $1$). A small number of cells carry given values; the solver fills the rest subject to two constraints. Every row and every column contains equal counts of the two states, and no row or column contains three consecutive cells of the same state.

The puzzle is known under several names: Binairo in European sources, Tohu-Wa-Vohu in the janko.at archive (after the Hebrew for "formless and void"), Takuzu in Japan, Binary Puzzle in English-language newspapers. Nikoli publishes it under one of several Japanese names in the sum/shading family. The earliest version with the three-in-a-row prohibition seems to be due to Adolfo Zanellati circa $2009$; earlier binary Latin-square puzzles without the consecutive constraint existed in recreational literature for decades.

Mathematically, Takuzu is a pure $0$/$1$ integer program, like Kakurasu of the previous chapter, but with a richer constraint shape. The equal-counts constraint is one linear equality per row and per column. The no-three-consecutive constraint bans just two local patterns, $000$ and $111$; it translates cleanly into pairs of inequalities on sliding windows of three variables.

Rules and a small instance

A Takuzu puzzle is an $n \times n$ grid with $n$ even. Each cell $(r, c)$ holds a value $x_{r,c} \in \{0, 1\}$. Two constraints govern the grid.

1. Every row and every column contains exactly $n/2$ zeros and $n/2$ ones.

2. No three consecutive cells in any row or column share the same value.

A well-posed Takuzu puzzle has a subset of cells pre-filled with $0$ or $1$; these are the givens. The solver’s task is to extend the partial assignment to the unique complete grid that respects both rules.

Figure 5.1 shows a $6 \times 6$ Takuzu with eight given cells, four white and four black. The unique completion appears in Figure 5.2; givens in the solution are outlined in copper so as to distinguish them from cells the solver filled.

The programming model

Let $x_{r,c} \in \{0, 1\}$ for $0 \le r, c < n$. The equal-counts constraint is $$\begin{align*} \sum_{c=0}^{n-1} x_{r,c} &= \tfrac{n}{2} & \text{for each row } r, \\ \sum_{r=0}^{n-1} x_{r,c} &= \tfrac{n}{2} & \text{for each column } c. \end{align*}$$

The no-three-consecutive constraint is a pair of inequalities on every sliding window of three consecutive cells. For a window to avoid $(0, 0, 0)$ the sum must be at least $1$; to avoid $(1, 1, 1)$ the sum must be at most $2$: $$\begin{align*} 1 \;\le\; x_{r,c} + x_{r,c+1} + x_{r,c+2} \;\le\; 2, \\ 1 \;\le\; x_{r,c} + x_{r+1,c} + x_{r+2,c} \;\le\; 2. \end{align*}$$

On an $n \times n$ grid this gives $2 n (n-2)$ sliding-window inequalities plus $2n$ equal-counts equalities, all linear, all on binary variables. Unlike Kakurasu the constraints are local: each involves only two or three variables. The number of feasible assignments of a raw Takuzu grid (no givens) grows rapidly but slower than $2^{n^2}$; a typical published puzzle constrains it down to a single solution with only a modest number of givens.

A solver in a dozen lines

from ortools.sat.python import cp_model

def solve_takuzu(n, givens):
    """givens: (r, c, v) triples; v in {0, 1}."""
    m = cp_model.CpModel()
    x = [[m.NewBoolVar(f"x{r}{c}")
          for c in range(n)] for r in range(n)]
    for r, c, v in givens:
        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(s >= 1); 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(s >= 1); m.Add(s <= 2)
    s = cp_model.CpSolver()
    ok = s.Solve(m)
    if ok not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        raise RuntimeError("no solution")
    return [[s.Value(x[r][c])
             for c in range(n)] for r in range(n)]

The toy instance solves in about $14$ milliseconds.

A hard instance

Figure 5.3 is puzzle $140$ from the janko.at Tohu-Wa-Vohu archive, Otto Janko’s own, rated at the top tier of the site’s difficulty scale. The grid is $14 \times 14$; fifty-four cells are given, leaving one hundred and forty-two to deduce. The same solver code returns the unique completion in about $3$ milliseconds, faster than the toy despite the larger grid: with a denser set of givens the local inequalities propagate earlier and the solver’s search tree is narrower.

The variant with distinct rows and columns

A stricter version of the puzzle, often marketed as Binairo, adds a third rule: no two rows are identical and no two columns are identical. This turns the puzzle into a kind of binary Latin-square relative: the rows and columns are $n$-bit strings that are $n/2$-balanced and avoid triple repeats, and the grid must be a set of such strings.

The distinctness constraint is cheap to add. For each pair of rows $(r_1, r_2)$ with $r_1 < r_2$, require at least one column at which they differ: $$\sum_{c=0}^{n-1} \mathbf{1}\bigl[x_{r_1, c} \ne x_{r_2, c}\bigr] \;\ge\; 1,$$ reified cell-by-cell into booleans. The same for each pair of columns. In the CP-SAT model this adds $\binom{n}{2}$ row-pair constraints and $\binom{n}{2}$ column-pair constraints, each with $n$ auxiliary booleans: $O(n^3)$ booleans in total. For $n = 14$ that is manageable; for $n$ larger than about $20$ the model starts to hurt and a dedicated all-different constraint over row-integers is preferable.

Curiously, the janko.at puzzle $140$ does not satisfy the distinctness rule: one column appears twice in the solution. Whether the author intended the strict Binairo rules or the three-in-a-row rules alone is a curatorial question. The solver code above uses the latter; switching to the Binairo rules would have rendered the published puzzle infeasible.

Sources. The three-in-a-row prohibition and the equal-counts rule are due to Adolfo Zanellati (Italy, c. $2009$), who marketed the puzzle as Binairo. The Hebrew-language naming Tohu-Wa-Vohu comes from the janko.at archive; puzzle $140$ in that archive is by Otto Janko. Nikoli publishes the three-in-a-row variant under various Japanese names. The CP-SAT formulation here follows the natural $0$/$1$ ILP approach; for a decision-theoretic study of the puzzle’s complexity, see Utiyama and Uehara, Computational complexity of the Binairo puzzle, Proceedings of IPSJ Workshop on Game Informatics $27$ ($2012$).