Assigning Fields to Matches

I have 8 teams who have to play each other in a round-robin format, therefore 7 rounds, but only have 4 fields. How can I write a script to allocate fields to games in a fair manner so that any one team only plays on the same field as few times, not in succession, as possible.

python

8x8 array filled with fields assigned. Could be done with standard search. Assignement is really 3 fields as last is fixed by the third choice. So you have depth three search tree (choosing 2 of 8 teams, 2 of 6 teams and 2 of 4 teams) for each play.

I suggest a recursive search where allocated matches are represented by a list of lists

F = [
    [(0, 1), (2, 4), (3, 6)],
    [(2, 3), (0, 7)],
    [(4, 5), (1, 6)],
    [(6, 7), (3, 5)]
]

There are 4 rows in this list, each representing a field. Here, F means that in round 0, teams 0 and 1 played in field 0, teams 2 and 3 played in field 1, teams 4, 5 in f. 2, t. 6 and 7 in f. 3.
In round 1, t 2 and 4 played in f. 0, etc.

We suppose by induction that we have a function solve(F) which returns a solution of the allocation problem (an array where all 4 rows have length 7, which means that the 7 rounds have been allocated) which rows start with the same elements as the argument array F. The function solve(F) returns None if there is no such solution.

Now here is the pseudo-code for solve() if we look for solutions where each team plays at most twice in each field

def solve(F):
    n = len(F[0])
    if n == len(F[-1]): # all rows have the same length
        if n == 7: # we have a solution
            return F
        else:
            x = 0
            y = n
    else:
        x = index of first row with length (n - 1)
        y = n - 1
    # we try to add a new element in position F[x][y] and call solve() recursively
    teams = set(range(8))
    remove from teams all teams already in column F[.][y]
    remove from teams all teams which appear in position F[x][y-1] (if y > 0)
    remove from teams all teams which appear twice in row F[x]
    teams = sorted(teams)
    pairs = union of set(row) for row in F
    F[x].append(None)
    for i, a in enumerate(teams):
        for b in teams[i+1:]:
            if (a, b) in pairs:
                continue
            F[x][y] = (a, b)
            rv = solve(F)
            if rv is not None:
                return rv
    del F[x][-1]
    return None

This algorithm can be improved by passing more parameters to solve(). For example the set 'pairs'... or make solve a method of a State class.

Edited 4 Years Ago by Gribouillis