Problem Traveling Tournament

from pycsp3 import *

distances = [
    [0,10,15,34],
    [10,0,22,32],
    [15,22,0,47],
    [34,32,47,0]
]

nTeams = len(distances)
nRounds = len(distances) * 2 - 2
assert nTeams % 2 == 0, "An even number of teams is expected"

# o[i][k] is the opponent (team) of the ith team at the kth round
o = VarArray(size=[nTeams, nRounds], dom=range(nTeams))

print("Array of variable o: ", o)
print("Domain of any variable in o: ", o[0][0].dom)

satisfy(
    # each team must play exactly two times against each other team
    Cardinality(o[i], occurrences={j: 2 for j in range(nTeams) if j != i}) for i in range(nTeams)
);

print(posted())

if solve() is SAT:
    print(values(o))

satisfy(
    # ensuring symmetry of games: if team i plays against j at round k, then team j plays against i at round k
    o[o[i][k]][k] == i for i in range(nTeams) for k in range(nRounds)
);

print(posted(-1))

if solve() is SAT:
    print(values(o))

# h[i][k] is 1 iff the ith team plays at home at the kth round
h = VarArray(size=[nTeams, nRounds], dom={0, 1})

print("Array of variable h: ", h)
print("Domain of any variable in h: ", h[0][0].dom)

satisfy(
    # channeling the arrays o and h
    h[o[i][k]][k] != h[i][k] for i in range(nTeams) for k in range(nRounds)
);

print(posted(-1)[:8])

if solve() is SAT:
    print("Opponents: ", values(o))
    print("Playing at home: ", values(h))

if solve() is SAT:
    for k in range(nRounds):
        matches = [(i,o[i][k].value) for i in range(nTeams) if h[i][k].value == 1]
        print(f"Matches at Round {k}: {matches}")            

satisfy(
   # playing against the same team must be done once at home and once away
   If(
       o[i][k1] == o[i][k2], 
       Then=h[i][k1] != h[i][k2]
   ) for i in range(nTeams) for k1, k2 in combinations(range(nRounds), 2)
);

print(posted()[-10:])

if solve() is SAT:
    for k in range(nRounds):
        matches = [(i,o[i][k].value) for i in range(nTeams) if h[i][k].value == 1]
        print(f"Matches at Round {k}: {matches}")       

It works. It may even that the constraint about a maximal sequence of two successive matches at home or away is respected. However, we need to guarantee it. 

def automaton():
    qi, q01, q02, q03, q11, q12, q13 = states = "q", "q01", "q02", "q03", "q11", "q12", "q13"
    trs = [(qi, 0, q01), (qi, 1, q11), (q01, 0, q02), (q01, 1, q11), 
           (q11, 0, q01), (q11, 1, q12), (q02, 1, q11), (q12, 0, q01)]
    return Automaton(start=qi, transitions=trs, final=states[1:])

A = automaton()

print(A)

satisfy(
    # at most 2 consecutive games at home, or consecutive games away
    h[i] in A for i in range(nTeams)
);

print(posted(-1))

We run the solver.

if solve() is SAT:
    for k in range(nRounds):
        matches = [(i,o[i][k].value) for i in range(nTeams) if h[i][k].value == 1]
        print(f"Matches at Round {k}: {matches}")     

if solve(sols=ALL) is SAT:
    print("Number of solutions: ", n_solutions())

# t[i][k] is the travelled distance by the ith team at the kth round. 
# An additional round is considered for returning at home.
t = VarArray(size=[nTeams, nRounds + 1], dom=distances)

print("Array of variable t: ", t)
print("Domain of any variable in t: ", t[0][0].dom)

def table_end(i):  # traveled distance for the first or last game of the ith team
    return [(1, ANY, 0)] + [(0, j, distances[i][j]) for j in range(nTeams) if j != i]

print(table_end(0))

def table(i):  # traveled distance for the a game that is not the first or last one of the ith team
    return ([(1, 1, ANY, ANY, 0)] +
            [(0, 1, j, ANY, distances[i][j]) for j in range(nTeams) if j != i] +
            [(1, 0, ANY, j, distances[i][j]) for j in range(nTeams) if j != i] +
            [(0, 0, j1, j2, distances[j1][j2]) for j1 in range(nTeams) for j2 in range(nTeams) 
              if different_values(i, j1, j2)])

print(table(0))

