I have been trying to find a solution both theoretical and practical to my problem but I just can't. The question is you have x players that should play some rounds y of games in groups of 4. Now if a player was in a game with somebody else, he is not allowed to be ever again with that player in the same group. Now the question is give n groups that satisfy this conditions. With n being maximal amount of possible groups.My first approach was to just take a player put him into a group, now for the next player check the array already_played_with_players of the first player for the second player if he's not in add him and add the players he played with to the already_played_with_players array. Proceed so too for the next two players. Then mark these 4 players as in a group and take the next player out of the pool and so on.This is not some educational question, but a real world problem. I would like to organize a game tournament, but so that people meet new people and don't play with the same people again. I already ask multiple people mathematicians, physicians, computer scientist, but the solution was not really evident to anybody. So I was wondering if the problem is NP-complete? I know I would need to find a reduction from another NP-complete problem to my problem to prove that, but I don't even know how to formalize my problem exactly.
Game tournament program, NP complete?
np complete