Avoid more than one duplicate opponent

Question

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?

Answer 1

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)
            # copy playerCount and adjust
            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.

Answer 2

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"