Three More from the Phone

Hartmann’s collection lines up six smartphone puzzles, each as an integer program, and two of them have already had their chapters: the Thermometer board, gentlest of the six, and Flow Free, the richest. The remaining four make three more models, and they are worth taking together because no two are alike underneath. Kakuro fills cells with digits and is an assignment with sums; Match 22 and its cousin Infinity Loop spin coloured disks into agreement and are a matching read off modular arithmetic; Slider walks a block to a square and is a shortest path. One paper, then, touches three of the staple model types, which is exactly why it makes a good tour.

Kakuro

Kakuro, sold also as Cross Sums, is an old paper-and-pencil puzzle. A grid has white cells to be filled with the digits one to nine and black cells that carry clues. Each maximal run of white cells, across or down, has a target, and the digits in the run must add to it and be all different. The all-different is the local Sudoku rule, one digit to a run; the target is what ties the runs together.

Variables

Hartmann gives each white cell $(i, j)$ and each digit $d \in \{1, \dots, 9\}$ a binary variable, $$x_{ijd} = 1 \iff \text{cell } (i, j) \text{ holds digit } d .$$ Write $C$ for the white cells, and let the runs be indexed $k = 1, \dots, K$, run $k$ covering the cell set $R_k$ with target $r_k$.

Constraints

Each white cell takes one digit; within a run no digit repeats; and the run’s digits hit its target: $$\sum_{d} x_{ijd} = 1 \ \ (\forall (i, j) \in C), \qquad \sum_{(i,j) \in R_k} x_{ijd} \le 1 \ \ (\forall k, d),$$ $$\sum_{(i,j) \in R_k} \sum_{d} d \, x_{ijd} = r_k \quad (\forall k) .$$ There is nothing to minimise. The listing below keeps the same feasible set but says it in the solver’s own terms: one integer variable per white cell, an all-different over each run, and the run’s sum fixed to its target. That is the binary model with the digit choice folded back into the value of a single variable.

from ortools.sat.python import cp_model

RUNS = [
    (11, [(1,1),(1,2),(1,3),(1,4)]), (14, [(1,6),(1,7)]),
    (34, [(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7)]),
    (23, [(3,3),(3,4),(3,5)]), (8, [(3,7),(3,8)]),
    (23, [(4,1),(4,2),(4,3)]), (11, [(4,6),(4,7),(4,8)]),
    (6, [(5,1),(5,2),(5,3)]), (14, [(5,6),(5,7),(5,8)]),
    (3, [(6,1),(6,2)]), (10, [(6,4),(6,5),(6,6)]),
    (36, [(7,2),(7,3),(7,4),(7,5),(7,6),(7,7),(7,8)]),
    (8, [(8,2),(8,3)]), (30, [(8,5),(8,6),(8,7),(8,8)]),
    (12, [(1,1),(2,1)]), (10, [(4,1),(5,1),(6,1)]),
    (6, [(1,2),(2,2)]), (18, [(4,2),(5,2),(6,2),(7,2),(8,2)]),
    (31, [(1,3),(2,3),(3,3),(4,3),(5,3)]),
    (13, [(7,3),(8,3)]), (12, [(1,4),(2,4),(3,4)]),
    (7, [(6,4),(7,4)]), (8, [(2,5),(3,5)]),
    (17, [(6,5),(7,5),(8,5)]), (14, [(1,6),(2,6)]),
    (26, [(4,6),(5,6),(6,6),(7,6),(8,6)]),
    (32, [(1,7),(2,7),(3,7),(4,7),(5,7)]),
    (7, [(7,7),(8,7)]), (8, [(3,8),(4,8),(5,8)]),
    (10, [(7,8),(8,8)]),
]

def solve_kakuro():
    cells = {c for _, cs in RUNS for c in cs}
    m = cp_model.CpModel()
    v = {c: m.NewIntVar(1, 9, "") for c in cells}
    for total, cs in RUNS:
        m.AddAllDifferent([v[c] for c in cs])
        m.Add(sum(v[c] for c in cs) == total)
    s = cp_model.CpSolver()
    s.Solve(m)
    return {c: s.Value(v[c]) for c in cells}

