How to automatically generate a sports league schedule

Question

I'll start of by saying that I understand that this topic is complicated and that there probably isn't an easy answer. If it were easy then everybody would be doing it. That being said...

I've been asked to build an application to manage a sports league. Most of the concepts are fairly easy to understand except for this one: How to generate a schedule of play where there are no overlaps (team plays 2 teams at once), where a team in a division plays its teams twice but plays teams from the other divisions once, and makes sure that there are no holes in the schedule (each team plays every week)

Right now the process is done manually using a rosetta stone type spreadsheet that I've built to serve this purpose, but it only works for the number of teams it was designed for. I have variations made for 30 teams, 24 teams and 28 teams. Rather than continually attempt to readjust my translation table, I'd like to be able to codify that logic and tweak that process instead.

Thoughts?

Answer 1

There is a pretty straightforward system used in e.g. chess tournaments called round-robin.

The idea is to divide the players to the two sides of a table. One of the players is designated as a "hub" (for a want of a better word). The tournament starts by having players facing each other playing against each other. After the first round everyone but the hub move one chair forward and the white/black (home/away in sports) order is switched. The entire round-robin competition is finished when the players sit in their original places. If you want everyone to play everyone twice just do the same again.

Wikipedia article with implementation details.

In your special case I would try doing the round robin once including all teams. Then you do the same for each division once and to make sure teams within divisions play each other once at home and once away, check from the first round robin what way the teams played in that round.

The down-side of this is, of course, that you will play all inter-division matches well before the tournament finishes (since the last n-1 matches are against intra-division teams [n=number of teams in division]). If this is a problem you could simply swap matches around a bit.

I actually wrote a simple Python script that does this. It didn't take many lines of code and produced pretty good results. This will create a schedule where each team plays each team in their division twice and once against teams in other divisions. There is no check to make sure that the teams meet each other twice in such a way that the same team is at home, however. But this code should give a good idea on how to create your own scheduling code.

#!/usr/bin/python

div1 = ["Lions", "Tigers", "Jaguars", "Cougars"]
div2 = ["Whales", "Sharks", "Piranhas", "Alligators"]
div3 = ["Cubs", "Kittens", "Puppies", "Calfs"]

def create_schedule(list):
    """ Create a schedule for the teams in the list and return it"""
    s = []

    if len(list) % 2 == 1: list = list + ["BYE"]

    for i in range(len(list)-1):

        mid = len(list) / 2
        l1 = list[:mid]
        l2 = list[mid:]
        l2.reverse()    

        # Switch sides after each round
        if(i % 2 == 1):
            s = s + [ zip(l1, l2) ]
        else:
            s = s + [ zip(l2, l1) ]

        list.insert(1, list.pop())

    return s


def main():
    for round in create_schedule(div1):
        for match in round:
            print match[0] + " - " + match[1]
    print
    for round in create_schedule(div2):
        for match in round:
            print match[0] + " - " + match[1]
    print
    for round in create_schedule(div3): 
        for match in round:
            print match[0] + " - " + match[1]
    print
    for round in create_schedule(div1+div2+div3): 
        for match in round:
            print match[0] + " - " + match[1]
        print

if __name__ == "__main__":
    main()

Answer 2

I would just encode these constraints as a boolean formula and use some SAT-solver to obtain solutions (e.g. MiniSAT for C++, SAT4J for Java, and you could even write you own simple solver). The input to these solvers is standartized by DIMACS.

See also "A SAT Encoding for the Social Golfer Problem" and "A SAT Based Scheduler for Tournament Schedules" for SAT-encodings of similar problems.

Answer 3

here's a shot at an implementation

public interface ITeam
{
   bool PlaysOn(DateTime date);
   bool canPlay(ITeam); //returns true if a game between the teams is legal (played once/twice   
                        //already, same different divisions and other applicable rules
}

IEnumerable<ITeam> teams = null; //replace with initialization
IEnumerable<ITeams> reversed = team.Reverse();
IEnumerable<Dates> listOfGameDays = null;//replace with initialization
var count = teams.Count();

foreach(var date in dates)
{
   for(int i = 0;i<count;i++)
   {
      var innerTeams = i % 2 == 0 ? teams : reversed;
      var team = (from t in innerTeams
                  where !t.PlaysOn(date)
                  select t).First();  
      var opp = (from t in teams
                 where !t.PlaysOn(date) && t.CanPlay(team)
                 select t).First();
      SetupGame(team,opp);
   }
} //lot of optimazation possible :)

I've only tested it on paper but for my setup it works. By alternating between starting at the start of the teams list and the end of the list I avoid the situations where the same team would have to play the same team over and over again (or repeatedly play on the same day) in my paper test I represented every possible encounter as a different opponnent but that's basically what the CanPlay method should do. Hope this helps, eventhough it not a complete solution

Answer 4

There are two algorithms, one for odd teams, one for even teams to make sure the round robin happens.

I am going to generate you a graphic if i can.

ODD # of teams

The algorithm is to rotate all the teams clockwise. If we had 5 teams:

1 2 --> 3 1 --> 5 3 --> 4 5 --> 2 4
3 4     5 2     4 1     2 3     1 5
5       4       2       1       3

At this point we have completed one round robin where everyone plays each other once... the next round would again be..

1 2
3 4
5

EVEN # of teams

When we have an even number of teams, you do the same rotation, except you hold team #1 in fixed position and rotate all the other teams around #1 in a clockwise fashion. So, if we had 4 teams..

1 2 --> 1 3 --> 1 4 
3 4     4 2     2 3

This would be one complete round robin... the next match up would be..

1 2 
3 4

Programmatically, There's a few ways you could approach this. Maybe the code posted above does the same thing lol..