SocialGolfers

CSP medium

The coordinator of a local golf club has come to you with the following problem. In their club, there are 32 social golfers, each of whom play golf once a week, and always in groups of 4. They would like you to come up with a schedule of play for these golfers, to last as many weeks as possible, such that no golfer plays in the same group as any other golfer on more than one occasion. The problem can easily be generalized to that of scheduling $G$ groups of $K$ golfers over at most $W$ weeks, such that no golfer plays in the same group as any other golfer twice (i.e. maximum socialisation is achieved). For the original problem, the values of $G$ and $K$ are respectively 8 and 4. See CSPLib (Problem 10).

A golfer who apparently needs socialization. Image from www.publicdomainpictures.net Social Golfers

To build a CSP (Constraint Satisfaction Problem) model, we need first to import the library PyCSP$^3$:

from pycsp3 import *

Then, we need some data.

nGroups = 3
size = 3
nWeeks = 4
nPlayers = nGroups * size

We start our CSP model by introducing an array $x$ of variables.

# x[w][p] is the group admitting on week w the player p
x = VarArray(size=[nWeeks, nPlayers], dom=range(nGroups))

We can display the structure of the array, as well as the domain of the first variable (note that all variables have the same domain).

print("Array x: ", x)
print("Domain of any variable: ", x[0][0].dom)

Array x:  [
  [x[0][0], x[0][1], x[0][2], x[0][3], x[0][4], x[0][5], x[0][6], x[0][7], x[0][8]]
  [x[1][0], x[1][1], x[1][2], x[1][3], x[1][4], x[1][5], x[1][6], x[1][7], x[1][8]]
  [x[2][0], x[2][1], x[2][2], x[2][3], x[2][4], x[2][5], x[2][6], x[2][7], x[2][8]]
  [x[3][0], x[3][1], x[3][2], x[3][3], x[3][4], x[3][5], x[3][6], x[3][7], x[3][8]]
]
Domain of any variable:  0..2

Concerning the constraints, we have to post a group of constraints Intension by using the structure If: this allows us to avoid having a pair of golfers playing together in two different weeks.

satisfy(
   # ensuring that two players don't meet more than one time
   If(
       x[w1][p1] == x[w1][p2],
       Then=x[w2][p1] != x[w2][p2]
   ) for w1, w2 in combinations(nWeeks, 2) for p1, p2 in combinations(nPlayers, 2)
);

We can display the internal representation of the 8 first posted constraints; this way, although a little bit technical, we can see that the constraints are correctly posted (note that ‘ne’ stands for ‘not equal to’).

print(posted()[:10])

intension(function:imp(eq(x[0][0],x[0][1]),ne(x[1][0],x[1][1])))
intension(function:imp(eq(x[0][0],x[0][2]),ne(x[1][0],x[1][2])))
intension(function:imp(eq(x[0][0],x[0][3]),ne(x[1][0],x[1][3])))
intension(function:imp(eq(x[0][0],x[0][4]),ne(x[1][0],x[1][4])))
intension(function:imp(eq(x[0][0],x[0][5]),ne(x[1][0],x[1][5])))
intension(function:imp(eq(x[0][0],x[0][6]),ne(x[1][0],x[1][6])))
intension(function:imp(eq(x[0][0],x[0][7]),ne(x[1][0],x[1][7])))
intension(function:imp(eq(x[0][0],x[0][8]),ne(x[1][0],x[1][8])))
intension(function:imp(eq(x[0][1],x[0][2]),ne(x[1][1],x[1][2])))
intension(function:imp(eq(x[0][1],x[0][3]),ne(x[1][1],x[1][3])))

Interestingly, by calling the function solve(), we can check that the problem is satisfiable (SAT). We can also display the found solution. Here, we call the function values() that collects the values assigned to a specified list of variables.

if solve() is SAT:
    print(values(x))

