The Degree Is the Data

Some puzzles hand you a graph and ask for its colours; others hand you the colours and ask for the graph. Two more of Hartmann’s apps share a quiet idea: in each, the data is a list of degrees, how many things meet at a point. V3ck fixes a graph and tells you, for every node, how many of its edges must take each colour. Monodot gives no graph at all, only how many neighbours each node should end with, and asks you to build one by placing the nodes on a grid. The first realises a degree specification by colouring; the second realises it by construction.

V3ck

The app shows a graph, its nodes and edges drawn on the screen, and a palette of colours. Each node carries a little tally: so many of my edges red, so many green, so many blue. Colour every edge with one colour so that each node’s tally is met. It is a cousin of edge-colouring, but the familiar rule that touching edges must differ is gone; here a node may repeat a colour, it simply has to repeat it the right number of times.

Variables

An edge is undirected, but a tally belongs to a node, so it is easier to look down each edge from both ends. Split every edge $\{i, j\}$ into two arcs, $(i, j)$ and $(j, i)$, and let a binary variable colour each arc, $$x_{ijk} = 1 \iff \text{arc } (i, j) \text{ takes colour } k, \qquad k = 1, \dots, C .$$

Constraints

Each arc gets one colour; the two arcs of an edge must agree, so the edge has a single colour; and at each node the arcs leaving it carry colour $k$ exactly $a_{ik}$ times, the node’s tally: $$\sum_k x_{ijk} = 1 \ \ (\forall\, \text{arcs } (i, j)), \qquad x_{ijk} = x_{jik} \ \ (\forall\, \text{edges } \{i, j\},\ k),$$ $$\sum_{(i, j)} x_{ijk} = a_{ik} \quad (\forall\, \text{node } i,\ k),$$ the last sum running over the arcs that leave node $i$. There is nothing to optimise.

from ortools.sat.python import cp_model

def solve_v3ck(nodes, edges, C, a):
    m = cp_model.CpModel()
    arcs = []
    for i, j in edges:
        arcs += [(i, j), (j, i)]
    x = {(i, j, k): m.NewBoolVar("")
         for (i, j) in arcs for k in range(1, C + 1)}
    for i, j in arcs:
        m.Add(sum(x[i, j, k] for k in range(1, C + 1)) == 1)
    for i, j in edges:
        for k in range(1, C + 1):
            m.Add(x[i, j, k] == x[j, i, k])
    for v in nodes:
        for k in range(1, C + 1):
            m.Add(sum(x[i, j, k] for (i, j) in arcs if i == v)
                  == a.get((v, k), 0))
    s = cp_model.CpSolver()
    s.Solve(m)
    return {(i, j): next(k for k in range(1, C + 1)
                         if s.Value(x[i, j, k]))
            for (i, j) in edges}

Take five nodes and the eight edges $\{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}, \{2,5\}, \{3,4\}, \{3,5\}, \{4,5\}$, with three colours and the tallies $$\begin{array}{c|ccc} \text{node} & c_1 & c_2 & c_3 \\ \hline 1 & 2 & 1 & 0 \\ 2 & 2 & 1 & 0 \\ 3 & 3 & 1 & 0 \\ 4 & 1 & 1 & 1 \\ 5 & 0 & 2 & 1 \end{array}$$ Each row sums to the node’s degree, as it must, since every edge at a node is counted once. The tallies leave exactly one colouring: colour $c_1$ takes the edges $\{1,2\}, \{1,3\}, \{2,3\}, \{3,4\}$, colour $c_2$ takes $\{1,4\}, \{2,5\}, \{3,5\}$, and colour $c_3$ takes the single edge $\{4,5\}$. An independent count finds no other, which is not guaranteed in general: swap two colours around an even cycle whose edges alternate between them and the tallies are unchanged, so a graph with such a cycle has several colourings. This instance has none.

Monodot

Monodot gives a row of loose nodes, each labelled with a number, and an empty grid. Drop a node on a cell and the app wires it to every node already sitting in one of the eight cells around it, the neighbours a king would reach. The label is the degree the node should finish with, its count of neighbours, and the puzzle is solved when every label is honoured. So the data is a multiset of wanted degrees, and a solution is a placement that delivers them.

Variables

