Deconflict constrained N team schedule

Question

I am writing a perl program to schedule N number of teams to play each other team once as home team and once as visitor. We use two fields and two time periods. So up to eight teams play in a day. No team can play at the same time on both fields or play twice in the same day. Any team not playing for the day is put on the BYE list.

I have written the code to define all the required games. But when I try to schedule each game and remove it from the array of games to be played, I arrive at conditions where there are no games left that can satisfy the rules for field or time periods in a day. This is most pronounced if I do not shuffle the array of games to be played. Even with 8 teams, I get these conflicts near the end.

What is the logic to deconflict the schedule sequence?

Answer 1

Do not simply create a list of all games and select from that at random: you need an algorithm to create the rounds - the circular method being the "standard" one (see for instance the link in the comment by @David Eisenstat).

Once you created the rounds you still have to define a calendar that will respect the limitation of 4 games per day (and no team playing more than once per day). This is straightforward: if one round fills exactly one or more days, i.e. if you have 8, 16, 24, ... teams, then you simply split each round in the requested number of days. But even if N is not a multiple of 8, there are no problems.

Lets' keep things simple, and consider the case of N = 12, so each round requires one day and a half: on day 1 you select (randomly) 4 of the 6 games of round 1; on day 2 you select the 2 missing games of round 1, and 2 games of round 2, taking care to avoid that the same team plays twice in a day; finally on day 3 you complete round 2, and so on. Can we be sure that we will always able to assign day 2 avoiding the duplication of a team? Yes, we can: when you assign the last two games from round 1, you have 4 teams affected; even if in round 2 there are no games between those 4, you only exclude 4 games from day 2, so you still have 2 games available for placement on that day.

Final notes: as you can see there's no need for a bye list. The only situation to deal with is when N is odd, and it is usually handled by adding a dummy team.

Regarding home vs visitors, you will need to repeat the full calendar a second time. Just note that it is not possible to have every team alternating between home and visitors at each round. For instance with 4 teams you may have TeamA (h) vs TeamB and TeamC (h) vs TeamD; at the second round you may still do TeamD (h) vs TeamA and TeamB (h) vs TeamC; but at the third round TeamA and TeamC must play each other, and both come from a visitor round. And the same hold for TeamB and TeamD, who both come from a home round.