Tennis Mixed Doubles

Ten men and ten women meet to play mixed doubles. A round is five matches played at once, each match a man and a woman on one side against a man and a woman on the other, so all twenty are on court every round. The players are sociable but particular: no two people should ever partner each other twice, and no two should ever find themselves on opposite sides twice. Partnering someone one week and opposing them another is fine; what is barred is a repeat of either kind. How many rounds can they play before the conditions force a stop?

Where the rounds run out

An easy ceiling comes from the men alone. In every round a man has exactly one man on the far side of his net, his opposite number for that match. There are nine other men, and he may face each at most once, so he runs out of fresh opponents after nine rounds. The women give the same bound, and the partnership and mixed-opposition limits are looser still, each allowing up to ten. Nine rounds is therefore the most that could conceivably be played.

Reaching nine, or even knowing how close one can get, is another matter. The puzzle is a scheduling problem of the kind that combinatorial design theory studies, cousin to the round-robin and the Room square, and these are notorious for having clean upper bounds that the actual constructions fall short of. Dick Hess, who posed the problem, found a schedule of seven rounds by an exhaustive computer search. Whether eight are possible he left open.

The model

Index the men $1, \ldots, n$ and the women $1, \ldots, n$ (here $n = 10$), and the rounds $1, \ldots, m$. A single five-index Boolean variable records an entire match: $$x_{g h i j k} = \begin{cases} 1 & \text{man } g \text{ and woman } h \text{ play man } i \text{ and woman } j \text{ in round } k,\\ 0 & \text{otherwise.} \end{cases}$$ A match names two sides with no inherent order, so the same match is recorded both ways round; the model is told they mean the same thing, $$x_{g h i j k} = x_{i j g h k} \qquad \forall\, g, h, i, j \in N,\; k \in M.$$

The tournament conditions are then a short list of linear constraints, each a count held to one. In every round each man, and each woman, plays exactly one match: $$\sum_{h, i, j} x_{g h i j k} = 1 \quad \forall g, k, \qquad \sum_{g, i, j} x_{g h i j k} = 1 \quad \forall h, k.$$ Across the whole tournament, each pair of men meet on opposite sides at most once, and likewise each pair of women: $$\sum_{h, j, k} x_{g h i j k} \le 1 \;\; \forall g \neq i, \qquad \sum_{g, i, k} x_{g h i j k} \le 1 \;\; \forall h \neq j.$$ Each man-woman partnership, and each man-woman opposition, occurs at most once: $$\sum_{i, j, k} x_{g h i j k} \le 1 \;\; \forall g, h, \qquad \sum_{h, i, k} x_{g h i j k} \le 1 \;\; \forall g, j.$$ Finally a man never opposes himself and a woman never opposes herself, $\sum_{h,j,k} x_{g h g j k} = 0$ and $\sum_{g,i,k} x_{g h i h k} = 0$. There is nothing to maximise: a tournament of $m$ rounds either exists or it does not, so the question is pure feasibility, and a single feasible assignment is a schedule.

A solver

The model reads almost exactly as the constraints are written, each condition a loop of linear sums over the unconstrained indices.

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

def solve(n, m, seconds=60):
    M = cp_model.CpModel()
    R, K = range(n), range(m)
    x = {z: M.NewBoolVar("") for z in product(R, R, R, R, K)}
    for g, h, i, j, k in x:  # a match has two sides
        M.Add(x[g,h,i,j,k] == x[i,j,g,h,k])
    for g, k in product(R, K):  # man g plays one match
        M.Add(sum(x[g,h,i,j,k] for h,i,j in product(R,R,R)) == 1)
    for h, k in product(R, K):  # woman h plays one match
        M.Add(sum(x[g,h,i,j,k] for g,i,j in product(R,R,R)) == 1)
    for g in R:  # man g never opposes himself
        M.Add(sum(x[g,h,g,j,k] for h,j,k in product(R,R,K)) == 0)
    for h in R:  # woman h never opposes herself
        M.Add(sum(x[g,h,i,h,k] for g,i,k in product(R,R,K)) == 0)
    for g, i in product(R, R):  # men g, i meet at most once
        if g != i:
            M.Add(sum(x[g,h,i,j,k] for h,j,k in product(R,R,K)) <= 1)
    for h, j in product(R, R):  # women h, j meet at most once
        if h != j:
            M.Add(sum(x[g,h,i,j,k] for g,i,k in product(R,R,K)) <= 1)
    for g, h in product(R, R):  # partnership g-h at most once
        M.Add(sum(x[g,h,i,j,k] for i,j,k in product(R,R,K)) <= 1)
    for g, j in product(R, R):  # man g vs woman j at most once
        M.Add(sum(x[g,h,i,j,k] for h,i,k in product(R,R,K)) <= 1)
    s = cp_model.CpSolver()
    s.parameters.max_time_in_seconds = seconds
    s.parameters.num_search_workers = 8
    if s.Solve(M) not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        return None
    sched = []
    for k in K:
        games = [((g,h), (i,j)) for g,h,i,j in product(R,R,R,R)
                 if g < i and s.Value(x[g,h,i,j,k])]
        sched.append(games)
    return sched

Seven rounds, and the wall after

When Chlond first ran this model the seven-round case was a trial. Six rounds came in under an hour; seven ran overnight and failed, and a schedule appeared only after three rounds were fixed by hand to give the search a start. A constraint solver of the present day finds all seven at once, from nothing, in well under a minute. Figure 37.1 shows one such schedule, the seven rounds it returns, every condition met.

The eighth round is where it stops, or seems to. Neither Hess’s search nor Chlond’s program found an eight-round schedule, and a short search with the model above does not settle it either: the solver neither produces an eighth round nor proves that none exists. Seven remains the best schedule its sources record, one short of the bound of nine, and the gap between what the counting argument permits and what can be built is exactly the kind of thing that makes scheduling designs hard.

Sources. The problem was set by Richard I. Hess and presented at the eighth Gathering for Gardner, the recreational mathematics meeting held in Atlanta in honour of Martin Gardner; Hess gives his seven-round solution and surrounding discussion in “Scheduling Tennis Doubles Competitions,” in A Lifetime of Puzzles, edited by Erik D. Demaine, Martin L. Demaine and Tom Rodgers (A. K. Peters, Wellesley, $2008$), pages $303$–$311$. The integer-programming formulation, the nine-round bound, and the report that six rounds solved quickly while seven needed a partial schedule to seed it are from Martin J. Chlond, Puzzle—Tennis Mixed Doubles, INFORMS Transactions on Education volume $9$, number $2$ ($2009$), pages $93$–$97$. The seven-round schedule drawn here was produced by the model above and is checked against every tournament condition by tools/gen_tennis_fig.py before the figure is drawn; that modern solvers find it unaided, where the original needed a hand-built seed, is a remark about a decade and a half of progress in constraint solving, not about the puzzle.