The League Table

Aleague table is a summary, and summaries lose information. After a round of matches the table records, for each team, how many games it played, won, drew and lost, how many goals it scored and conceded, and how many points it took. The scores of the individual matches are gone, boiled down into those totals. Sometimes, though, the totals remember more than they seem to: from the bare table alone the actual scoreline of every match can be recovered, with no other clue. When that happens the table is a puzzle, and it is a puzzle an integer program is built to answer, because it asks not for the best of something but merely for the one arrangement of scores the totals will allow.

The puzzle

Four clubs play a single round, each meeting each of the others once: six matches in all. The season ends with the table below, three points for a win and one for a draw, the clubs listed in order of points. Recover the score of every match.

A little thought cracks it by hand. Pinner lost all three and scored nothing, so it was beaten in every game; its eight goals against are the goals the others put past it. Foxholt conceded only one goal all season, yet drew a game, so that drawn game was goalless and the single goal it conceded came elsewhere. Pull on these threads and the six scores come loose one by one. The point of a model is to pull on them all at once, and to know when the answer it finds is the only one.

The model

There is no quantity to maximise or minimise here. The table states facts, and we want scores consistent with every one of them; this is a pure feasibility problem, an integer program whose whole content is its constraints. Number the clubs $1$ to $4$ in table order. For each pair of clubs $\{i, j\}$ with $i < j$ there is at most one match, and we give it six variables: a flag $\mathrm{played}_{ij}$, the two goal counts $g_{ij}$ and $g_{ji}$ for the lower- and higher-numbered club, and three flags $\mathrm{win}^i_{ij}$, $\mathrm{win}^j_{ij}$, $\mathrm{draw}_{ij}$ recording which way the match went.

The table’s seven columns become seven families of constraints, each saying that a club’s totals are what its matches add up to. Writing the sum over a club $t$’s matches, its games played, its wins, its draws, its goals for and its goals against must equal the corresponding entries, and losses follow as played minus wins minus draws. A club counts a win in a match when it is the winning side of that match, whichever side of the pairing it sits on, and the sums are written to respect that.

What ties the goal counts to the result flags is the one piece of real modelling. A match is a home win, in our neutral labelling a win for club $i$, exactly when $g_{ij} > g_{ji}$, and that “exactly when” is forced by a pair of inequalities with a constant $M$ larger than any score, $$g_{ij} - g_{ji} - M\,\mathrm{win}^i_{ij} \le 0, \qquad g_{ij} - g_{ji} - (M+1)\,\mathrm{win}^i_{ij} \ge -M ,$$ the first making the flag fall to zero unless club $i$ leads, the second making it rise to one when it does. The mirror image governs a win for club $j$, and a played match that is neither is a draw, $$\mathrm{win}^i_{ij} + \mathrm{win}^j_{ij} + \mathrm{draw}_{ij} = \mathrm{played}_{ij} ,$$ while an unplayed pair carries no goals, $g_{ij}, g_{ji} \le M\, \mathrm{played}_{ij}$. That is the entire model.

The solver

from ortools.sat.python import cp_model

TEAMS = ["Foxholt", "Marden", "Westwell", "Pinner"]
# columns: played, won, drawn, lost, goals for, goals against, points
TABLE = [[3, 2, 1, 0, 5, 1, 7], [3, 2, 0, 1, 4, 2, 6],
         [3, 1, 1, 1, 3, 1, 4], [3, 0, 0, 3, 0, 8, 0]]
n = len(TEAMS)
pairs = [(i, j) for i in range(n) for j in range(i + 1, n)]
M = 10                                  # an upper bound on any score

