Round-robin tournament scheduling, with teams that may share their home field

Question

I need to implement an algorithm to create schedules for round-robin tournaments (where each team faces each other team exactly once), but with the constraint that up to 2 teams – that may play in different leagues – might share the same field on the same time slot of the week, so they must never be scheduled to play at their home field in the same round of their league schedule.

Simple example:

leagueA = [
  TeamA(plays at **FieldA on Sunday**),
  TeamB(plays at FieldB on Sunday),
  TeamC(plays at FieldA on Saturday),
  TeamD(plays at FieldD on Saturday)
]
leagueB = [
  TeamE(plays at **FieldA on Sunday**),
  TeamF(plays at FieldF on Sunday),
  TeamG(plays at FieldG on Saturday),
  TeamH(plays at FieldF on Saturday)
]

I was thinking of generating the schedule for leagueA with the circle method, alternating home and away teams at each round as described in the linked article, and then to approach the scheduling for leagueB by prefilling the slots for the teams that share the field with teams in the other league somehow, but I'm not sure whether it's the right approach and how to actually implement it in a way that is guaranteed to produce schedules not containing conflicts.

Answer 1

This sounds like a operations research problem. I suggest using a standard hammer for that kind of problem: use a SAT solver or ILP solver. For instance, you might have a boolean variable for each tuple of team/location/time, which is true if that team plays at that location at that time; then use boolean/linear constraints to encode all of the requirements for this to count as a valid solution. Then, use an off-the-shelf SAT solver or ILP solver to search for a solution that meets all of those constraints.