# Avoid more than one duplicate opponent

OK, I'm not sure if I can explain this:

• I have 12 players
• I want that each player play 3 times
• Each game is of 3 vs 3 players
• In each game each player plays with 2 different team members (no duplicate team members in the 3 matches)

I want that during the tournament each player avoid having more than one duplicate opponent (or none if possible)

Can you help me?

• Have you tried just writing out a tournament? As each player has only 6 team members and 9 opponents, it seems like it shouldn't be hard. Think of three rounds of two games each, where each player is in one game or the other. The restrictions may get hard, though. – Ross Millikan Jul 25 '13 at 16:31
• @RossMillikan That's what I did... and that was the problem that I found. – Leizar Azariel W. Jul 25 '13 at 16:56
• @RossMillikan: Unless you come up with some better way to decide which matches to take: Yes, they are hard. I chose to implement this with Python and I just counted the number of times it ended up with some combination of matches that fulfill all restrictions, but you can't get 6 matches. It were 3090 failed tries! – Martin Thoma Jul 26 '13 at 7:22
• By "no duplicate team members in the 3 matches", do you mean that (for instance) if my teammates in some match are the two players A and B, then in the next match I can't have teammates A and C, because A is duplicate? – ShreevatsaR Jul 26 '13 at 9:07
• @LeizarAzarielW. What ShreevatsR wants to know is if you mean: a) $\forall t_i, t_j \in \text{List of all 12 teams}: i \neq j \Rightarrow t_i \cap t_j = \emptyset$ or b) $\forall t_i, t_j \in \text{List of all 12 teams}: i \neq j \Rightarrow t_i \neq t_j$. a) Means, once you've played with a guy, you'll not play with him again. b) means, there is never the same team in any match. So a) is much stronger than b) as $a) \Rightarrow b)$. For my solution, I thought you want a). – Martin Thoma Jul 26 '13 at 9:21

## Restrictions

• (I) 12 players
• (II) Each player has to play exactly 3 times
• (III) Each game is of 3 vs 3 players
• (IV) In each game each player plays with 2 different team members (no duplicate team members in the 3 matches). So: $\forall t_i, t_j \in \text{List of all 12 teams}: i \neq j \Rightarrow t_i \cap t_j = \emptyset$
• (V) Every player plays at most 1 time more than once against the same opponent player
• (VI) No player plays against himself

## Some thoughts first:

• (VII) You need exactly $\underbrace{12}_{(I)} \cdot \frac{\overbrace{3}^{(II)}}{\underbrace{6}_{(III)}} = \frac{36}{6} = 6$ matches

• (I), (III) and (VI) $\Rightarrow$ There are $\binom{12}{3} \cdot \binom{9}{3} = 220 \cdot 84 = 18480$ possbile matches

• (VII) and above $\Rightarrow$ There are $\binom{18480}{6} = 55274746326873815880600 \approx 5.5 \cdot 10^{22}$ possible games
• $\Rightarrow$ numbers are way too big to brute force. But maybe we can use (IV), (V) to reduce numbers.

## Code

If you relax (V) to twice I found a solution with the following script:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def existsDuplicateTeamMember(games, team):
for i in range(3):
for j in range(i+1,3):
for game in games:
if (team[i] in game[0] and team[j] in game[0]) or \
(team[i] in game[1] and team[j] in game[1]):
return True
return False

def isMaximumGamesReached(playerCount, team):
for player in team:
if playerCount[player] >= 3:
return True
return False

def isConditionBroken(games, playerCount, team):
return isMaximumGamesReached(playerCount, team) or \
existsDuplicateTeamMember(games, team)

def willGetDuplicateOpponents(opponents, team1, team2):
for player in team1:
newDuplicates = 0
for opponent in team2:
if opponents[player][opponent] >= 1:
newDuplicates += 1
if sum(map(lambda k: k-1,filter(lambda k: k>1, opponents[player].values()))) + newDuplicates > 1:
return True
for player in team2:
newDuplicates = 0
for opponent in team1:
if opponents[player][opponent] >= 1:
newDuplicates += 1
if sum(map(lambda k: k-1,filter(lambda k: k>1, opponents[player].values()))) + newDuplicates > 1:
return True
return False

def updateDuplicateOpponents(opponents, team1, team2):
for player in team1:
newDuplicates = 0
for opponent in team2:
opponents[player][opponent] += 1
for player in team2:
newDuplicates = 0
for opponent in team1:
opponents[player][opponent] += 1
return opponents

