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:

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, 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.