Tournament

team_sat.py

#!/usr/bin/env python3
"""Example of a simple team scheduling problem."""
from ortools.sat.python import cp_model

def main(n):
    # Data.
    num_teams = 2 * n
    num_rounds = n
    num_games = n
    all_teams = range(num_teams)
    all_rounds = range(num_rounds)
    all_games = range(num_games)

    # Creates the model.
    model = cp_model.CpModel()

    # Creates games variables.
    # games[(t, r, g)]: team 't' play on round 'r' the game 'g'.
    games = {}
    for t in all_teams:
        for r in all_rounds:
            for g in all_games:
                games[(t, r, g)] = model.NewBoolVar('team%i_round%i_game%i' % (t, r, g))

    # Each game is assigned to exactly two teams.
    for r in all_rounds:
        for g in all_games:
            tmp_teams = []
            for t in all_teams:
                tmp_teams.append(games[(t, r, g)])
            model.Add(sum(tmp_teams) == 2)

    # Each team plays at most one game per round.
    for t in all_teams:
        for r in all_rounds:
            model.AddExactlyOne(games[(t, r, g)] for g in all_games)

    # Each team plays at most one game against other teams.
    for t1 in all_teams:
        for t2 in range(t1+1, num_teams):
            tmp = []
            for r in all_rounds:
                for g in all_games:
                    b = model.NewBoolVar('b_t%i_t%i_r%i_g%i' % (t1, t2, r, g))
                    model.Add(games[(t1, r, g)] + games[(t2, r, g)] == 2).OnlyEnforceIf(b)
                    model.Add(games[(t1, r, g)] + games[(t2, r, g)] != 2).OnlyEnforceIf(b.Not())
                    tmp.append(b)
            model.AddAtMostOne(tmp)

    # Creates the solver and solve.
    solver = cp_model.CpSolver()
    solver.parameters.linearization_level = 2
    # Enumerate all solutions.
    solver.parameters.enumerate_all_solutions = True

    class TeamsPartialSolutionPrinter(cp_model.CpSolverSolutionCallback):
        """Print intermediate solutions."""
        def __init__(self, games, num_teams, num_rounds, num_games, limit):
            cp_model.CpSolverSolutionCallback.__init__(self)
            self._games = games
            self._num_teams = num_teams
            self._num_rounds = num_rounds
            self._num_games = num_games
            self._solution_count = 0
            self._solution_limit = limit

        def on_solution_callback(self):
            self._solution_count += 1
            print('Solution %i' % self._solution_count)
            for r in range(self._num_rounds):
                print('Round %i' % r)
                for g in range(self._num_games):
                    for t in range(self._num_teams):
                        if self.Value(self._games[(t, r, g)]):
                            print('  Team %i plays game %i' % (t, g))
            if self._solution_count >= self._solution_limit:
                print('Stop search after %i solutions' % self._solution_limit)
                self.StopSearch()

        def solution_count(self):
            return self._solution_count

    # Display the first five solutions.
    solution_limit = 3
    solution_printer = TeamsPartialSolutionPrinter(games, num_teams,
                                                    num_rounds, num_games,
                                                    solution_limit)

    # solve
    solver.Solve(model, solution_printer)

    # Statistics.
    print('\nStatistics')
    print('  - conflicts      : %i' % solver.NumConflicts())
    print('  - branches       : %i' % solver.NumBranches())
    print('  - wall time      : %f s' % solver.WallTime())
    print('  - solutions found: %i' % solution_printer.solution_count())


if __name__ == '__main__':
    main(n=4)

zzz.md

Possible output

$ python -m pip install --user ortools
$ ./team_sat.py
Solution 1
Round 0
  Team 4 plays game 0
  Team 5 plays game 0
  Team 6 plays game 1
  Team 7 plays game 1
  Team 0 plays game 2
  Team 3 plays game 2
  Team 1 plays game 3
  Team 2 plays game 3
Round 1
  Team 4 plays game 0
  Team 6 plays game 0
  Team 3 plays game 1
  Team 5 plays game 1
  Team 1 plays game 2
  Team 7 plays game 2
  Team 0 plays game 3
  Team 2 plays game 3
Round 2
  Team 2 plays game 0
  Team 3 plays game 0
  Team 1 plays game 1
  Team 4 plays game 1
  Team 0 plays game 2
  Team 7 plays game 2
  Team 5 plays game 3
  Team 6 plays game 3
Round 3
  Team 1 plays game 0
  Team 6 plays game 0
  Team 0 plays game 1
  Team 5 plays game 1
  Team 3 plays game 2
  Team 4 plays game 2
  Team 2 plays game 3
  Team 7 plays game 3
Solution 2
Round 0
  Team 0 plays game 0
  Team 2 plays game 0
  Team 4 plays game 1
  Team 6 plays game 1
  Team 5 plays game 2
  Team 7 plays game 2
  Team 1 plays game 3
  Team 3 plays game 3
Round 1
  Team 5 plays game 0
  Team 6 plays game 0
  Team 4 plays game 1
  Team 7 plays game 1
  Team 0 plays game 2
  Team 1 plays game 2
  Team 2 plays game 3
  Team 3 plays game 3
Round 2
  Team 3 plays game 0
  Team 6 plays game 0
  Team 1 plays game 1
  Team 2 plays game 1
  Team 0 plays game 2
  Team 7 plays game 2
  Team 4 plays game 3
  Team 5 plays game 3
Round 3
  Team 1 plays game 0
  Team 6 plays game 0
  Team 0 plays game 1
  Team 5 plays game 1
  Team 3 plays game 2
  Team 4 plays game 2
  Team 2 plays game 3
  Team 7 plays game 3
Solution 3
Round 0
  Team 0 plays game 0
  Team 5 plays game 0
  Team 2 plays game 1
  Team 6 plays game 1
  Team 4 plays game 2
  Team 7 plays game 2
  Team 1 plays game 3
  Team 3 plays game 3
Round 1
  Team 5 plays game 0
  Team 6 plays game 0
  Team 1 plays game 1
  Team 7 plays game 1
  Team 0 plays game 2
  Team 4 plays game 2
  Team 2 plays game 3
  Team 3 plays game 3
Round 2
  Team 3 plays game 0
  Team 6 plays game 0
  Team 2 plays game 1
  Team 5 plays game 1
  Team 0 plays game 2
  Team 7 plays game 2
  Team 1 plays game 3
  Team 4 plays game 3
Round 3
  Team 0 plays game 0
  Team 6 plays game 0
  Team 1 plays game 1
  Team 5 plays game 1
  Team 3 plays game 2
  Team 4 plays game 2
  Team 2 plays game 3
  Team 7 plays game 3
Stop search after 3 solutions

Statistics
  - conflicts      : 57
  - branches       : 1975
  - wall time      : 0.164184 s
  - solutions found: 3