Hitori

Hitori is the puzzle of hiding duplicates. The grid is a square of digits; the solver must shade some cells black and leave the rest unshaded, subject to three rules. Every row and every column must contain each digit at most once among its unshaded cells. No two shaded cells may touch along an edge. And every unshaded cell must reach every other unshaded cell through a chain of orthogonally adjacent unshaded cells, i.e. the unshaded region must be connected.

The puzzle was published by Nikoli in $1990$; the Japanese name, Hitori ni shite kure, literally “leave me alone,” is a pun on the solving procedure of eliminating duplicates by shading. The puzzle has the unusual property, among Nikoli shadings, of operating on a complement region: the unshaded cells carry the content and must be connected, while the shaded cells are merely the deletion pattern.

Each of the three rules contributes a distinct CP-SAT constraint register. The row and column uniqueness is a “pairwise conflict” family: for each pair of cells sharing a row or column and carrying the same digit, at least one must be shaded. The adjacency rule is a pairwise $\le 1$ constraint on neighbouring cells. The connectivity rule is, as in Nurikabe, a distance-from-root flow but applied to the complement of the shading.

Rules and a small instance

A Hitori puzzle is an $R \times C$ grid (usually with $R = C$, and typically $R \in \{5, \ldots, 17\}$). Each cell carries a positive integer. The solver chooses a subset of cells to shade subject to three rules.

1. In every row, each digit appears at most once among the unshaded cells; likewise in every column.

2. No two shaded cells are orthogonally adjacent.

3. The unshaded cells form a single orthogonally connected region.

Figure 15.1 is puzzle $4$ from the janko.at Hitori archive, an $8 \times 8$ instance by Otto Janko.

The programming model

For each cell $(r, c)$ define a Boolean $s_{r, c}$, with $s_{r, c} = 1$ meaning shaded.

Pairwise uniqueness on unshaded cells

For each row $r$ and each pair of distinct columns $c_1 < c_2$ with grid digits equal, at least one of the two cells must be shaded: $$s_{r, c_1} + s_{r, c_2} \;\ge\; 1 \quad \text{whenever } g_{r, c_1} = g_{r, c_2}.$$ The analogous constraint holds for every column and every pair of rows with equal column digits.

No adjacent black cells

For each pair of orthogonally adjacent cells $(p, q)$, $$s_p + s_q \;\le\; 1.$$

Connectivity of the unshaded region

Attach a distance variable $d_{r, c} \in \{0, 1, \ldots, R C - 1\}$ to every cell, and a Boolean $\rho_{r, c}$ marking a designated unshaded root. The root’s $d$ is $0$ and $\rho$ implies the cell is unshaded. Every other unshaded cell must have $d \ge 1$ and an orthogonally adjacent unshaded neighbour with $d - 1$.

Exactly one $\rho$ is set: $\sum_{r, c} \rho_{r, c} = 1$.

A solver in fifty lines

from ortools.sat.python import cp_model

def solve_hitori(R, C, grid):
    """grid[r][c] = digit. Returns shaded {0, 1} grid."""
    m = cp_model.CpModel()
    s = {(r, c): m.NewBoolVar("")
         for r in range(R) for c in range(C)}
    for r in range(R):
        for c1 in range(C):
            for c2 in range(c1+1, C):
                if grid[r][c1] == grid[r][c2]:
                    m.Add(s[(r, c1)] + s[(r, c2)] >= 1)
    for c in range(C):
        for r1 in range(R):
            for r2 in range(r1+1, R):
                if grid[r1][c] == grid[r2][c]:
                    m.Add(s[(r1, c)] + s[(r2, c)] >= 1)
    for r in range(R):
        for c in range(C):
            for dr, dc in [(0,1),(1,0)]:
                nr, nc = r+dr, c+dc
                if 0 <= nr < R and 0 <= nc < C:
                    m.Add(s[(r,c)] + s[(nr,nc)] <= 1)

    d = {(r, c): m.NewIntVar(0, R*C-1, "")
         for r in range(R) for c in range(C)}
    rho = {(r, c): m.NewBoolVar("")
           for r in range(R) for c in range(C)}
    un = {k: m.NewBoolVar("") for k in s}
    for k in s:
        m.Add(s[k] == 0).OnlyEnforceIf(un[k])
        m.Add(s[k] == 1).OnlyEnforceIf(un[k].Not())
        m.Add(d[k] == 0).OnlyEnforceIf(rho[k])
        m.Add(un[k] == 1).OnlyEnforceIf(rho[k])
    m.Add(sum(rho.values()) == 1)

    def less(p, q):
        b = m.NewBoolVar("")
        m.Add(d[q] + 1 == d[p]).OnlyEnforceIf(b)
        m.Add(d[q] + 1 != d[p]).OnlyEnforceIf(b.Not())
        return b

    for r in range(R):
        for c in range(C):
            cell = (r, c); sr = rho[cell]
            m.Add(d[cell] >= 1).OnlyEnforceIf([un[cell],
                                              sr.Not()])
            preds = []
            for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
                nr, nc = r+dr, c+dc
                if not (0 <= nr < R and 0 <= nc < C):
                    continue
                nb = (nr, nc)
                lb = less(cell, nb)
                p = m.NewBoolVar("")
                m.AddBoolAnd([un[nb], lb]).OnlyEnforceIf(p)
                m.AddBoolOr([un[nb].Not(), lb.Not()]
                            ).OnlyEnforceIf(p.Not())
                preds.append(p)
            if preds:
                m.AddBoolOr(preds).OnlyEnforceIf(
                    [un[cell], sr.Not()])

    sol = cp_model.CpSolver()
    sol.Solve(m)
    return [[sol.Value(s[(r, c)])
             for c in range(C)] for r in range(R)]

The toy of Figure 15.1 solves uniquely in about $70$ milliseconds.

A hard instance

Figure 15.3 is puzzle $78$ from the janko.at Hitori archive, a $17 \times 17$ instance by Koyoppz, the only puzzle in the archive at the top-tier difficulty “schwer”. The grid carries $289$ cells filled with digits $1$ to $15$, many of them with multiple repetitions; the solver’s task is to find the unique shading pattern that satisfies all three rules. CP-SAT returns the result in about $1.4$ seconds.

Sources. Hitori was first published by Nikoli in $1990$. The toy is puzzle $4$ from the janko.at Hitori archive (Otto Janko); the hard instance is puzzle $78$ (Koyoppz). Hearn and Demaine ($2005$) proved the general Hitori decision problem NP-complete via a reduction from planar $3$-SAT in Games, Puzzles and Computation (AK Peters).