def printGamesNice(games):
for game in games:
print(str(game[0]) + " vs. " + str(game[1]))

def printNiceOpponentMatrix(players, opponents):
line = "  "
for player in players:
line += player + " "
line += "| Duplicates"
print(line)

for player1 in players:
line = player1 + " "
for player2 in players:
line += str(opponents[player1][player2]) + " "
line += "|" + str(sum(map(lambda k: k-1,filter(lambda k: k>1, opponents[player1].values()))))
print line

def game(players, playerCount, opponents, games = []):
from itertools import combinations
from collections import defaultdict
from copy import deepcopy
if playerCount == None:
playerCount = defaultdict(int)

if opponents == None:
opponents = {}
for player1 in players:
opponents[player1] = {}
for player2 in players:
opponents[player1][player2] = 0

for team1 in combinations(players, 3):
if isConditionBroken(games, playerCount, team1):
continue

for team2 in combinations(players, 3):
if isConditionBroken(games, playerCount, team1):
continue
if isConditionBroken(games, playerCount, team2):
continue
if willGetDuplicateOpponents(opponents, team1, team2):
continue
# A player should not be forced to play against
# himself
if len(set(team1).intersection(set(team2))) > 0:
continue

# copy current matches and add new match
gameCopy = deepcopy(games)
gameCopy.append([team1, team2])
# copy oppenents and adjust that
opponentsCopy = deepcopy(opponents)
opponentsCopy = updateDuplicateOpponents(opponentsCopy, team1, team2)
playerCountCopy = deepcopy(playerCount)
for player in (team1+team2):
playerCountCopy[player] += 1
# descend in depth-first-search tree
returned = game(players, playerCountCopy, opponentsCopy, gameCopy)
if returned != None:
return returned
continue

if len(games) == 5:
printGamesNice(games)
print("#"*20)

if len(games) == 6:
printNiceOpponentMatrix(players, opponents)
return games
else:
return None

if __name__ == "__main__":
players = map(chr, range(65, 65+12))
games = game(players, None, None)
printGamesNice(games)


## Ideas in the code

Well ... pretty straight forward. You basically try every combination. It's implemented as a depth-first-search.

I make use of itertools.combinations, set and defaultdict. I love Python ♥

## Solution

  A B C D E F G H I J K L | Duplicates
A 0 1 1 1 2 2 0 1 0 1 0 0 |2
B 1 0 0 2 1 1 2 0 0 1 0 1 |2
C 1 0 0 1 2 1 0 0 2 1 1 0 |2
D 1 2 1 0 1 0 1 1 0 1 0 1 |1
E 2 1 2 1 0 1 1 0 0 1 0 0 |2
F 2 1 1 0 1 0 1 1 1 0 1 0 |1
G 0 2 0 1 1 1 0 1 1 0 1 1 |1
H 1 0 0 1 0 1 1 0 2 1 1 1 |1
I 0 0 2 0 0 1 1 2 0 1 1 1 |2
J 1 1 1 1 1 0 0 1 1 0 1 1 |0
K 0 0 1 0 0 1 1 1 1 1 0 3 |2
L 0 1 0 1 0 0 1 1 1 1 3 0 |2
('A', 'B', 'C') vs. ('D', 'E', 'F')
('A', 'D', 'G') vs. ('B', 'E', 'H')
('A', 'E', 'I') vs. ('C', 'F', 'J')
('B', 'D', 'K') vs. ('G', 'J', 'L')
('C', 'H', 'L') vs. ('I', 'J', 'K')
('F', 'I', 'L') vs. ('G', 'H', 'K')


At least there are at maximum two duplicate opponents. My script currently tries to find a solution with at most one duplicate opponent. It checks all combinations in alphabetical order. Currently it checked:

1. ('A', 'B', 'C') vs. ('D', 'E', 'F')
2. ('A', 'D', 'G') vs. ('B', 'E', 'H')
3. ('A', 'F', 'J') vs. ('C', 'G', 'I')
4. ('H', 'I', 'J') vs. ('B', 'K', 'L')
5. ('F', 'H', 'L') vs. ('E', 'J', 'K')


I guess as soon as the 3. match gets 'B' in the first position we can be sure that there is no possibility to avoid more than one duplicate opponent.

