Event with 6 games, 24 teams

[MaximeJ]

Hi  

I have to organize an event with 24 teams and six different games:

-4 teams per game.
-6 rounds, so that each team can do all the games without doing a game twice.
-A team can't be with a team she already has been with on another game.

I spent some time on it and I didn't find an appropriate schedule...
I also tried to code my own solution based on a modified sudoku algorithm but it didn't work.

Could someone help me ?

[Ian Wakeling]

Hi Maxime,

I think what you are trying to do will be impossible.  Please have a look at the zipped Excel file that can be found here (look for the paperclip attachment).  The worksheet for 24 players, gives 3 of the 6 rounds of play that you want, simply rename Foursome 1 to Foursome 6 as Game 1 to Game 6, and ignore the fact that the players are divided into two groups, so reassign A1 to A12 to be teams 1 to 12, and B1 to B12 to be teams 13 to 24.  Unfortunately there is no way to complete this schedule to 6 rounds.  But note that the situation is different for 28 teams, as the next worksheet gives a solution for 7 games, 7 rounds and 28 teams.

Incidentally does your modified Sudoku algorithm work for 28?

Ian.

[MaximeJ]

Thanks for taking time to help.

I wasn't sure if it was possible or not and I don't know if we can calculate it with some formulas, but it indeed seems impossible.

With 28 teams, 7 rounds, 7 games my program runs for a very long time, so I guess I'm not doing it the right way but I'm not a professional coder...
However, for 24 teams, 6 rounds, 6 games, here's the output I get if I stop it.

Code: [Select]

-------------------------------------------------
1 2     |3 4    |5 6    |7 8    |9 10   |11 12  |
13 14   |15 16  |17 18  |19 20  |21 22  |23 24  |
-------------------------------------------------
3 5     |1 6    |2 4    |9 11   |7 12   |8 10   |
19 21   |20 23  |22 24  |13 15  |14 17  |16 18  |
-------------------------------------------------
4 6     |2 5    |1 3    |16 21  |18 19  |14 20  |
7 9     |8 11   |10 12  |17 23  |13 24  |15 22  |
-------------------------------------------------
8 12    |7 10   |9 14   |1 4    |2 3    |5 13   |
15 0    |0 0    |0 0    |0 0    |0 0    |0 0    |
-------------------------------------------------
0 0     |0 0    |0 0    |0 0    |0 0    |0 0    |
0 0     |0 0    |0 0    |0 0    |0 0    |0 0    |
-------------------------------------------------
0 0     |0 0    |0 0    |0 0    |0 0    |0 0    |
0 0     |0 0    |0 0    |0 0    |0 0    |0 0    |
-------------------------------------------------
And thanks for for the link, can I ask how did you find these schedules ?

[Ian Wakeling]

I am guessing you are trying an exhaustive search and that your code may be working well.  For 24 teams it looks like you have found that it is impossible to fill more than 3 complete rounds (as I expect).  And for 28 teams, it may well be that the algorithm will take too long to find even the first example.  With problems like this it is often that case that what may seem a small increase, i.e. going from 6 to 7 games, has a huge impact on the number of combinations that need to be enumerated.

The schedules in the Excel file are all combinatorial constructions which use sets of 4 mutually orthogonal Latin squares (MOLS), or in the case of 24 and 40 players incomplete MOLS.  There is some info here.  If 4 orthogonal order 6 squares were to exist, then I could make the 24 team schedule that you are looking for.  However as the Wikipedia link shows the non-existence of these squares was finally proved in 1901.

[MaximeJ]

And for 28 teams, it may well be that the algorithm will take too long to find even the first example.

Same for 24 players, it will probably take too long to find there's no solution so I manually made it stop at the position where it begins to loop for a while.

Anyway, it turns out that the problem wasn't exposed to me the correct way.
In a round, there are 4 teams per game BUT it's divided in two matchs played in parallel.

With the algo, some tweaks, and manual operations, I finally managed to make my schedule with all the constraints.

By the way, there's a mistake in the sheet you linked for 24 players :
in round 3, third combination, A4 meets B7 again (R1 fourth combination)

Thanks again for help and explanations.