The thirty runs of Hartmann’s eight-by-eight board leave a single filling, the black cells shown as solid squares: $$\begin{array}{cccccccc} 3 & 1 & 5 & 2 & \blacksquare & 8 & 6 & \blacksquare \\ 9 & 5 & 7 & 1 & 2 & 6 & 4 & \blacksquare \\ \blacksquare & \blacksquare & 8 & 9 & 6 & \blacksquare & 5 & 3 \\ 6 & 8 & 9 & \blacksquare & \blacksquare & 2 & 8 & 1 \\ 3 & 1 & 2 & \blacksquare & \blacksquare & 1 & 9 & 4 \\ 1 & 2 & \blacksquare & 1 & 3 & 6 & \blacksquare & \blacksquare \\ \blacksquare & 4 & 8 & 6 & 5 & 9 & 1 & 3 \\ \blacksquare & 3 & 5 & \blacksquare & 9 & 8 & 6 & 7 \end{array}$$ A solution count confirms there is no other, as a well-set Kakuro promises.

Match 22 and Infinity Loop

Match 22 is a board of coloured disks. Every disk is cut into four quarter-segments, each coloured, and the player turns disks until the touching segments of every pair of neighbours agree. A turn is one left, or counter-clockwise, quarter-rotation, and the score is the total number of turns, so the disks should be brought into line with as few as possible.

Variables

Number the disks $i = 1, \dots, n$ and their segments $0, 1, 2, 3$ for top, left, bottom, right. A disk may be left as it is or turned one, two or three times, and one binary variable records the choice, $$x_{ij} = 1 \iff \text{disk } i \text{ is given } j \text{ left turns}, \qquad j \in \{0, 1, 2, 3\} .$$

Constraints

A left turn carries the segment at position $h$ round to position $h + 1$, so after $j$ turns the segment now showing at position $h$ is the one that started at position $(h - j) \bmod 4$. Let $d_{ih}$ be the starting colour of segment $h$ of disk $i$. Then the colour now at any position is a sum over the single chosen $j$, and the matching rules become linear. Where $k$ sits to the right of $i$ their touching sides are the right of $i$ (segment $3$) and the left of $k$ (segment $1$); where $k$ sits below $i$ the sides are the bottom of $i$ (segment $2$) and the top of $k$ (segment $0$). With $H$ the horizontal neighbour pairs and $V$ the vertical ones, $$\sum_j x_{ij} = 1 \quad (\forall i),$$ $$\sum_j d_{i,(3-j) \bmod 4}\, x_{ij} = \sum_j d_{k,(1-j) \bmod 4}\, x_{kj} \quad ((i, k) \in H),$$ $$\sum_j d_{i,(2-j) \bmod 4}\, x_{ij} = \sum_j d_{k,(0-j) \bmod 4}\, x_{kj} \quad ((i, k) \in V),$$ and the objective counts the turns, $\min \sum_i \sum_j j \, x_{ij} .$ The shift by $j$ inside the colour index is the whole trick: it lets a rotation, which is awkward to write as a constraint, ride along as a relabelling of fixed data.

from ortools.sat.python import cp_model

def solve_match22(d, H, V, borders=None):
    n = len(d)
    m = cp_model.CpModel()
    x = {(i, j): m.NewBoolVar("")
         for i in range(1, n + 1) for j in range(4)}
    for i in range(1, n + 1):
        m.Add(sum(x[i, j] for j in range(4)) == 1)

    def show(i, h):  # colour now showing at position h
        return sum(d[i][(h - j) % 4] * x[i, j]
                   for j in range(4))

    for i, k in H:
        m.Add(show(i, 3) == show(k, 1))
    for i, k in V:
        m.Add(show(i, 2) == show(k, 0))
    for i, h in (borders or []):    # no line off the edge
        m.Add(show(i, h) == 0)
    m.Minimize(sum(j * x[i, j] for i in range(1, n + 1)
                   for j in range(4)))
    s = cp_model.CpSolver()
    s.Solve(m)
    turns = {i: next(j for j in range(4) if s.Value(x[i, j]))
             for i in range(1, n + 1)}
    return int(s.ObjectiveValue()), turns

On Hartmann’s twenty-disk level the matching is reached in twenty-eight turns, and that minimum is met one way only. The disks turned are, in order, none for the first two, then one, none three times, one, three, one, none twice, two, three, two, two, three, three, two, three, two: thirteen disks moved, twenty-eight turns spent, every seam in agreement.

Infinity Loop