satisfy(
    # handling traveling for the first game
    [(h[i][0], o[i][0], t[i][0]) in table_end(i) for i in range(nTeams)],

    # handling traveling for the last game
    [(h[i][-1], o[i][-1], t[i][-1]) in table_end(i) for i in range(nTeams)],

    # handling traveling for two successive games
    [(h[i][k], h[i][k + 1], o[i][k], o[i][k + 1], t[i][k + 1]) in table(i) 
      for i in range(nTeams) for k in range(nRounds - 1)]
);

print(posted(-1,-1))

if solve() is SAT:
    for k in range(nRounds):
        matches = [(i,o[i][k].value) for i in range(nTeams) if h[i][k].value == 1]
        print(f"Matches at Round {k}: {matches}")  
    for i in range(nTeams):
         print(f"Distance traveled by team {i}: {sum(t[i][k].value for k in range(nRounds))}")  
    print(f"Overall traveled distance: {sum(t[i][k].value for i in range(nTeams) for k in range(nRounds))}")

minimize(
    # minimizing summed up traveled distance
    Sum(t)
);

if solve() is OPTIMUM:
    for k in range(nRounds):
        matches = [(i,o[i][k].value) for i in range(nTeams) if h[i][k].value == 1]
        print(f"Matches at Round {k}: {matches}")  
    for i in range(nTeams):
         print(f"Distance traveled by team {i}: {sum(t[i][k].value for k in range(nRounds))}")  
    print(f"Overall traveled distance: {bound()}")

from pycsp3 import *

distances = data
nTeams, nRounds = len(distances), len(distances) * 2 - 2
assert nTeams % 2 == 0, "An even number of teams is expected"
nConsecutiveGames = 2 if variant("a2") else 3  # used in one comment


def table(i):  # this is for the a game that is not the first or last one of the ith team
    return ({(1, 1, ANY, ANY, 0)} |
            {(0, 1, j, ANY, distances[i][j]) for j in range(nTeams) if j != i} |
            {(1, 0, ANY, j, distances[i][j]) for j in range(nTeams) if j != i} |
            {(0, 0, j1, j2, distances[j1][j2]) for j1 in range(nTeams) for j2 in range(nTeams) 
              if different_values(i, j1, j2)})


def table_end(i):  # this is for the first or last game of the ith team
    return {(1, ANY, 0)} | {(0, j, distances[i][j]) for j in range(nTeams) if j != i}


def automaton():
    qi, q01, q02, q03, q11, q12, q13 = states = "q", "q01", "q02", "q03", "q11", "q12", "q13"
    trs = [(qi, 0, q01), (qi, 1, q11), (q01, 0, q02), (q01, 1, q11), 
           (q11, 0, q01), (q11, 1, q12), (q02, 1, q11), (q12, 0, q01)]
    return Automaton(start=qi, transitions=trs, final=states[1:])


# o[i][k] is the opponent (team) of the ith team  at the kth round
o = VarArray(size=[nTeams, nRounds], dom=range(nTeams))

# h[i][k] is 1 iff the ith team plays at home at the kth round
h = VarArray(size=[nTeams, nRounds], dom={0, 1})

# t[i][k] is the travelled distance by the ith team at the kth round (plus an additional round to home)
t = VarArray(size=[nTeams, nRounds + 1], dom=distances)

satisfy(
    # each team must play exactly two times against each other team
    [Cardinality(o[i], occurrences={j: 2 for j in range(nTeams) if j != i}) for i in range(nTeams)],

    # ensuring symmetry of games: if team i plays against j at round k, then team j plays against i at round k
    [o[o[i][k]][k] == i for i in range(nTeams) for k in range(nRounds)],

    # channeling the arrays o and h
    [h[o[i][k]][k] != h[i][k] for i in range(nTeams) for k in range(nRounds)],

    # playing against the same team must be done once at home and once away
    [
        If(
            o[i][k1] == o[i][k2], 
            Then=h[i][k1] != h[i][k2]
        ) for i in range(nTeams) for k1, k2 in combinations(range(nRounds), 2)
    ],

    # at most 'nConsecutiveGames' consecutive games at home, or consecutive games away
    [h[i] in automaton() for i in range(nTeams)],

    # handling travelling for the first game
    [(h[i][0], o[i][0], t[i][0]) in table_end(i) for i in range(nTeams)],

    # handling travelling for the last game
    [(h[i][-1], o[i][-1], t[i][-1]) in table_end(i) for i in range(nTeams)],

    # handling travelling for two successive games
    [(h[i][k], h[i][k + 1], o[i][k], o[i][k + 1], t[i][k + 1]) in table(i) 
      for i in range(nTeams) for k in range(nRounds - 1)]
)

minimize(
    # minimizing summed up travelled distance
    Sum(t)
)