compute all possible combinations given some constrains

Question

I am trying to solve this algorithmic problem for a personal project.

1. In this tournament there are 8 players.
2. They play 2vs2
3. Two matches at the same time are played (so that all 8 players are playing)
4. Each player has to play 7 matches playing once (in the same team) with all the others
5. At the end of the tournament each player played 7 matches.
6. The tournament is composed by a total of 14 matches
7. A permutation of the matches does not count as a new tournament. (i.e. the tournament is defined as a set of matches)

This is an example tournament with players A,B,C,D,E,F,G,H:

Match  1 :   A, B  VS  C, D.                                Score = ____ : ____
Match  2 :   E, F  VS  H, G.                                Score = ____ : ____
Match  3 :   C, A  VS  B, D.                                Score = ____ : ____
Match  4 :   E, G  VS  H, F.                                Score = ____ : ____
Match  5 :   A, D  VS  C, B.                                Score = ____ : ____
Match  6 :   H, E  VS  F, G.                                Score = ____ : ____
Match  7 :   E, A  VS  B, F.                                Score = ____ : ____
Match  8 :   C, G  VS  H, D.                                Score = ____ : ____
Match  9 :   A, F  VS  E, B.                                Score = ____ : ____
Match 10 :   H, C  VS  D, G.                                Score = ____ : ____
Match 11 :   A, G  VS  H, B.                                Score = ____ : ____
Match 12 :   C, E  VS  D, F.                                Score = ____ : ____
Match 13 :   H, A  VS  B, G.                                Score = ____ : ____
Match 14 :   C, F  VS  E, D.                                Score = ____ : ____

Note that Match i and Match i+1 are played at the same time if i%2==1

Question:

How many different tournaments are possible? Which are these tournaments?

I tried a sort of brute force approach but it is too slow. Is there any better algorithm?

EDIT:

code is welcome. Especially python

Answer 1

The problem is highly symmetric Let me write it in more compact form

AB CD + EF GH                              
AC BD + EG FH                              
AD BC + EH FG 
AE BF + CG DH
AF BE + CH DG
AG BH + CE DF
AH BG + CF DE

For 8 players, there are 28 possible teams of two people (AB, AC, AD...) and all are present in the table, each exactly once. AB and BA is the same team, I would choose the first form as it is alphabetical order. AB CD and CD AB is the same match, I would choose the first form. AB CD + EF GH and EF GH + AB CD is just permutation of matches, I would choose the first form. Given all this we reduced the problem to filling 21 words into this schema

AB __ + __ __
AC __ + __ __
AD __ + __ __
AE __ + __ __
AF __ + __ __
AG __ + __ __
AH __ + __ __

in such a way, that every row contains all 8 letters, each exactly once. And this can be easily brute forced, it took about 15 seconds to calculate (without writing combinations to the console), the result is 10034775

static bool SolutionIsOK(string[,] matchesTuples)
{
    for (int i = 1; i < 7; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            string a1 = matchesTuples[j, 2];
            string a2 = matchesTuples[i, 2];

            if (a1[0] > a2[0] || a1[0] == a2[0] && a1[1] > a2[1])
            {
                string b1 = matchesTuples[j, 3];
                string b2 = matchesTuples[i, 3];

                int check1 = (1 << (a1[0] - 'A')) |
                             (1 << (a1[1] - 'A')) |
                             (1 << (b1[0] - 'A')) |
                             (1 << (b1[1] - 'A'));
                int check2 = (1 << (a2[0] - 'A')) |
                             (1 << (a2[1] - 'A')) |
                             (1 << (b2[0] - 'A')) |
                             (1 << (b2[1] - 'A'));

                if (check1 == check2) { return false; }
            }
        }
    }
    return true;
}

static void WriteSolution(string[,] matchesTuples)
{
    for (int i = 0; i < 7; ++i)
    {
        Console.WriteLine(matchesTuples[i, 0] + " " + matchesTuples[i, 1] + " + "
            + matchesTuples[i, 2] + " " + matchesTuples[i, 3]);
    }
    Console.WriteLine("------------------------------");
}

static int counter = 0;

static void placeTeam(int level, string[] teams, string[,] matchesTuples, bool[,] presentPlayers)
{
    if (level == teams.Length)
    {
        if (!SolutionIsOK(matchesTuples)) { return; };
        WriteSolution(matchesTuples);
        counter++; // solution found
        return;
    }

    string team = teams[level++];
    for (int i = 0; i < 7; ++i)
    {
        if (presentPlayers[i, team[0] - 'A']
         || presentPlayers[i, team[1] - 'A'])
        {
            continue;
        }
        presentPlayers[i, team[0] - 'A'] = true;
        presentPlayers[i, team[1] - 'A'] = true;

        for (int j = 1; j < 4; ++j)
        {
            if (matchesTuples[i, j] != null) { continue; }
            if (j == 3 && (matchesTuples[i, 2] == null)) { continue; }
            matchesTuples[i, j] = team;

            placeTeam(level, teams, matchesTuples, presentPlayers);

            matchesTuples[i, j] = null;
        }

        presentPlayers[i, team[0] - 'A'] = false;
        presentPlayers[i, team[1] - 'A'] = false;
    }
}

static void Main(string[] args)
{
    string[,] matchesTuples = new string[7, 4]; // AE BF + CG DH 
    bool[,] presentPlayers = new bool[7, 8];  // ABCDEFGH
    string[] teams = new string[28]; // AB, AC, AD, ..., BC, BD, ..., GH

    int i = 0;
    for (char c1 = 'A'; c1 < 'H'; ++c1)
    {
        for (char c2 = c1; ++c2 <= 'H';)
        {
            teams[i] = c1.ToString() + c2;
            if (c1 == 'A')
            {
                matchesTuples[i, 0] = teams[i];
                presentPlayers[i, c1 - 'A'] = true;
                presentPlayers[i, c2 - 'A'] = true;
            }
            ++i;
        }
    }

    placeTeam(7, teams, matchesTuples, presentPlayers);

    Console.WriteLine("Found " + counter);
    Console.ReadKey();
}

the only tricky part is the SolutionIsOK function. It solves the last remaining symmetry that was not addressed. Those two cases are equal:

AC BD + EG FH
AD BC + EH FG


AC BD + EH FG
AD BC + EG FH

because the second match is only permutated. The second match can be permutated only if those matches contain the same 4 people. This case can be detected and we can choose only the case that is alphabetically ordered. And that is exactly what SolutionIsOK does.

Answer 2

You can check constraint satisfaction problem. It is about SAT solver or SMT solver.

Maybe your problem can be defined as CS problem.

Example libraries that can resolve CS problems:

• Z3 Theorem Prover. It is for C++, but also there are wrappers for Java, .Net, Python etc.
• OptaPlanner. Dedicated for Java. I think it's friendly to use. Documentation has comprehensive explanation.
• Choco. Also dedicated for Java. I think it's the simplest. Example usage for solving eight queens puzzle.

I know I give you libraries, not algorithm, but maybe there's no need reinvent the wheel.