6 Scheduling a Golf Tournament

Problem Specification

There are 32 individually playing golfers who play in groups of 4, so-called foursomes. For every week of the golf tournament new sets of foursomes are to be compiled. The task is to assign foursomes for a given number of weeks such that no player plays with another player in a foursome twice.

Maximal Number of Weeks

The upper bound for the number of weeks is 10 weeks due to the following argument. There are {32 \choose 2}= 496 pairing of players. Each foursome takes 6 pairings and every week consists of 8 foursomes, hence, every week occupies 48 pairings. Having only 496 pairings available, at most \lfloor496/48\rfloor=10 weeks can be assigned without duplicating foursomes. Unfortunately, only assignments for 9 weeks could be found so far. Fortunately again, this assignment could only be found by solvers using set constraints. Other approaches, using linear integer programming, failed for this problem size.


A foursome is modeled as a set of cardinality 4. A week is a collection of foursomes and all foursomes of a week are pairwise disjoint and their union is the set of all golfers. This leads to a partition constraint. Further, each foursome shares at most one element with any other foursome, since a golfer, of course, may occur in different foursomes but only on his own. Therefore, the cardinality of the intersection of a foursome with any other foursome of the other weeks has to be either 0 or 1.

Distribution Strategy

The distribution strategy is crucial for this problem.1 A player is taken and assigned to all possible foursomes. Then the next player is taken and assigned and so on. This player-wise distribution allows to solve instances of that problems up to 9 weeks. The approach, coming usually into mind first, to distribute a foursome completely, fails even for smaller instances of the problem.


The function Golf returns a solver to find an assignment for NbOfFourSomes foursomes per week and NbOfWeeks weeks duration. The number of players is computed from NbOfFourSomes and stored in NbOfPlayers. The auxiliary function Flatten is used to flatten a list of lists of variables. Its definition is necessary since the library function of the same name works only on ground terms.

The procedure DistrPlayers implements the player-wise distribution strategy. It tries to create for every player on every foursome a choice point by simply enumerating all players and iterating for each player over all foursomes.

The variable Weeks holds NbOfWeeks weeks. A week is a list of foursomes. A foursome is modeled as a set. All sets are subsets of \{1,\ldots,\mbox{NbOfPlayers}\} and have exactly 4 elements. Further, the sets modeling the foursomes of a week form a partition of the set \{1,\ldots,\mbox{NbOfPlayers}\}. These constraints are imposed by the first ForAll loop.

The following nested loops (ForAllTail and ForAll) impose that every foursome shares at most one element with any other foursome of other weeks. Finally, the distribution procedure is called with a flattened copy of Weeks, i. e., a list of all foursomes.

fun {Golf NbOfWeeks NbOfFourSomes}
   NbOfPlayers = 4*NbOfFourSomes
   fun {Flatten Ls}
      {FoldL Ls fun {$ L R}
                   if R==nil then L
                   else {Append L R} end 
                end nil}
   proc {DistrPlayers AllWeeks Player Weeks}
         case Weeks
         of FourSome|Rest then 
            dis {FS.include Player FourSome} then 
               {DistrPlayers AllWeeks Player Rest}
            [] {FS.exclude Player FourSome} then 
               {DistrPlayers AllWeeks Player Rest}
            if Player < NbOfPlayers then 
               {DistrPlayers AllWeeks Player+1 AllWeeks}
            else skip end 
   proc {$ Weeks}
      Weeks = {MakeList NbOfWeeks}
      {ForAll Weeks
       proc {$ Week}
          Week =
           NbOfFourSomes [1#NbOfPlayers]}
          {ForAll Week proc {$ FourSome}
                          {FS.card FourSome 4}
          {FS.partition Week
           {FS.value.make [1#NbOfPlayers]}}
      {ForAllTail Weeks
       proc {$ WTails}
          case WTails
          of Week|RestWeeks then 
             {ForAll Week
              proc {$ FourSome}
                 {ForAll {Flatten RestWeeks}
                  proc {$ RestFourSome}
                     {FS.cardRange 0 1
                       FourSome RestFourSome}}
          else skip end 
      FlattenedWeeks = {Flatten Weeks}
      {DistrPlayers FlattenedWeeks 1 FlattenedWeeks}

Invoking the solver by {ExploreOne {Golf 9 8}} produces the following search tree.

The search tree has a depth of 200 which makes the problem a good candidate for recomputation. Invoking the search engine with a computation depth of one 2 requires 64.1 MB of heap memory. On the other hand an recomputation depth of 10 3 decreases the required heap memory to 19.3 MB.

1. The distribution strategy was proposed by Stefano Novello from IC-PARC on the newsgroup comp.constraints.
2. declare S = {Search.one.depth {Golf 9 8} 1 _}
3. declare S = {Search.one.depth {Golf 9 8} 10 _}

Tobias Müller
Version 1.4.0 (20080702)