Generate a table that meet conditions (tournament team assignation)

Question

I would like for an activity to generate a table that meet certain conditions as know as:

• There are 16 groups
• There are 8 activities
• There are 8 rounds, during a round a team can only do one activity
• Every group need to do every activity
• Each activity must accommodate 2 group and no more
• We would like a group to never meet the same group again (so the people can see the maximum amount of other people :-) )

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.

Answer 1

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:

1. Teams cannot play themselves.
2. Teams cannot play more than once in the same round.
3. Periods cannot be used/(played on) more than once in the same round.

Typically, the following two minimum constraints are also common (though some obscure variant problems may change these):

4. Teams cannot play in the same period more than once.
5. Teams cannot play the same team more than once.

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:

10. No Byes are allowed (i.e., every team must play every round).
11. #Periods = #Rounds (i.e., a "Square" schedule).
12. #Teams = 2 x #Rounds (i.e., "2x").

Numerically, this compels an additional rule that may also be treated as a pseudo-constraint for programming and logical inferencing purposes:

20. All Periods must be used every round (i.e., no empty Periods).

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;

Answer 2

One (of probably many other) solution :

round\xtvt	1	2	3	4	5	6	7	8
1	AL	BK	CJ	DI	EP	FO	GN	HM
2	PK	AJ	BI	CH	DO	EN	FM	GL
3	OJ	PI	AH	BG	CN	DM	EL	FK
4	NI	OH	PG	AF	BM	CL	DK	EJ
5	BE	DG	LO	JM	FI	HK	CP	AN
6	CD	EF	MN	KL	GH	AB	IJ	OP
7	GM	LN	DF	EO	AK	JP	BH	CI
8	FH	CM	EK	NP	JL	GI	AO	BD

Algo used : [ Draw + Brute + Sudoku ]

Step 0 - setup :

With formula :

M3  : =IF(COUNTIFS($B$3:$I$10,$L3,$B$13:$I$20,M$2)=0,"",COUNTIFS($B$3:$I$10,$L3,$B$13:$I$20,M$2))
V3  : =IF(B3="","",COUNTIF($B$3:$I$10,B3))
AE3 : =COUNTIF($B3:$I3,AE$2)

and drag till end of the table.

Step 1-4 - Use the (previous answer version) paired links :

And map it to "Fill in team pair" table row 1. We'll see that the "xtvt number #" , "xtvt repeat watch" table count will be done automatically. We just have to make sure no paired team is repeated (both, pairing & xtvt done).

By "map it" I mean : key in team pairings in "Fill in team pair" table, and observe the "fill up" in “xtvt repeat watch” table. Once it is full with '1', we are done.

The result (for now) :

Step 5 - Brute force (fill up 2 line)

Noticing the similar gap in "xtvt repeat watch" table, I put AN @ xtvt 8, round5.

Then I put BM @ xtvt 1,round5. But cannot work : coz BM had happened before. So we put BE. Repeat the same for others too : look for similar gap, pair on it. Do the same other pair, we will fill up round5 pairings..

Observe that the “xtvt repeat watch” table is the major attention. The pattern use for round6 is :

Imho, this is a bit brute force, but a less rigorous one. Finishing this step, we’ll get :

Any repeat of xtvt/team, we can see ‘2’ in the “xtvt repeat watch” table. If we get a 2, means the team had already played the xtvt before.

I think by now, we can see the step IS sort of like filling up a coloring book, using thinking steps pretty much similar to Sudoku.

Look for possible

• pair (in “xtvt repeat watch” table)
• feed (the team pairing in "Fill in team pair" table)
• test (after entering the pair, make sure it doesn't trigger '2' in “xtvt repeat watch” table)
• repeat for the next pair (in the same round).

Step 6 - Sudoku-like finishing

As for the last 2 round, it has to be done together. Just fill up both at once, then sort it so that no team repeat on the same round (just like Sudoku). Wrapping it up :

Just to verify, use “Pair repetition chk” table and make sure no repeat team pair.

I thought it was impossible at some point of figuring this out. Glad to share the solution found with all..

Hope it helps.