compute all possible combinations given some constrains

Question

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

In this tournament there are 8 players.
They play 2vs2
Two matches at the same time are played (so that all 8 players are playing)
Each player has to play 7 matches playing once (in the same team) with all the others
At the end of the tournament each player played 7 matches.
The tournament is composed by a total of 14 matches
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

What you are attempting appears to match the requirements of a Duplicate Bridge individual tournament called a Shomate Movement tournament. https://en.wikipedia.org/wiki/Duplicate_bridge_movements#Shomate_Movement — RBarryYoung, Nov 06 '20 at 22:28
Unconstrained, there are `(7!)^7` different tournaments. So with the constraints, it will be something less than that. — RBarryYoung, Nov 06 '20 at 22:38

score 1 · Accepted Answer · answered Nov 07 '20 at 02:58

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.

thanks. I have never used it . I need to understand how to run it :-D — Donbeo, Nov 07 '20 at 12:06

mkczyk · Answer 2 · 2020-11-06T22:25:54.470

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.

compute all possible combinations given some constrains

Question:

EDIT:

2 Answers2