[
  [2, 1, 2, 1, 1, 0, 2, 0, 0]
  [2, 1, 0, 0, 2, 0, 1, 2, 1]
  [0, 0, 1, 2, 1, 0, 2, 2, 1]
  [0, 1, 1, 0, 2, 2, 2, 1, 0]
]

We can display the solution in a more readable format:

if solve() is SAT:
    for w in range(nWeeks):
        print("Groups of week ", w , [[p for p in range(nPlayers) if x[w][p].value == g] for g in range(nGroups)])

Groups of week  0 [[5, 7, 8], [1, 3, 4], [0, 2, 6]]
Groups of week  1 [[2, 3, 5], [1, 6, 8], [0, 4, 7]]
Groups of week  2 [[0, 1, 5], [2, 4, 8], [3, 6, 7]]
Groups of week  3 [[0, 3, 8], [1, 2, 7], [4, 5, 6]]

It seems to be a valid solution even if we didn’t impose anything about the size of the groups. Indeed, each group must be of the same size. An open question is: does the group of posted constraints Intension ensure this fact for any data? we are note sure (and didn’t take time to answer this question, sorry). Anyway, to avoid any ambiguity, we can post a group of constraints Cardinality

satisfy(
   # respecting the size of the groups
   Cardinality(x[w], occurrences={i: size for i in range(nGroups)}) for w in range(nWeeks)
);

We can control the last posted constraint:

print(posted(-1)[-1])

cardinality(list:[x[3][0], x[3][1], x[3][2], x[3][3], x[3][4], x[3][5], x[3][6], x[3][7], x[3][8]], values:[0, 1, 2], occurs:[3, 3, 3])

We can run again the solver:

if solve() is SAT:
    for w in range(nWeeks):
        print("Groups of week ", w , [[p for p in range(nPlayers) if x[w][p].value == g] for g in range(nGroups)])

Groups of week  0 [[0, 1, 2], [3, 4, 5], [6, 7, 8]]
Groups of week  1 [[0, 3, 6], [1, 4, 7], [2, 5, 8]]
Groups of week  2 [[0, 5, 7], [1, 3, 8], [2, 4, 6]]
Groups of week  3 [[0, 4, 8], [1, 5, 6], [2, 3, 7]]

Interestingly, we have the guarantee (the proof is let to the reader) of keeping at least one solution (when, of course, the instance is satisfiable), when a matrix variant of the constraint [Lexicographic](/documentation/constraints/Lexicographic) is posted. 

satisfy(
   # tag(symmetry-breaking)
   LexIncreasing(x, matrix=True)
);

We can run again the solver. Here, we just display the array $x$ to see the lexicographic order obtained on both rows and columns.

if solve() is SAT:
    print(values(x))

[
  [0, 0, 0, 1, 1, 1, 2, 2, 2]
  [0, 1, 2, 0, 1, 2, 0, 1, 2]
  [0, 1, 2, 1, 2, 0, 2, 0, 1]
  [0, 1, 2, 2, 0, 1, 1, 2, 0]
]

We can even compute the number of solutions.

if solve(sols=ALL) is SAT:
    print("Number of solutions: ", n_solutions())

Number of solutions:  36

Finally, we give below the model in one piece. Here the data is expected to be given by the user (in a command line).

from pycsp3 import *

nGroups, size, nWeeks = data
nPlayers = nGroups * size

# x[w][p] is the group admitting on week w the player p
x = VarArray(size=[nWeeks, nPlayers], dom=range(nGroups))

satisfy(
   # ensuring that two players don't meet more than one time
   [
       If(
           x[w1][p1] == x[w1][p2],
           Then=x[w2][p1] != x[w2][p2]
       ) for w1, w2 in combinations(nWeeks, 2) for p1, p2 in combinations(nPlayers, 2)
   ],

   # respecting the size of the groups
   [Cardinality(x[w], occurrences={i: size for i in range(nGroups)})
     for w in range(nWeeks)],

   # tag(symmetry-breaking)
   LexIncreasing(x, matrix=True)
)

Problem Social Golfers