Infinity Loop is the same model wearing different data. Each tile carries not colours but line ends, a connection present or absent on each of its four sides, and the tiles are turned until every line runs unbroken from tile to tile and no line points off the board. So $d_{ih} \in \{0, 1\}$ now marks a connection, the neighbour equations above become both present or both absent along each shared side, and one rule is added that Match 22 did not need: a tile on an edge of the board must not offer a connection to the outside. Writing $B_{\text{top}}$, $B_{\text{left}}$, $B_{\text{bottom}}$ and $B_{\text{right}}$ for the tiles on each border, $$\sum_j d_{i,(h-j) \bmod 4}\, x_{ij} = 0$$ for every border tile $i$ and its outward side $h$. These are the borders passed to the solver above, a list of (tile, side) pairs.

Take a three-by-three frame: eight tiles around a blank centre, the four corners each an elbow and the four edges each a straight, handed to the solver in scrambled orientations. The border rule forbids any line leaving the frame, and the only way to close every connection inside it is the single ring, $$\begin{array}{ccc} \ulcorner & - & \urcorner \\ \mid & \ \cdot\ & \mid \\ \llcorner & - & \lrcorner \end{array}$$ the centre staying empty. The turn counts that reach it are not unique, since spinning the blank centre or half-turning a straight piece moves no line, but the loop itself, the only thing the puzzle shows, is forced.

Slider

In the Slider app a block sits on a grid of cells, some of them obstacles, and is to be pushed to a marked target in the fewest moves. A push sends the block sliding until it hits the far wall or the cell just before an obstacle; it cannot stop partway. This is a shortest path, and the only work is to read off the graph: a node for each cell, and an arc from a cell to every cell the block can come to rest on in one slide.

Variables and constraints

Let $S_{ij}$ list the cells reachable from $(i, j)$ in one slide, the successors. An arc-variable records each move, $$x_{ijkl} = 1 \iff \text{the block slides from } (i, j) \text{ to } (k, l), \quad (k, l) \in S_{ij} .$$ One unit of flow leaves the start and arrives at the target, every other cell passing on what it receives, and the moves are counted: $$\min \sum x_{ijkl} \quad \text{subject to flow balance at every cell,}$$ with a surplus of one at the start and a deficit of one at the target. A path is the cheapest flow, and minimising the arcs is minimising the moves.

from ortools.sat.python import cp_model

def solve_slider(succ, start, target):
    m = cp_model.CpModel()
    edges = [(a, b) for a in succ for b in succ[a]]
    x = {e: m.NewBoolVar("") for e in edges}
    for v in succ:
        out = sum(x[a, b] for a, b in edges if a == v)
        inc = sum(x[a, b] for a, b in edges if b == v)
        if v == start:
            m.Add(out - inc == 1)
        elif v == target:
            m.Add(inc - out == 1)
        else:
            m.Add(inc == out)
    m.Minimize(sum(x.values()))
    s = cp_model.CpSolver()
    s.Solve(m)
    return [e for e in edges if s.Value(x[e])]

On Hartmann’s small board the block starts at $(3, 2)$ and must reach $(5, 3)$. Three slides do it and no fewer: from $(3, 2)$ up to $(2, 2)$, along to $(2, 3)$, and down the column to $(5, 3)$. The path is unique, the one shortest route through the obstacles.

Three puzzles, three of the standard shapes: a constrained assignment, a matching turned linear by a modular relabelling, and a shortest path. With the Thermometer board and Flow Free from the earlier chapters, the whole of Hartmann’s smartphone collection now sits in the book, six apps that between them rehearse most of what a first course in modelling sets out to teach.

Sources. All three puzzles, with the Thermometer board of the previous chapter and Flow Free, are modelled by Sönke Hartmann, Puzzle—Solving Smartphone Puzzle Apps by Mathematical Programming, INFORMS Transactions on Education volume $18$, number $2$ ($2018$), pages $127$–$141$, which supplies the binary digit model for Kakuro, the modular rotation model for Match 22 and its border extension for $\infty$ Infinity Loop, and the shortest-path model for Slider. The Kakuro board, the twenty-disk Match 22 level and the Slider example are Hartmann’s own instances, given in his appendices; their solutions (the unique grid, the twenty-eight-turn alignment, the three-slide path) are reproduced by the models above and each checked unique. The three-by-three Infinity Loop frame is the present chapter’s, its single closed loop confirmed by an independent solution count. The apps are credited by Hartmann to Pink Pointer Games (Kakuro), Abhinav Bhadoria of Zero Logic Games (Match 22), Muhammad Satar and Balys Valentukevicius ($\infty$ Infinity Loop), and Alex Gwyn (Slider).