edit:

The script just checked:

('A', 'B', 'C') vs. ('D', 'E', 'F')
('A', 'D', 'G') vs. ('B', 'E', 'H')
('B', 'D', 'I') vs. ('J', 'K', 'L')
('A', 'I', 'L') vs. ('C', 'G', 'J')
('F', 'H', 'K') vs. ('C', 'E', 'L')


after some hours of execution. So I guess (no proof :-( ) there is no way to get a solution with only one duplicate opponent.

• While this didn't lead to an optimal answer, it definitely deserves more up-votes – jameselmore Jul 26 '13 at 21:34

Here's a near-solution using the Z3 SMT solver.

We represent our search space as a $12 \times 3 \times 2 \times 2$ array of 1's and 0's. $X[p][r][g][t] = 1$ if player $p$ is on team $t$ of game $g$ in round $r$, and otherwise equals $0$. We then require the following constraints:

• Each player plays once per round.
• Each team has exactly three players.
• No two players play together (on the same team) more than once.

We'd like to also satisfy:

• Each player has at least eight distinct opponents.

But I've had the solver running for a while with that constraint and haven't gotten a solution back yet. So we settle for:

• Each player has at least seven distinct opponents.
• No two players play against each other more than twice.

Which gives this solution:

• Round 0, game 0: [1, 9, 10] vs. [0, 4, 6]
• Round 0, game 1: [2, 3, 8] vs. [5, 7, 11]
• Round 1, game 0: [0, 7, 10] vs. [2, 5, 6]
• Round 1, game 1: [8, 9, 11] vs. [1, 3, 4]
• Round 2, game 0: [4, 5, 9] vs. [1, 2, 7]
• Round 2, game 1: [6, 8, 10] vs. [0, 3, 11]

Here's the source code:

from z3 import *

X = [ [ [ [ Int("x_%s_%s_%s_%s" % (p,r,g,t))
for t in range(2) ]
for g in range(2) ]
for r in range(3) ]
for p in range(12) ]

# Each cell is 0 or 1
bits_c = [ Or(X[p][r][g][t] == 0, X[p][r][g][t] == 1)
for t in range(2)
for g in range(2)
for r in range(3)
for p in range(12) ]

# Each player plays once per round.
distinct_c = [ Sum([ X[p][r][g][t]
for t in range(2) for g in range(2) ]) == 1
for r in range(3) for p in range(12) ]

# Each team has three players.
teamsize_c = [ Sum([ X[p][r][g][t]
for p in range(12) ]) == 3
for g in range(2)
for r in range(3)
for t in range(2) ]

# No two players play together more than once.
teammates_c = [ Sum( [X[p][r][g][t] * X[q][r][g][t]
for t in range(2)
for g in range(2)
for r in range(3)]) <= 1
for p in range(12)
for q in range(p) ]

# No two players play against each other more than twice.
opponents2_c = [ Sum( [X[p][r][g][0] * X[q][r][g][1] +
X[p][r][g][1] * X[q][r][g][0]
for g in range(2)
for r in range(3)]) <= 2
for p in range(12)
for q in range(p) ]

# Each player has at least seven opponents.
opponents7_c = [ Sum( [ If(X[p][0][0][0] * X[q][0][0][1] +
X[p][0][0][1] * X[q][0][0][0] +
X[p][0][1][0] * X[q][0][1][1] +
X[p][0][1][1] * X[q][0][1][0] +
X[p][1][0][0] * X[q][1][0][1] +
X[p][1][0][1] * X[q][1][0][0] +
X[p][1][1][0] * X[q][1][1][1] +
X[p][1][1][1] * X[q][1][1][0] +
X[p][2][0][0] * X[q][2][0][1] +
X[p][2][0][1] * X[q][2][0][0] +
X[p][2][1][0] * X[q][2][1][1] +
X[p][2][1][1] * X[q][2][1][0] > 0,
1, 0) for q in range(12)]) >= 7
for p in range(12) ]

s = Solver()
s.add(bits_c + distinct_c + teamsize_c +
teammates_c + opponents2_c + opponents7_c)
if s.check() == sat:
m = s.model()
r = [ [ p for p in range(12)
if str(m.evaluate(X[p][r][g][t])) == "1" ]
for r in range(3)
for g in range(2)
for t in range(2)
]
print_matrix(r)
else:
print "no solution"