Brushing the Court Lines

On a clay court the closing courtesy is to leave the lines clean for the players who follow. Sweeping the surface is dull work, but brushing the painted lines is a small routing problem hiding in plain sight. The brush must pass along every line, the walker may stride across bare clay between lines when that saves steps, and there is no fixed place to begin or end. What is the shortest walk that brushes every line? Baker and Magazine posed exactly this in the INFORMS puzzle column, and it turns out to be a famous hard problem wearing tennis whites: the rural postman problem, the postman who must walk a chosen few streets of a town rather than all of them.

The puzzle

Take one half of a standard court, the side between the net and a baseline. Its painted lines form a small network. Number the twelve points where lines meet or end, as in Figure 30.1, and each line becomes a segment between two of them. There are twelve such segments: the two long doubles sidelines, the three pieces of the baseline, the two short pieces of each singles sideline, the two halves of the service line, and the centre service line. They measure $240$ feet of paint in all, and every foot must be brushed.

Three rules fix what counts as a walk. The brush may start at any point and finish at any point, because clubs keep no standard home for it. The walker need not stay on the lines: stepping straight across the clay from one point to another is allowed, and sometimes shortens the trip, so we treat every pair of the twelve points as joined by a straight stretch the walker may use. And a line may be brushed, or merely crossed, more than once; nothing forbids returning to a stretch already done. With those rules the question is sharp. Find the shortest walk, from any point to any point, that includes all twelve painted segments.

The lower bound writes itself. Any walk that brushes every line covers at least the $240$ feet of paint, so $240$ is a floor. The interest is in how far above it the geometry forces the walker, and why.

The model

A postman, not a salesman

The walk resembles a travelling-salesman tour, and the resemblance is worth pressing because it hands us a formulation. Index the twelve points by $j$, write $c_{jk}$ for the straight-line distance between points $j$ and $k$, and let the binary variable $x_{jk}$ be $1$ when the walk steps directly from $j$ to $k$. The length to minimise is then $\sum_{j}\sum_{k} c_{jk}\,x_{jk}$, exactly as for a salesman.

Three things separate this postman from the salesman, and each is one line of algebra. First, the salesman returns home; our walk need not. The standard repair is a phantom point, numbered $0$, a zero distance from every real point: $c_{0j}=c_{j0}=0$. A closed tour through the phantom, entering once and leaving once, is read back as an open walk whose start is the point after $0$ and whose finish is the point before it. So we ask for a tour and recover a walk. $$\sum_{j} x_{0j} = 1, \qquad \sum_{j} x_{j0} = 1 .$$

Second, the salesman visits each point exactly once; our walker may pass through a point as often as the brushing demands. The equality “one edge in, one edge out” relaxes to “at least one in, at least one out,” with a companion equation forcing the two counts to agree, so that every walk that enters a point also leaves it. $$\begin{gathered} \sum_{j} x_{jk} \ge 1, \qquad \sum_{k} x_{jk} \ge 1 \qquad (k, j \ge 1),\\[2pt] \sum_{k} x_{jk} = \sum_{k} x_{kj} \qquad (\text{all } j). \end{gathered}$$

Third, the salesman is free to choose his edges; our walker is not. Twelve particular segments, the painted lines, must appear in the walk. Call that set $E$. Brushing a line in either direction will do, so each required segment contributes one covering constraint. $$x_{jk} + x_{kj} \ge 1 \qquad \text{for every painted line } \{j,k\}\in E .$$ These are the salesman’s missing constraints: he had none, the postman has twelve.

The subtour question

One worry remains, the same one that dogs the salesman. The constraints so far could in principle be satisfied by two separate loops, each balanced and each covering some lines, with no single walk joining them. Such a disconnected solution is a subtour, and salesman models carry extra constraints to forbid it. We add them only if they are needed: solve, look at the result, and if it splits into loops, forbid that split with a cut requiring at least one edge to leave the offending set, then solve again. For this court the precaution proves idle. The first solve returns a single connected walk, so not one subtour cut is ever added, a small piece of luck that the geometry of a tennis court happens to grant.

The solver

import math
from itertools import product
from ortools.sat.python import cp_model

# the twelve points, in feet, with the net along y = 0
P = {1:(0,0), 2:(0,39), 3:(4.5,39), 4:(31.5,39), 5:(36,39),
     6:(36,0), 7:(4.5,0), 8:(4.5,21), 9:(18,21), 10:(31.5,21),
     11:(31.5,0), 12:(18,0)}
E = [(1,2),(2,3),(3,4),(4,5),(5,6),(10,11),
     (4,10),(3,8),(7,8),(8,9),(9,10),(9,12)]   # painted lines

def dist(a, b):
    (xa, ya), (xb, yb) = P[a], P[b]
    return round(100 * math.hypot(xa - xb, ya - yb))   # integer cents