Let $a_t$ be how many nodes want $t$ neighbours, $t = 1, \dots, 8$. A binary variable places a node of each kind on each cell, and a companion records whether a cell is used at all: $$x_{ijt} = 1 \iff \text{a degree-}t\text{ node sits at } (i, j), \qquad o_{ij} = \sum_t x_{ijt} .$$

Constraints

A cell holds at most one node; every node is placed; and the heart of it, a placed node’s count of occupied king-neighbours must equal its label. Writing $N_{ij}$ for the cells a king reaches from $(i, j)$, the degree $\sum_{(k,l) \in N_{ij}} o_{kl}$ is pinned from both sides, with a big constant $M = 8$ that lets the upper bound go slack on an empty cell: $$o_{ij} \le 1, \qquad \sum_{(i,j)} x_{ijt} = a_t \ \ (\forall t),$$ $$\sum_{(k,l) \in N_{ij}} o_{kl} \ \ge\ \sum_t t\, x_{ijt},$$ $$\sum_{(k,l) \in N_{ij}} o_{kl} \ \le\ \sum_t t\, x_{ijt} + M\,(1 - o_{ij}) .$$ On a used cell the two bounds meet and the degree equals the label; on an empty one the upper bound is $M$ and says nothing.

from ortools.sat.python import cp_model

def king(n, i, j):
    return [(i + di, j + dj)
            for di in (-1, 0, 1) for dj in (-1, 0, 1)
            if (di, dj) != (0, 0)
            and 0 <= i + di < n and 0 <= j + dj < n]

def solve_monodot(n, a):
    m = cp_model.CpModel()
    cells = [(i, j) for i in range(n) for j in range(n)]
    T = sorted(a)
    x = {(i, j, t): m.NewBoolVar("")
         for (i, j) in cells for t in T}
    o = {(i, j): m.NewBoolVar("") for (i, j) in cells}
    for i, j in cells:
        m.Add(sum(x[i, j, t] for t in T) <= 1)
        m.Add(o[i, j] == sum(x[i, j, t] for t in T))
    for t in T:
        m.Add(sum(x[i, j, t] for (i, j) in cells) == a[t])
    for i, j in cells:
        deg = sum(o[k, l] for (k, l) in king(n, i, j))
        req = sum(t * x[i, j, t] for t in T)
        m.Add(deg >= req)
        m.Add(deg <= req + 8 * (1 - o[i, j]))
    s = cp_model.CpSolver()
    s.Solve(m)
    return {(i, j): t for (i, j) in cells for t in T
            if s.Value(x[i, j, t])}

Ask for five nodes, one wanting four neighbours and four wanting three, on a five-by-five grid. Only one shape obliges. The node of degree four needs four neighbours, and the four others, each of degree three, must be those neighbours and must also see two of each other; the single arrangement is a plus, the high-degree node at the centre and its four companions on the arms: $$\begin{array}{ccccc} \cdot & \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & 3 & \cdot & \cdot \\ \cdot & 3 & 4 & 3 & \cdot \\ \cdot & \cdot & 3 & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot & \cdot \end{array}$$ The model finds nine solutions, but they are the same plus slid to nine positions on the grid: the degrees fix the shape of the graph, and the board only says it may sit anywhere it fits. That gap, a structure determined while its placement is free, is worth naming, because it is the usual reason a puzzle with one picture reports many solutions.

Both puzzles began with a degree list and asked for the object that realises it, one by handing out colours along fixed edges, the other by choosing where edges should form. The tally and the label are the same kind of datum, a count at a node, and in each the model is just the sentence that says: make the counts come true.

Sources. V3ck and Monodot, with four further apps (Starbattle, Circuit Scramble, Binary Sudoku, and a knight’s tour), are modelled by Sönke Hartmann, Puzzle—More Logic Puzzle Apps Solved by Mathematical Programming, INFORMS Transactions on Education volume $20$, number $1$ ($2019$), pages $49$–$55$, which gives the arc-and-tally model for V3ck and the placement-and-degree model for Monodot. The five-node graph with its tallies and the five-node Monodot instance are the present chapter’s own; the unique V3ck colouring and the plus (unique up to where it sits) are each produced and checked by the models above. Hartmann credits the V3ck app to Leia and Nicolas Jobard (Dark Eye, France) and thanks his daughter Solvei for pointing him to Monodot.