Wijuko and ABC Logic

The puzzle page of a daily newspaper is a quiet supply of small integer programs. Alongside the sudoku and the kakuro sit lesser-known grids, each a set of cells to fill under simple rules, and each, once the rules are written as constraints, a model a solver clears in an instant. Two that ran in the British paper the i make the point. The first places nine digits under sum clues; the second places three letters under clues that see only the ends of a line.

Wijuko

A Wijuko is a three-by-three block of cells into which the digits $1$ through $9$ go, each once. Between some pairs of neighbouring cells a number is printed, a subtotal, and the two cells flanking it must add to it. The digits are forced not by a Latin condition, as in sudoku, but by these few sums together with the demand that all nine digits appear.

Writing a cell by its row and column from the top left, the worked instance carries seven subtotals: the pairs $(1,2)\,(1,3) = 7$ and $(2,2)\,(2,3) = 14$ across the grid, and $(1,1)\,(2,1) = 12$, $(1,2)\,(2,2) = 8$, $(1,3)\,(2,3) = 13$, $(2,1)\,(3,1) = 7$, $(2,3)\,(3,3) = 15$ down it. The model is as short as the rules. A digit variable holds each cell, one global all-different forces the nine to be a permutation of $1$ through $9$, and each subtotal is one linear equation on its two cells.

from ortools.sat.python import cp_model

def solve_wijuko(subtotals):
    m = cp_model.CpModel()
    v = {(r, c): m.NewIntVar(1, 9, "")
         for r in range(3) for c in range(3)}
    m.AddAllDifferent(list(v.values()))  # all digits distinct
    for a, b, s in subtotals:  # each clue is a pair sum
        m.Add(v[a] + v[b] == s)
    sol = cp_model.CpSolver()
    sol.Solve(m)
    val = sol.Value
    return [[val(v[r, c]) for c in range(3)] for r in range(3)]

The seven sums pin the block completely. The solver returns $$\begin{array}{ccc} 9 & 2 & 5 \\ 3 & 6 & 8 \\ 4 & 1 & 7 \end{array}$$ and, asked for every solution rather than the first, returns this one alone: the instance is well posed. A Wijuko is close kin to the Suko of an earlier chapter, another three-by-three holding the digits $1$ through $9$ under sum clues; there the clues were the totals of overlapping two-by-two blocks, here they are the sums of single adjacent pairs, and the same all-different and a handful of linear equations dispatch both.

ABC Logic

ABC Logic is played on a five-by-five grid. The letters A, B, and C are each written once in every row and once in every column, which leaves two cells of each row and column empty. The clues sit outside the grid: a letter against the left of a row is the first letter met scanning that row from the left, a letter against the right is the last, and likewise the top and bottom of each column give the first and last letter seen down it. From a scatter of these edge clues the whole grid is to be recovered.

The placement is the easy part: a binary $x_{ijk}$ for letter $k$ in cell $(i, j)$, at most one letter to a cell, and exactly one of each letter along every row and every column. The clues are the interesting part. The article that posed the puzzle reached them through a chain of sufficient conditions; there is a more direct reading. Since a letter sits in exactly one cell of its row, its position in that row is well defined, the column index $$\mathrm{col}_i(k) = \sum_j j\, x_{ijk},$$ and a clue that names the first letter of a row is simply the statement that that letter’s position is smaller than the other two. A first-letter clue $L$ on row $i$ reads $\mathrm{col}_i(L) < \mathrm{col}_i(M)$ for the other two letters $M$; a last-letter clue reverses the inequality; the column clues say the same with row positions $\mathrm{row}_j(k) = \sum_i i\, x_{ijk}$.

def solve_abc(clues, n=5):
    m = cp_model.CpModel()
    x = {(i, j, k): m.NewBoolVar("")
         for i in range(n) for j in range(n) for k in "ABC"}
    for i in range(n):
        for j in range(n):
            m.Add(sum(x[i, j, k] for k in "ABC") <= 1)
    for k in "ABC":  # each letter once per row and column
        for i in range(n):
            m.Add(sum(x[i, j, k] for j in range(n)) == 1)
        for j in range(n):
            m.Add(sum(x[i, j, k] for i in range(n)) == 1)
    cpos = {(i, k): sum(j * x[i, j, k] for j in range(n))
            for i in range(n) for k in "ABC"}
    rpos = {(j, k): sum(i * x[i, j, k] for i in range(n))
            for j in range(n) for k in "ABC"}
    for side, idx, L in clues:
        pos = cpos if side in "LR" else rpos
        for M in "ABC":
            if M == L:
                continue
            if side in "LT":
                m.Add(pos[idx, L] < pos[idx, M])  # L first
            else:
                m.Add(pos[idx, L] > pos[idx, M])  # L last
    sol = cp_model.CpSolver()
    sol.Solve(m)
    g = [["."] * n for _ in range(n)]
    for (i, j, k), var in x.items():
        if sol.Value(var):
            g[i][j] = k
    return g

Eight edge clues are enough to fix a grid. Take the left of row $3$ to be B; the rights of rows $1$, $2$, $3$ to be C, A, A; the tops of columns $1$, $3$, $4$ to be B, C, C; and the bottom of column $4$ to be B. The solver fills the twenty-five cells one way only, with a dot for an empty cell: $$\begin{array}{ccccc} B & A & C & \cdot & \cdot \\ C & B & A & \cdot & \cdot \\ \cdot & \cdot & B & C & A \\ \cdot & C & \cdot & A & B \\ A & \cdot & \cdot & B & C \end{array}$$ A sweep for further solutions finds none. The position reading earns its keep here: an inequality between two sums says exactly what a first-or-last clue means, with no case analysis, and the same four lines serve every clue on every side.

Sources. Wijuko and ABC Logic both appeared on the puzzle page of the i, the compact sister paper of The Independent, and their integer-programming treatment is due to Martin J. Chlond, Puzzle—IP in the i, INFORMS Transactions on Education volume $16$, number $1$ ($2015$), pages $39$–$41$, which gives the Wijuko instance solved here and poses ABC Logic through a set of sufficient first-and-last conditions; the position-based reading of those conditions, and the ABC Logic instance with its eight clues, are the present chapter’s. The Suko comparison is to the puzzle of the Three Set Pieces chapter, after Jai Kobayaashi Gomer. The Wijuko solution is the one printed with the original puzzle; the ABC Logic grid and its uniqueness are produced and checked by the model above.