Multi-sport tournament organization with 7 teams

You say that each team must play at least once against each of the others? Let's make a little diagram with a diagonal matrix:
The first row and the first column are for numbering the teams.
\ 1 2 3 4 5 6 7
1 *
2 1 *
3 1 2 *
4 1 2 3 *
5 1 2 3 4 *
6 1 2 3 4 5 *
7 1 2 3 4 5 6 *
The asterisk is to show that a team does not play against itself.
We see that there will be 21 games in total. We have 3 fields. So each field will be used 7 times.
And we repeat for each of the 6 sports.
Does that meet your criteria?
We place on each field two teams that are not on another field (at first all fields are free).
And we erase each of the 3 boxes after the games.
We start again as long as there are boxes in the matrix.

hello,

You need more than 6 rounds to achieve this. In 6 rounds, each team won't even have played 6 times, so they won't have faced every other team. Nor have played each sport.

Hello,

Is the goal to find out which matches should be played at each time slot? The problem, of course, has many symmetries since with a renumbering of the teams, one can find another match schedule.

The problem obviously has a solution (in the worst case, we can have only one match played at each time slot from those listed by Pierrot, which means 21 time slots).

If we omit the constraint of the fields, to solve the problem in fewer time slots, I think a greedy algorithm that keeps track of already played matches is sufficient. I assume each match lasts one time slot.

• Played matches = {}
• t = 0
• While |Played matches| != 21
  • Reset available teams = {1, ..., 7}
  • For i = 0 ... 6
    • If i is not available
      • Continue
    • Find an available team j such that neither (i, j) nor (j, i) is in Played matches
    • If j exists:
      • Add (i, j) -and/or (j, i)- to Played matches: the match (i, j) is played at time t
      • Remove i and j from available teams
    • i ++
  • t ++

Once you have decided on the matches, I think you can address the issue of the games associated with each match at a later time.

In any case, it is likely that for this instance a greedy algorithm of the same kind would be sufficient. At worst, your problem can be solved with an ILP (Integer Linear Program) or a CSP (Constraint Satisfaction Program), but this assumes you have some knowledge in operational research (the branch of mathematics that deals with optimization problems).

Good luck

We all agree that it takes more than 6 "rounds" to play all the matches for the 6 sports in question.
This can be seen as a combinatorial analysis problem.
A team cannot play against itself. Team A cannot play against A.
Similarly, there is symmetry. If A plays against B, it is the same as saying that B plays against A.
Therefore, we need to calculate the number of combinations of 2 values among N (here N equals 7).
C(7, 2) is exactly 21 (7!/(5!2!))
We can list these pairs of numbers and ensure that there are no duplicate pairs (or their equivalents).
Depending on the language used, we could have a list of tuples or a 2D array thus providing the pairs.
Here, we are lucky, 21 is exactly divisible by 3. We can go through the list and assign the teams in groups of 3 pairs.
This will make exactly 7 rounds of 3 matches or courts. And we start again for each sport. So in total, 21*6 = 126 matches or 42 complete rounds.
Suppose the number of teams is 8 instead of 7.
The number of combinations will then be C(8, 2) = (8!/(6!2!)) = 28, which does not divide by 3.
We can proceed as with the other list by assigning a pair to each court in groups of 3 pairs.
This will create 27 pairs grouped by 3, hence 9 rounds.
And what do we do with the 28th pair?
We place it on the first court and go back to the beginning of the list but move on to the next sport.
We will virtually have a list of 28*6 (168) pair-matches, so 168/3 = 56 complete rounds.
If the number of sports were 7 instead of 6, we would have a total of 28*7 = 196 pair-matches.
In this case, we would have 65 complete rounds with 3 courts and one round with a single court.

Hello,

I propose this ILP formulation which I hope is complete and correct. We define T_max a priori (for example 24) and check if the solver finds a solution; if not, we increase T_max.

Notations: (I give the domains of definition here; to lighten the notations, I will not repeat them in the sums or the quantifiers of the constraints since they are implicitly always the same):

• i, j: the indices of the teams in {1...7}
• k: the indices of the sports with values in {1...6}
• t: the indices of time with values in {1...T_max}

Decision variables (for each value of i, j, k, t):

• Xijt: teams i and j meet at time t to play sport k, with values in {0, 1}
• Yikt: team i plays sport k at time t, with values in {0, 1}

Objective function:

• min sum_t sum_i sum(i <j) Xijt // Minimize the number of matches (we want to avoid pairs of teams (i, j) meeting multiple times "for fun")

Constraints (linear):

• Xiit = 0 // Team i cannot meet itself
• For all i, for all j != i, for all t: Xijt = Xjit // If i meets j at time t, then team j meets i at time t as well
• For all i, sum_k Yikt <= 1 // Each team i plays at most one sport at time t
• For all i, for all j != i, for all k: Yikt + Yijt >= 2 * Xijt // If i and j meet at time t, then they both practice sport k
• For all t: sum_i sum_(i<j) Xijt <= 3 // At most 3 matches at each time t
• For all i, for all t: sum_k Yikt <= 1 // Each team i plays at most 1 sport at each instant t
• For all i: sum_t sum_k Yikt >= 6 // Each team i plays all 6 sports

Implementation

From a practical point of view, there are many ILP solvers. In Python, for example, scipy provides a function to solve a MILP (thus an ILP), namely scipy.optimize.milp.

There are many other solvers, not just in Python. Among the most well-known, we can notably mention Ilog Cplex (paid), Coin-OR (free equivalent of Cplex) usable in C++ and Java.

Remarks

We can probably make some linear relaxations (for example, saying that the Xijt and/or the Yikt are in [0, 1] instead of {0, 1}) in order to reduce the number of integer variables (which become effectively continuous) and thus significantly speed up the resolution. We hope that by making such a relaxation, we still find an integer solution (if that is not the case, we revert them to the discrete domain). It's worth looking at scipy.optimize.linprog.

Good luck

Here is an example of how to organize this tournament into 24 matches, thus in 8 rounds:

 In round 0, teams 0 and 1 play in game 0. In round 0, teams 2 and 3 play in game 0. In round 0, teams 4 and 5 play in game 0. In round 1, teams 1 and 2 play in game 1. In round 1, teams 3 and 4 play in game 1. In round 1, teams 5 and 6 play in game 1. In round 2, teams 0 and 2 play in game 2. In round 2, teams 1 and 3 play in game 2. In round 2, teams 4 and 6 play in game 2. In round 3, teams 0 and 3 play in game 3. In round 3, teams 1 and 6 play in game 3. In round 3, teams 2 and 5 play in game 3. In round 4, teams 0 and 4 play in game 4. In round 4, teams 1 and 5 play in game 4. In round 4, teams 3 and 6 play in game 4. In round 5, teams 0 and 5 play in game 5. In round 5, teams 1 and 4 play in game 5. In round 5, teams 2 and 6 play in game 5. In round 6, teams 0 and 6 play in game 0. In round 6, teams 2 and 4 play in game 4. In round 6, teams 3 and 5 play in game 5. In round 7, teams 0 and 6 play in game 1. In round 7, teams 2 and 4 play in game 3. In round 7, teams 3 and 5 play in game 2.