Three Set Pieces

Not all puzzle data fits a rectangle. A model is at its happiest when the givens line up in a neat array, one number per cell, but many puzzles refuse to oblige: a runner has however many witnesses to his finishing place, a coloured region has however many cells. The remedy is to stop forcing the data into a grid and to describe it instead as a family of sets, each constraint then a sum or an all-different over whichever set it concerns. Three puzzles show the move, each awkward in its own way and each tamed by the same idea.

A queue from scraps

The first is a ranking puzzle. Ten runners finish a marathon, and all we are told is a heap of pairwise results: this one beat that one, who beat two others, and so on, with no runner carrying the same number of mentions as the next. From the heap, recover the finishing order. Each runner brings a set of people he beat, of whatever size, and that is exactly the data that will not sit in a column.

Give each runner a position, all distinct, and read every result as one inequality: a winner’s position is smaller than his victim’s. The inequalities, gathered from the sets, pin the order completely.

from ortools.sat.python import cp_model

BEAT = {
    "Matthew": ["Tom", "Jimmy", "Kevin"],
    "Peter": ["Jimmy", "Tom", "Alan", "Zach", "Graham"],
    "Graham": ["Tom", "Kevin"],
    "Zach": ["Frank", "Matthew"],
    "Frank": ["Graham", "Tom", "Matthew", "Brian"],
    "Tom": ["Brian"],
    "Alan": ["Zach", "Kevin", "Graham", "Matthew", "Tom"],
    "Brian": ["Kevin"],
    "Jimmy": ["Tom", "Graham", "Brian"],
}

def solve_queue():
    runners = sorted(set(BEAT).union(*BEAT.values()))
    m = cp_model.CpModel()
    pos = {r: m.NewIntVar(0, len(runners) - 1, "") for r in runners}
    m.AddAllDifferent(list(pos.values()))
    for winner, losers in BEAT.items():
        for loser in losers:
            m.Add(pos[winner] < pos[loser])  # winner is earlier
    s = cp_model.CpSolver()
    s.Solve(m)
    return sorted(runners, key=lambda r: s.Value(pos[r]))

The clues leave exactly one order, from first to last: Peter, Alan, Zach, Frank, Matthew, Jimmy, Graham, Tom, Brian, Kevin. The model does not so much search for it as let the inequalities settle, a chain of beats that admits no other arrangement.

Suko

The second is Suko, a small grid that has run in The Times. The nine cells hold the digits one to nine, each once. Four inner totals are given, one for each of the four overlapping two-by-two blocks, each equal to the sum of the four cells around it. And the cells are painted in colour groups, the digits of each group summing to a stated colour total; the groups are of unequal size, which is where the set notation pays its way again.

from ortools.sat.python import cp_model

INNER = {(0, 0): 25, (0, 1): 19, (1, 0): 24, (1, 1): 19}
GROUPS = {22: [(0, 0), (0, 1), (1, 1)], 8: [(0, 2), (1, 2), (2, 2)],
          15: [(1, 0), (2, 0), (2, 1)]}

def solve_suko():
    m = cp_model.CpModel()
    v = {(i, j): m.NewIntVar(1, 9, "") for i in range(3) for j in range(3)}
    m.AddAllDifferent(list(v.values()))
    for (i, j), t in INNER.items():
        m.Add(sum(v[i + di, j + dj] for di in (0, 1) for dj in (0, 1)) == t)
    for total, cells in GROUPS.items():
        m.Add(sum(v[c] for c in cells) == total)
    s = cp_model.CpSolver()
    s.Solve(m)
    return [[s.Value(v[i, j]) for j in range(3)] for i in range(3)]

The four block-sums and three group-sums leave one filling, Figure 41.1.

Strimko

The third is Strimko, a Latin-square puzzle in the Sudoku family. The digits one to $n$ fill an $n \times n$ grid so that each row and each column carries them all, and so too does each stream, a connected chain of $n$ cells laid across the grid. The streams replace Sudoku’s boxes, and being arbitrary connected shapes they are the set data once more. A handful of givens fix the rest.

from ortools.sat.python import cp_model

STREAMS = [
    [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)],
    [(0, 1), (0, 2), (0, 3), (0, 4), (1, 4)],
    [(1, 1), (1, 2), (1, 3), (2, 3), (2, 4)],
    [(3, 0), (3, 1), (4, 0), (4, 1), (4, 2)],
    [(3, 2), (3, 3), (3, 4), (4, 3), (4, 4)],
]
GIVENS = {(1, 3): 4, (3, 4): 3, (4, 1): 2, (4, 2): 3, (4, 3): 5}

def solve_strimko(n=5):
    m = cp_model.CpModel()
    v = {(i, j): m.NewIntVar(1, n, "") for i in range(n) for j in range(n)}
    for i in range(n):
        m.AddAllDifferent([v[i, j] for j in range(n)])  # rows
        m.AddAllDifferent([v[j, i] for j in range(n)])  # columns
    for stream in STREAMS:
        m.AddAllDifferent([v[c] for c in stream])        # streams
    for c, d in GIVENS.items():
        m.Add(v[c] == d)
    s = cp_model.CpSolver()
    s.Solve(m)
    return [[s.Value(v[i, j]) for j in range(n)] for i in range(n)]

Rows, columns and streams are three families of all-different sets, and five givens cut the rest to the single solution of Figure 41.2.

Across the three, the awkward data was always the same shape underneath: a family of subsets of the cells, irregular in size, over which a sum or an all-different is asked. Once the puzzle is read that way the model writes itself, and the differences between a marathon, a sum-grid and a Latin square shrink to which operation rides on top of the sets.

Sources. The three puzzles and the set-notation theme follow Martin J. Chlond, Puzzle—Three Set Pieces, INFORMS Transactions on Education volume $14$, number $2$ ($2014$), pages $105$–$107$. The marathon ranking is from brainbashers.com, as Chlond credits, and its finishing order is reproduced and shown unique by the model above. Suko was created by Jai Kobayaashi Gomer (Kobayaashi Studios) in $2010$ and has appeared in The Times; the instance here is Chlond’s, and its solution is checked against all four inner totals and three colour totals. Strimko was devised by the Grabarchuk family (Serhiy, Tanya, Peter and Helen Grabarchuk) in $2008$; the instance drawn here is our own, its five streams and five givens designed so that rows, columns and streams admit exactly one filling, which an independent solution count confirms.