def brush():
    real = list(P)
    nodes = [0] + real                  # 0 is the phantom point
    cost = {(a, b): 0 if 0 in (a, b) else dist(a, b)
            for a, b in product(nodes, nodes) if a != b}
    m = cp_model.CpModel()
    x = {e: m.NewBoolVar("") for e in cost}
    m.Add(sum(x[0, k] for k in real) == 1)    # leave phantom once
    m.Add(sum(x[j, 0] for j in real) == 1)    # return to it once
    for v in real:
        m.Add(sum(x[v, k] for k in nodes if k != v) >= 1)
        m.Add(sum(x[j, v] for j in nodes if j != v) >= 1)
    for v in nodes:                           # in-degree = out-degree
        m.Add(sum(x[v, k] for k in nodes if k != v)
              == sum(x[j, v] for j in nodes if j != v))
    for a, b in E:                            # brush each line either way
        m.Add(x[a, b] + x[b, a] >= 1)
    m.Minimize(sum(cost[e] * x[e] for e in cost))
    s = cp_model.CpSolver()
    while True:
        s.Solve(m)
        used = [e for e in cost if s.Value(x[e])]
        comp, adj = {0}, {}
        for a, b in used:
            adj.setdefault(a, []).append(b)
        stack = [0]
        while stack:                          # walk the chosen arcs
            for w in adj.get(stack.pop(), []):
                if w not in comp:
                    comp.add(w); stack.append(w)
        S = {v for e in used for v in e} - comp
        if not S:                             # one connected walk: done
            return s.ObjectiveValue() / 100, used
        m.Add(sum(x[a, b] for a in S          # else cut the subtour off
                  for b in nodes if b not in S and (a, b) in x) >= 1)

The model holds $156$ binary variables, an edge each way between the thirteen points, and solves in a blink. The shortest brushing walk is $280.5$ feet, and the solver reaches it with no subtour cut, just as promised. One optimal walk, starting at point $4$, is $$\begin{aligned} &4 \to 10 \to 11 \to 6 \to 5 \to 4 \to 3 \to 8 \to 3 \to 2 \to 1\\ &\qquad {}\to 7 \to 8 \to 9 \to 10 \to 9 \to 12 . \end{aligned}$$

Where the extra forty feet go

The walk costs $280.5$ feet against a floor of $240$, an overhead of $40.5$, and the figure shows where every foot of it is spent. Two kinds of move push the walker above the paint. The first is retracing: the segment $3$–$8$ and the segment $9$–$10$ are each brushed twice, once out and once back, because three painted lines meet at each of the junctions $8$, $9$ and $10$, and an odd tally of lines at a point cannot be cleared without arriving and leaving along one of them twice. That is $18 + 13.5 = 31.5$ feet of doubling. The second is crossing bare clay: to get from the outer corner across an alley the walker steps along the net, which carries no line, on the pieces $1$–$7$ and $11$–$6$, another $4.5 + 4.5 = 9$ feet. Add them to the paint and the account closes exactly, $240 + 31.5 + 9 = 280.5$.

The shape of the optimum

A single number invites a harder question: is the best walk unique, and if not, how many best walks are there? The model answers cleanly. Fix the length at its optimum and enumerate every solution, and exactly eight distinct sets of edges achieve $280.5$ feet. They are not eight unrelated routes but one route seen through the court’s symmetries: the left and right halves mirror each other, either retraced detour can be walked in either direction, and any walk reversed is a walk. Every one of the eight begins at point $3$, point $4$, or point $12$, and at no other point, which the model confirms a second way: forbid those three starts, by setting $x_{0,3}=x_{0,4}=x_{0,12}=0$, and the shortest walk that remains jumps to $285$ feet. The good starting points are the two ends of the baseline and the centre of the net, and beginning anywhere else costs the brusher four and a half extra feet before a single line is clean.

These eight edge sets do not exhaust the ways to walk them, since a fixed set of brushed and crossed segments can be traversed in more than one order; counting walking sequences rather than edge sets gives a larger tally still. Which number is “the” count of optima depends on whether a backtrack inserted at a different moment in the same route is a new solution or the same one taking a different breath. The integer program is honest about the distinction: it optimises over edge sets, and of those there are eight.

What the court teaches

The lesson is that a required-edge routing problem is a salesman model with two edits and a watchful eye. Relax the degree equalities to inequalities with a balance condition, add a covering constraint for each edge that must appear, and keep subtour elimination in reserve for when connectivity fails. The same three edits turn the salesman into the postman who must sweep a city’s snow routes, ink a plotter’s required strokes, or inspect a gas network’s mandatory pipes; the tennis court is only the gentlest instance, small enough to hold in the hand and to draw on a single page. What makes it a good teacher is that the overhead is legible. Forty and a half feet is not an oracle’s pronouncement but two retraced stubs and two alley steps, each of which you can see on the court and point to.

Sources. The puzzle and its salesman-style formulation follow Kenneth R. Baker and Michael J. Magazine, Puzzle—Brushing the Court Lines Optimally, INFORMS Transactions on Education volume $16$, number $2$ ($2016$), pages $79$–$83$. The optimal length of $280.5$ feet, the $285$ foot penalty for starting away from the three good points, and the lower bound of $240$ feet are theirs; the count of eight distinct optimal edge sets, and the reading of the $40.5$ foot overhead as $31.5$ feet of retracing plus $9$ feet of alley crossing, are reproduced and checked by the model above. The rural postman problem is one of the routing problems introduced by C. S. Orloff, “A Fundamental Problem in Vehicle Routing,” Networks volume $4$ ($1974$), pages $35$–$64$, and is shown NP-hard by J. K. Lenstra and A. H. G. Rinnooy Kan, “On General Routing Problems,” Networks volume $6$, number $3$ ($1976$), pages $273$–$280$; the kinder Chinese postman problem, where every edge must be walked, is solved in polynomial time by Jack Edmonds and Ellis L. Johnson, “Matching, Euler Tours and the Chinese Postman,” Mathematical Programming volume $5$ ($1973$), pages $88$–$124$.