def solve_league(table):
    m = cp_model.CpModel()
    played = {p: m.NewBoolVar("") for p in pairs}
    gi = {p: m.NewIntVar(0, M, "") for p in pairs}   # goals of club i
    gj = {p: m.NewIntVar(0, M, "") for p in pairs}   # goals of club j
    wi = {p: m.NewBoolVar("") for p in pairs}        # club i wins
    wj = {p: m.NewBoolVar("") for p in pairs}        # club j wins
    dr = {p: m.NewBoolVar("") for p in pairs}
    games = lambda t: [p for p in pairs if t in p]
    for t in range(n):
        P, W, D, Lo, GF, GA, _ = table[t]
        m.Add(sum(played[p] for p in games(t)) == P)
        m.Add(sum(wi[p] if p[0] == t else wj[p] for p in games(t)) == W)
        m.Add(sum(dr[p] for p in games(t)) == D)
        m.Add(sum(wj[p] if p[0] == t else wi[p] for p in games(t)) == Lo)
        m.Add(sum(gi[p] if p[0] == t else gj[p] for p in games(t)) == GF)
        m.Add(sum(gj[p] if p[0] == t else gi[p] for p in games(t)) == GA)
    for p in pairs:
        m.Add(gi[p] <= M * played[p])
        m.Add(gj[p] <= M * played[p])
        m.Add(gi[p] - gj[p] - M * wi[p] <= 0)        # i wins iff gi > gj
        m.Add(gi[p] - gj[p] - (M + 1) * wi[p] >= -M)
        m.Add(gj[p] - gi[p] - M * wj[p] <= 0)        # j wins iff gj > gi
        m.Add(gj[p] - gi[p] - (M + 1) * wj[p] >= -M)
        m.Add(wi[p] + wj[p] + dr[p] == played[p])
    s = cp_model.CpSolver()
    s.Solve(m)
    return {p: (s.Value(gi[p]), s.Value(gj[p])) for p in pairs}

The program returns the six scores of Figure 33.1: Foxholt past Marden, a goalless draw with Westwell, and the rest as the totals demand. Read the grid by row to see each club’s matches; the diagonal is dark because no club plays itself.

Whether the answer is the only one

A reconstruction is a real puzzle only if the table forces a single answer, and most tables do not. A goal total can be reached by many scorelines; a club that scored four across three games might have spread them three ways or four. The integer program can audit its own puzzle. Solve once to get a set of scores, then add a single constraint demanding that the next solution differ from this one in at least one match, and solve again. If the second solve fails, no other scores fit and the table is a sound puzzle; if it succeeds, the table is ambiguous and the second set of scores is the proof. For the table above the second solve fails: the six scores are unique, which is what earns the table its place here. Most four-club tables are not so obliging, and finding one that is took a short search.

What the puzzle teaches

Two lessons sit in this small table. The first is that an integer program need not optimise anything. Strip the objective away and what remains, the constraints, is a language for saying precisely what counts as a valid arrangement, and a solver will find one or report that none exists. A great many puzzles, and a great many real questions of scheduling and configuration, are feasibility problems wearing an optimisation costume. The second is the trick that did the real work: turning a comparison between two quantities, here which club scored more, into a yes-or-no variable, by trapping it between two inequalities scaled by a constant larger than any difference. That manoeuvre, the indicator constraint, reappears wherever a model must notice not just how big a number is but whether it crossed a line, and the league table is a painless place to see it first.

Sources. The puzzle type and its integer-programming model follow Martin J. Chlond, Puzzle—Integer Programming and League Table Puzzles, INFORMS Transactions on Education volume $11$, number $3$ ($2011$), pages $138$–$140$, including the home-and-away device for naming the two scores of a match, the column-consistency constraints, the indicator constraints linking scores to results, and the method of testing a table for a unique solution by forbidding a known one. The four-club table solved here is our own, with a unique reconstruction confirmed by the model; Chlond’s own examples include a World Cup group and, citing Rob Eastaway and John Haigh, Beating the Odds: The Hidden Mathematics of Sport (Robson Books, London, $2007$), smaller tables with missing and unplayed matches. The genre is older than the integer program: Chlond traces it to E. R. Emmet, Puzzles for Pleasure (Bell, New York, $1972$).