I would like for an activity to generate a table that meet certain conditions as know as:
We tried to manually generate this in Excel but there are always some groups that see each other again.
We tried to manually "generate a list" but we always end we teams crossing each other, like team 7 and team 9 cross 3 time in this exemple : table generated so far
I though maybe a thre dimensional array could do , but it seems like an overkill to me and there is certainly some known way to handle those situations.
So, even though @p.phidot has already provided one solution, I went ahead and wrote a program that could solve it as well. I did this primarily because I have seen various versions of this question many times on StackOverflow, with few of them receiving a satisfactory answer.
The problem presented here is one version of the more general Sports League Scheduling problem, of which the Howell and Mitchell movements of Duplicate Bridge tournaments try to address different variants of this problem. It is in fact an obscure type Combinatorial Search problem that has had some work on mathematics and computer science papers over the years(see: 1, 2, and 3 which seems to be taking an approach similar to @p.phidot)
Although there are many variants, the base problem is to arrange ("schedule") some group of things ("teams") in pairs (a "game", "match" or "event") within a rectangular array of a scheduling time (a "round") and a unique resource (a "period", "field", or "boards" in Bridge, or "activity" in the question above). This has to be done within the following common minimum constraints:
Typically, the following two minimum constraints are also common (though some obscure variant problems may change these):
After these almost universal rules, there are a plethora of additional constraints which produce all of the many variants of this problem. The question asked above is what I call the "2x" problem which has the following additional constraints:
Numerically, this compels an additional rule that may also be treated as a pseudo-constraint for programming and logical inferencing purposes:
While it is know that some variants of the general problem are solvable for some sizes, and that others are unsolvable, for the most part, beyond obvious numerical conflicts (like too many teams/not enough periods) each variant is different enough that it is usually unclear which problems can be solved and which cannot. The exception to this is what I call the "Odd Rule", in that if any of the parameters (#Rounds, #Periods, #Teams) is odd, then it is usually solvable by simply rotating the teams and periods by different amounts each round. However, this doesn't work for all even numbers because with simple rotations, either the team's opponents or the periods will duplicate halfway through. This means that when all of the parameters are even, there's no simple combination of rotations that can be used and, if it can be solved it becomes more like a Sudoku puzzle.
So, I wrote this program to solve the version of the problem presented above, using a limited form of the Branch and Bound combinatorial search technique. The good news is that it can solve the specific problem asked by the OP (8 rounds, 8 periods, 16 teams), here is the answer that it gives:
| period\round | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 0 | 0,1 | 3,5 | 2,4 | 6,8 | 7,12 | 10,14 | 9,13 | 11,15 |
| 1 | 3,4 | 0,2 | 1,5 | 7,9 | 6,14 | 8,15 | 11,12 | 10,13 |
| 2 | 2,5 | 1,4 | 0,3 | 12,15 | 8,13 | 7,11 | 6,10 | 9,14 |
| 3 | 6,7 | 8,10 | 9,11 | 0,4 | 1,15 | 3,13 | 2,14 | 5,12 |
| 4 | 8,9 | 6,11 | 7,10 | 13,14 | 0,5 | 1,12 | 4,15 | 2,3 |
| 5 | 10,11 | 12,14 | 13,15 | 1,2 | 3,9 | 0,6 | 5,8 | 4,7 |
| 6 | 12,13 | 9,15 | 8,14 | 3,10 | 2,11 | 4,5 | 0,7 | 1,6 |
| 7 | 14,15 | 7,13 | 6,12 | 5,11 | 4,10 | 2,9 | 1,3 | 0,8 |
(obviously, I have numbered everything from zero)
Now the bad news: Practically, it only works for up to 9 rounds. For 10 rounds and above it basically runs forever (I've let it run for hours without completing). So if someone wants to use it for larger problems, more optimization will need to be applied (Update: For 11 rounds it finished in about a day. For 12 rounds, my estimate is that it would take about a year). Keep in mind though, that odd numbers are always easy to solve manually, no matter how large.
So here's the main solver class (all code is in c#):
class SLSx2Solver
{
public int NumTeams { get; internal set; }
public int NumRounds { get; internal set; }
public int NumPeriods { get; internal set; }
public Schedule State;
public SLSx2Solver(int teams, int rounds, int periods)
{
NumRounds = rounds;
NumPeriods = rounds;
NumTeams = 2 * rounds;
}
public Schedule SolveIt()
{
State = new Schedule(NumTeams, NumRounds, NumPeriods);
// To remove as many solution symmetries as possible before doing
// the BnB search, fully specify the first team's schedule arbitrarily
for (int round = 0; round < NumRounds; round++)
{
State.AddPairing(0, round + 1, round, round);
}
// test all possible assignments for each round, in order
bool solutionWasFound = SolveRemainingRounds(State, 0);
return State;
}
// Try all possible assignments for this round and any remaining rounds.
// Returns true if it was able to find a solution.
internal bool SolveRemainingRounds(Schedule state, int round)
{
// check if all rounds have been finished
if (round >= state.NumRounds)
{
return state.IsSolved;
}
if (state.RoundHasUnassignedTeams(round))
{
if (AssignRemainingPeriods(state, round, 0))
{
return true; // current assignments worked, so cascade it back
}
return false; // current path found no solutions
}
else
{
if(state.RoundIsComplete(round))
{
return SolveRemainingRounds(state, round + 1);
}
return false; // current path found no solutions
}
}
// Test all possible assignments for this period, then all remaining
// periods in the round. Returns true if a solution was found.
internal bool AssignRemainingPeriods(Schedule state, int round, int period) //, List<int> teams = null, int teamIdx = 0)
{
// Is the Round done?
if (state.RoundIsComplete(round))
{
// move to the next round
return SolveRemainingRounds(state, round + 1);
}
// there has to be unassinged teams
List<int> teams = state.RoundUnassignedTeams(round);
if (teams == null || teams.Count == 0)
{
throw new Exception("AssignRemainingPeriods(" + round.ToString() + "): no unassigned teams!");
}
// find the first unassigned Period, starting from (period)
do
{
if (state.RoundPeriod(round, period) == null) break;
period++;
} while (period < state.NumPeriods);
if (period >= state.NumPeriods)
{
throw new Exception("AssignRemainingPeriods(" + round.ToString() + "): no unassigned periods!");
}
// try all combinations of the unassigned teams, in order
for (int teamIdx = 0; teamIdx < teams.Count - 1; teamIdx++)
{
int team1 = teams[teamIdx];
// before we try all team2 combinations, make sure team1
// hasn't already used this period
if (!state.TeamUsedPeriod(team1, period))
{
// try all higher unassigned teams
for (int idx2 = teamIdx + 1; idx2 < teams.Count; idx2++)
{
int team2 = teams[idx2];
if (state.AddPairing(team1, team2, round, period))
{
// assign the next team pair
bool found = AssignRemainingPeriods(state, round, period + 1);
if (found)
{
return true;
}
else
{
// undo the period-assignment
state.UndoPairing(team1, team2, round, period);
}
}
}
}
}
// no complete assignments found on this branch
return false;
}
}
This code implements the brand-and-bound style recursion over a Schedule object that holds and tracks the scheduling assignments in a type of 4-dimensional (Rounds x Periods x Team1 vs Team2) sparse array "Hollow tabulating cube" structure that I find useful for solving types of 8-queens problems (i.e., one occurrence of an object in every dimension). The code for that class is here:
class Schedule
{
// The public-readable attributes (immutable)
public int NumTeams { get; internal set; } // Max 32
public int NumRounds { get; internal set; } // Max 32
public int NumPeriods { get; internal set; }
public Schedule(int teams, int maxRounds, int periods)
{
NumTeams = teams;
NumRounds = maxRounds;
NumPeriods = periods;
// initialize the search-state
// (could make this a 4-dimensional array, but it would be HUGE)
roundXperiod = new Assignment[NumRounds, NumPeriods];
periodXteam = new Assignment[NumPeriods, NumTeams];
roundXteam = new Assignment[NumRounds, NumTeams];
teamXteam = new Assignment[NumTeams, NumTeams];
periodsAssignedCount = new int[NumRounds];
teamsAssignedCount = new int[NumRounds];
// init the moves-log stack
assignments = new Stack<Assignment>((NumTeams + 1 * NumRounds) / 2);
}
#region Internal Assignment-tracking structures
Assignment[,] roundXperiod;
Assignment[,] periodXteam;
Assignment[,] roundXteam;
Assignment[,] teamXteam; // [team1,team2] | team1 < team2
int[] periodsAssignedCount;
int[] teamsAssignedCount;
int roundsComplete;
#endregion
#region State-checking public interface
public bool RoundHasUnassignedTeams(int round)
{
return teamsAssignedCount[round] < NumTeams;
}
public bool RoundIsComplete(int round)
{
if (periodsAssignedCount[round] == NumPeriods
&& teamsAssignedCount[round] == NumTeams)
return true;
else
return false;
}
public bool IsSolved { get { return (roundsComplete == NumRounds); } }
public Assignment RoundPeriod(int round, int period)
{
return roundXperiod[round, period];
}
public bool TeamUsedPeriod(int team, int period)
{
return (periodXteam[period, team] != null);
}
#endregion
#region public List Generation
public List<int> RoundUnassignedTeams(int round)
{
List<int> lst = new List<int>();
for (int t = 0; t < NumTeams; t++)
{
if (roundXteam[round, t] == null)
lst.Add(t);
}
return lst;
}
public List<int> RoundUnassignedPeriods(int round)
{
List<int> lst = new List<int>();
for (int p = 0; p < NumPeriods; p++)
{
if (roundXperiod[round, p] == null)
lst.Add(p);
}
return lst;
}
#endregion
#region Schedule Assignment public interface
public bool AddPairing(int team1, int team2, int round, int period)
{
Assignment move = new Assignment(team1, team2, round, period);
return Push(move);
}
public void UndoPairing(int team1, int team2, int round, int period)
{
// do some validity checking
Assignment move = Peek();
if (move == null
|| move.Team1 != team1
|| move.Round != round
|| move.Team2 != team2
|| move.Period != period
)
throw new Exception("Schedule.UndoPairing: does not match last move!");
Pop();
return;
}
#endregion
#region Schedule-assignment internal implementation
Stack<Assignment> assignments;
// Adds an assignment to the search state, returns false if the
// assignmment was invalid. (All of the delta-logic is here)
bool Push(Assignment evnt)
{
/* Everything needs to be checked first */
// Has team1 already been assigned?
if (roundXteam[evnt.Round, evnt.Team1] != null) return false;
// Has team1 already used this period?
if (periodXteam[evnt.Period, evnt.Team1] != null) return false;
// Is the round-period unassigned?
if (roundXperiod[evnt.Round, evnt.Period] != null) return false;
// Has team2 already used this period?
if (periodXteam[evnt.Period, evnt.Team2] != null) return false;
// Is team2 unassinged for this round?
if (roundXteam[evnt.Round, evnt.Team2] != null) return false;
// Have these two teams already played each other?
if (teamXteam[evnt.Team1, evnt.Team2] != null) return false;
// Add the move to the stack
assignments.Push(evnt);
/* Make all changes to the data-structures */
roundXteam[evnt.Round, evnt.Team1] = evnt;
teamsAssignedCount[evnt.Round]++;
periodXteam[evnt.Period, evnt.Team1] = evnt;
roundXperiod[evnt.Round, evnt.Period] = evnt;
periodsAssignedCount[evnt.Round]++;
roundXteam[evnt.Round, evnt.Team2] = evnt;
teamsAssignedCount[evnt.Round]++;
periodXteam[evnt.Period, evnt.Team2] = evnt;
teamXteam[evnt.Team1, evnt.Team2] = evnt;
if (RoundIsComplete(evnt.Round)) roundsComplete++;
return true;
}
// UnDo whatever the last move (on top of the stack) was
// (this is where all of the state-UnDo logic needs to be)
void Pop()
{
Assignment evnt = assignments.Pop();
/* validate first */
if (roundXteam[evnt.Round, evnt.Team1] == null
|| roundXteam[evnt.Round, evnt.Team1] != evnt)
throw new Exception("Schedule.Pop: teamAssignment[Team1] does not match!");
if (periodXteam[evnt.Period, evnt.Team1] == null
|| periodXteam[evnt.Period, evnt.Team1] != evnt)
throw new Exception("Schedule.Pop: periodTeams[Period,Team1] does not match!");
// Is the round-period matching?
if (roundXperiod[evnt.Round, evnt.Period] == null
|| roundXperiod[evnt.Round, evnt.Period] != evnt)
throw new Exception("Schedule.Pop: periodAssignments does not match!");
if (periodXteam[evnt.Period, evnt.Team2] == null
|| periodXteam[evnt.Period, evnt.Team1] != evnt)
throw new Exception("Schedule.Pop: periodTeams[Period,Team2] does not match!");
if (roundXteam[evnt.Round, evnt.Team2] == null
|| roundXteam[evnt.Round, evnt.Team2] != evnt)
throw new Exception("Schedule.Pop: teamAssignment[Team2] does not match!");
if (teamXteam[evnt.Team1, evnt.Team2] == null
|| teamXteam[evnt.Team1, evnt.Team2] != evnt)
throw new Exception("Schedule.Pop: team1VsTeam2[Team1,Team2] does not match!");
// Implement UnDO
bool wasComplete = RoundIsComplete(evnt.Round);
roundXteam[evnt.Round, evnt.Team1] = null;
teamsAssignedCount[evnt.Round]--;
periodXteam[evnt.Period, evnt.Team1] = null;
roundXperiod[evnt.Round, evnt.Period] = null;
periodsAssignedCount[evnt.Round]--;
periodXteam[evnt.Period, evnt.Team2] = null;
roundXteam[evnt.Round, evnt.Team2] = null;
teamsAssignedCount[evnt.Round]--;
teamXteam[evnt.Team1, evnt.Team2] = null;
if (wasComplete
&& !RoundIsComplete(evnt.Round)) roundsComplete--;
return;
}
Assignment Peek()
{
return assignments.Peek();
}
#endregion
public override string ToString()
{
string str = "P \\ R->";
for (int r = 0; r < NumRounds; r++)
{
str += "\t" + r.ToString();
}
str += "\n";
for (int p = 0; p < NumPeriods; p++)
{
str += p.ToString();
for (int r = 0; r < NumRounds; r++)
{
str += "\t" + ((roundXperiod[r, p]?.PairString)??"");
}
str += "\n";
}
return str;
}
}
Finally, both of the classes above use Assignment objects that encapsulate two teams playing each other in a specific round and period:
public class Assignment
{
// Create a schedule pairing assignment
public Assignment(int team1, int team2, int round, int period)
{
if (team2 == -1 || period == -1)
throw new Exception("Cannot create a Pairing Assingment if team2 or period = -1");
// by convetion, Team1 must always be less than Team2
if (team1 < team2)
{
Team1 = team1;
Team2 = team2;
}
else
{
Team1 = team2;
Team2 = team1;
}
Round = round;
Period = period;
}
public int Team1 { get; internal set; }
public int Team2 { get; internal set; }
public int Round { get; internal set; }
public int Period { get; internal set; }
public string PairString
{
get
{
return Team1.ToString() + "," + Team2.ToString();
}
}
}
Below is some code from my form that illustrates how to use the solver class:
listBox1.Items.Clear();
listBox1.Items.Add(" ... running ...");
SLSx2Solver slv = new SLSx2Solver(rounds);
Schedule sol = slv.SolveIt();
if (!sol.IsSolved)
{
MessageBox.Show("No Solution Found.", "Solution Result:", MessageBoxButtons.OK, MessageBoxIcon.Information);
return;
}
// display the results
listBox1.Items.Clear();
string str = sol.ToString();
foreach(string s in str.Split('\n'))
{
listBox1.Items.Add(s);
}
NumTeams = teams;