So, I was tasked with creating an app that generates the schedule of a doubles tennis tournament (i.e., teams of two) in a way that, by the end of it, everyone would have played against the rest of the players. The trick is every team should change in each round so that not only everyone played against everyone but the teams are not repeated.
I've tried implementing it using greedy search with backtracking, but it just takes too long to find a valid solution, so what I'm asking for is sugerences of an algorithm more efficient that I can use to solve this problem. This are the especifics of the problem:
- There is a multiple of 4 number 'n' of players.
- There is at least n/4 fields to play, so that in each round all players have a match.
- No player can play twice with the same partner, so in each round the teams must change.
No player can play twice against the same opponent. At the end of the tournament, each player must have played against the rest.
The algorithm must search the ideal combination of matchs so it meets the requeriments above.
Any ideas? Thank you in advance.
EDIT 2: It's not possible for 4 players.
- Player 1 & Player 2 vs Player 3 & Player 4
So far so good.
- Player 1 & Player 3 vs Player 2 & Player 4
Player 1 already played against Player 4, not a valid solution. The other possibility:
- Player 1 & Player 4 vs Player 2 & Player 3
Player 1 already played against Player 3, not a valid solution either.
EDIT: It is double tennis, sorry for the misunderstanding. Each player must have played against the rest, but it's not mandatory that each player ended up playing with the rest. Question edited for clarity.