Tournament Scheduling Puzzle

Question

I have an interesting real life problem that can be turned into an interesting puzzle pertaining to a tournament that can be represented in this way: I have 24 people which are assigned numbers 1 to 24. A team of them are in groups of three.

ex: (1,2,3) is a team. Obviously, groups such as (1,1,3) are not possible. 4 games can arise from these teams, ex: (1,2,3) vs (4,5,6), (7,8,9) vs (10,11,12), (13,14,15) vs (16,17,18) and (19,20,21) vs (22,23,24).

There will be 4 of these games per round as there are always 8 teams, and 7 rounds in the entire tournament. The problem comes when these restrictions are placed: once 2 people are put on the same team, they cannot be on the same team once more. Ex: if (1,2,3) appears in round 1, (1,8,2) in round 2 cannot appear since 1 and 2 are on the same team.

The second restriction is that people cannot face off against each other more than once. Ex: if (1,2,3) vs (4,5,6) took place, then (1,11,5) vs (4,17,20) cannot because 1 and 4 already faced off against each other.

If there are 4 simultaneous games per round, is it possible to find a unique solution for creating and pairing teams for 7 continuous rounds with these criteria met? I'm not sure if there is a way to find just 1 solution without extensive (or impossible amounts of) computational resources, or if its somehow provable that there are 0 solutions. All I'm looking for is just 1 valid solution for 7 rounds, so in that way it can be seen as a nice (or very challenging in my case) puzzle.

Answer 1

In general, this is just a constraint satisfaction problem and there are usually several ways of solving such problems without using exponential amounts of time/space. Even backtracking works most of the time if you're careful to propagate constraints correctly.

For your tournament in particular:

I encoded your problem as a propositional boolean formula and solved it with a SAT solver. The code I wrote to encode the problem is here. I can solve a 5-round variant to get:

Round 1: (1, 2, 3) vs (4, 5, 6), (7, 8, 9) vs (10, 11, 12), (13, 14, 15) vs (16, 17, 18), (19, 20, 21) vs (22, 23, 24)

Round 2: (1, 4, 13) vs (8, 20, 22), (2, 5, 24) vs (7, 12, 18), (3, 17, 19) vs (9, 16, 21), (6, 10, 14) vs (11, 15, 23)

Round 3: (1, 5, 21) vs (11, 13, 16), (2, 18, 22) vs (9, 17, 23), (3, 12, 20) vs (10, 15, 19), (4, 8, 14) vs (6, 7, 24)

Round 4: (1, 6, 23) vs (12, 17, 24), (2, 7, 14) vs (3, 13, 21), (4, 15, 20) vs (5, 9, 11), (8, 10, 18) vs (16, 19, 22)

Round 5: (1, 10, 20) vs (14, 18, 21), (2, 15, 17) vs (8, 19, 24), (3, 4, 11) vs (12, 13, 23), (5, 7, 16) vs (6, 9, 22)

I could not find solutions for 7 rounds or even 6 within a few days. I played around with some symmetry-breaking constraints to speed up the search a little and the most effective was:

1. The first round is forced to be (1,2,3) vs. (4,5,6), (7,8,9) vs (10,11,12), etc.

2. The first teams are lexicographically ordered throughout rounds, e.g., team 1 is (1,2,3) in round 1, (1,4,22) in round 2, (1,6,8) in round 3, etc.

3. The two teams within each match are lexicographically ordered, e.g., the first match of round 1 is (1,2,3) vs (4,5,6) instead of the other way around

4. All matches within a round are lexicographically ordered by their constituent players, e.g., round 1 is (1,4,22) vs. (7,11,23), (2,5,13) vs. (12,14,21), ... because the tuples of all players within a match are ordered (1,4,7,11,22,23) < (2,5,12,13,14,21)

I could solve a variant of your original puzzle which might be interesting to you since even the 6-round case doesn't seem easily solvable. If you relax your second restriction and allow players to face off at most twice, you can get a 7-round tournament:

Round 1: (1, 2, 3) vs (4, 5, 6), (7, 8, 9) vs (10, 11, 12), (13, 14, 15) vs (16, 17, 18), (19, 20, 21) vs (22, 23, 24)

Round 2: (1, 4, 22) vs (7, 11, 23), (2, 5, 13) vs (12, 14, 21), (3, 16, 19) vs (9, 15, 17), (6, 20, 24) vs (8, 10, 18)

Round 3: (1, 6, 8) vs (13, 18, 23), (2, 15, 20) vs (4, 14, 24), (3, 7, 10) vs (5, 12, 19), (9, 16, 21) vs (11, 17, 22)

Round 4: (1, 7, 15) vs (2, 21, 24), (3, 8, 23) vs (10, 13, 16), (4, 11, 20) vs (6, 17, 19), (5, 14, 18) vs (9, 12, 22)

Round 5: (1, 11, 13) vs (6, 12, 15), (2, 9, 19) vs (10, 21, 22), (3, 4, 17) vs (7, 18, 24), (5, 8, 20) vs (14, 16, 23)

Round 6: (1, 16, 24) vs (18, 19, 22), (2, 4, 7) vs (9, 10, 20), (3, 5, 15) vs (8, 13, 21), (6, 11, 14) vs (12, 17, 23)

Round 7: (1, 21, 23) vs (10, 19, 24), (2, 16, 22) vs (12, 13, 20), (3, 6, 18) vs (7, 14, 17), (4, 8, 15) vs (5, 9, 11)

In fact, even an 8-round tournament is possible with the relaxed constraint.

Answer 2

SAT-solver symmetry breaking

There are 56 total teams of 3. Let's define a "Golden Triple" as a team where all pairs of team members are opponents at some point.

Each player will have 21 total opponents, avoiding only 2 other players as opponents. So, 24 pairs of players are never opponents out of 276 total pairs.

Each pair of players is on no more than one team of 3. So at most 24 teams are not Golden Triples. So, there will always be a round where at 3 or fewer of the teams are not Golden Triples. That round will have at least 5 Golden Triples. So, 3 of the 4 courts of that round will have a Golden Triple.

Let's call that round Round 1.

Round 1: (1, 2, 3) vs (4, 5, 6), (7, 8, 9) vs (10, 11, 12), (13, 14, 15) vs (16, 17, 18), (19, 20, 21) vs (22, 23, 24)

Without loss of generality, we can assume that (1, 2, 3), (7, 8, 9) and (13, 14, 15) are all Golden Triples. But let's just assume (1, 2, 3) is a Golden Triple. Then we know 1vs2, 2vs3, 3vs1 must happen in 3 separate rounds, and {1,2,3} must be on separate courts in the remaining 3 rounds:

Round 2: (1, ?, ?) vs (2, ?, ?), (3, ?, ?) vs (?, ?, ?), ...
Round 3: (2, ?, ?) vs (3, ?, ?), (1, ?, ?) vs (?, ?, ?), ...
Round 4: (3, ?, ?) vs (1, ?, ?), (2, ?, ?) vs (?, ?, ?), ...
Round 5: (1, ?, ?) vs (?, ?, ?), (2, ?, ?) vs (?, ?, ?), (3, ?, ?) vs (?, ?, ?), ...
Round 6: (1, ?, ?) vs (?, ?, ?), (2, ?, ?) vs (?, ?, ?), (3, ?, ?) vs (?, ?, ?), ...
Round 7: (1, ?, ?) vs (?, ?, ?), (2, ?, ?) vs (?, ?, ?), (3, ?, ?) vs (?, ?, ?), ...