# Social golfer schedules that may or may not exist

A golf club wants weekly groups in which no two players ever play together twice, for as many weeks as possible. The original 32-player question is settled, but for some club sizes the longest possible schedule is still unknown, and these cases are equivalent to open questions about resolvable block designs.

## Problem

Let $v = g \cdot s$ players be split each week into $g$ groups of $s$ players. A schedule for $w$ weeks is valid if every week is a partition of the players into groups of size $s$ and any two players share a group in at most one week. Since each player meets $s - 1$ new partners per week, $w \le \lfloor (v-1)/(s-1) \rfloor$. The instance $g$-$s$-$w$ asks whether a valid schedule exists. For the cases below the bound has not been reached, and nobody knows whether it can be:

| Players $v$ | Groups $g$-$s$ | Best known $w$ | Upper bound | A schedule meeting the bound is equivalent to |
|---|---|---|---|---|
| 45 | 9-5 | 9 | 11 | a resolvable 2-(45, 5, 1) design |
| 92 | 23-4 | 29 | 30 | a resolvable 4-GDD of type $2^{46}$ |
| 140 | 35-4 | 45 | 46 | a resolvable 4-GDD of type $2^{70}$ |
| 164 | 41-4 | 53 | 54 | a resolvable 4-GDD of type $2^{82}$ |
| 188 | 47-4 | 61 | 62 | a resolvable 4-GDD of type $2^{94}$ |
| 200 | 50-4 | 65 | 66 | a resolvable 4-GDD of type $2^{100}$ |

Here a resolvable 4-GDD of type $2^u$ is a set of blocks of size 4 on $2u$ points, split into $u$ disjoint pairs, such that two points from the same pair never share a block, two points from different pairs share exactly one block, and the blocks fall into parallel classes that each cover every point once.

## Background

The problem was posted to the newsgroup sci.op-research in May 1998: 32 golfers play weekly in groups of four; for how many weeks can they play without two of them meeting twice? It entered CSPLib as problem 10, proposed by Warwick Harvey, and became a standard benchmark for symmetry breaking in constraint programming. The 32-player answer is 10 weeks, the trivial maximum, through a resolvable group divisible design; CSPLib's own page still calls it unknown but links a 10-week solution. Miller, Valkov and Abel (2025, unrefereed preprint) used resolvable designs to give best-known schedules for every club of up to 150 players and complete answers for groups of three or four players, with the exceptions listed above; the exceptions come from the published existence results for resolvable designs that they cite.

## What is known

- For 45 players in groups of five, an 11-week schedule would cover every pair exactly once, so it is the same as a resolvable 2-(45, 5, 1) design; its existence is open, and the best schedule known, from a resolvable transversal design, has 9 weeks.
- For groups of four with $v \equiv 8 \pmod{12}$, a schedule meeting the bound exists for all $v$ except 8 and 20, and possibly the cases above and $v \in \{236, 260, 404, 428\}$, where the needed design is not known to exist. There the best schedules known have $(v-5)/3$ weeks, one short of the bound [1]. (The appendix table of [1] prints the bound for 164 players as 64; the counting bound is $\lfloor 163/3\rfloor = 54$.)
- Greedy heuristics solve many instances quickly (Triska and Musliu, 2012), but for the cases above no method has yet produced the missing weeks.

## What would count as progress

- A schedule for one of the instances above with more weeks than the best known, given as a list of weeks, each a list of groups. A script checks in milliseconds that each week partitions the players and that no pair repeats.
- A proof that the bound cannot be reached for one of these cases, for example the non-existence of a resolvable 2-(45, 5, 1) design, ideally with a computer proof that others can rerun.

## References

1. A. Miller, I. Valkov and R. J. R. Abel (2025). Combinatorial solutions to the social golfer problem and social golfer problem with adjacent group sizes. arXiv:2507.23376. https://arxiv.org/abs/2507.23376
2. M. Triska and N. Musliu (2012). An effective greedy heuristic for the social golfer problem. *Annals of Operations Research* 194, 413–425. https://doi.org/10.1007/s10479-011-0866-7
3. W. Harvey, results page for the social golfer problem (2002, archived). http://web.archive.org/web/20050308115423/http://www.icparc.ic.ac.uk/~wh/golf/

## Source

Imported from [CSPLib prob010](https://www.csplib.org/Problems/prob010/), curated by CSPLib editors. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.