Excel VBA function to solve impossible round-robin tournament roster with venue constraint

Question

I am really having difficulty generating a round-robin tournament roster with the following conditions:

• 10 Teams (Teams 1 - 10)
• 5 Fields (Field A - E)
• 9 Rounds (Round 1 - 9)
• Each team must play every other team exactly once.
• Only two teams can play on a field at any one time. (i.e. all 5 fields always in use)
• No team is allowed to play on any particular field more than twice. <- This is the problem!

I have been trying on and off for many years to solve this problem on paper without success. So once and for all, I would like to generate a function in Excel VBA to test every combination to prove it is impossible.

I started creating a very messy piece of code that generates an array using nested if/while loops, but I can already see it's just not going to work.

Is there anyone out there with a juicy piece of code that can solve?

Edit: Thanks to Brian Camire's method below, I've been able to include further desirable constraints and still get a solution:

• No team plays the same field twice in a row
• A team should play on all the fields once before repeating

The solution is below. I should have asked years ago! Thanks again Brian - you are a genius!

 Round     1      2      3      4      5      6      7      8      9
Field A   5v10   1v9    2v4    6v8    3v7    4v10   3v9    7v8    1v2
Field B   1v7    8v10   3v6    2v9    4v5    6v7    1v8    9v10   3v5
Field C   2v6    3v4    1v10   5v7    8v9    1v3    2v5    4v6    7v10
Field D   4v9    2v7    5v8    3v10   1v6    2v8    4v7    1v5    6v9
Field E   3v8    5v6    7v9    1v4    2v10   5v9    6v10   2v3    4v8

Answer 1

I think I've found at least one solution to the problem:

Round    Field    Team 1   Team 2
1        A        3        10
1        B        7        8
1        C        1        9
1        D        2        4
1        E        5        6
2        A        8        10
2        B        1        5
2        C        2        6
2        D        3        7
2        E        4        9
3        A        1        4
3        B        2        3
3        C        8        9
3        D        5        7
3        E        6        10
4        A        6        7
4        B        4        10
4        C        2        8
4        D        5        9
4        E        1        3
5        A        2        9
5        B        3        8
5        C        4        7
5        D        1        6
5        E        5        10
6        A        3        9
6        B        4        5
6        C        7        10
6        D        6        8
6        E        1        2
7        A        5        8
7        B        6        9
7        C        1        10
7        D        3        4
7        E        2        7
8        A        4        6
8        B        2        10
8        C        3        5
8        D        1        8
8        E        7        9
9        A        2        5
9        B        1        7
9        C        3        6
9        D        9        10
9        E        4        8

I found it using the OpenSolver add-in for Excel (as the problem was too large for the built-in Solver feature). The steps were something like this:

1. Set up a table with 2025 rows representing the possible matches -- that is, possible combinations of round, field, and pair of teams (with columns like the table above), plus one extra column that will be a binary (0 or 1) decision variable indicating if the match is to be selected.
2. Set up formulas to use the decision variables to calculate: a) the number matches at each field in each round, b) the number of matches between each pair of teams, c) the number of matches played by each team in each round, and, d) the number of matches played by each team at each field.
3. Set up a formula to use the decision variables to calculate the total number of matches.
4. Use OpenSolver to solve a model whose objective is to maximize the result of the formula from Step 3 by changing the decision variables from Step 1, subject to the constraints that the decision variables must be binary, the results of the formulas from Steps 2.a) through c) must equal 1, and the results of the formulas from Step 2.d) must be less than or equal to 2.

The details are as follows...

For Step 1, I set up my table so that columns A, B, C, and D represented the Round, Field, Team 1, and Team 2, respectively, and column E represented the decision variable. Row 1 contained the column headings, and rows 2 through 2026 each represented one possible match.

For Step 2.a), I set up a vertical list of rounds 1 through 9 in cells I2 through I10, a horizontal list of fields A through E in cells J1 through N1, and a series of formulas to calculate the number of matches in each field in each round in cells J2 through N10 by starting with =SUMIFS($E$2:$E$2026,$A$2:$A$2026,$I2,$B$2:$B$2026,J$1) in cell J2 and then copying and pasting.

For Step 2.b), I set up a vertical list of teams 1 through 9 in cells I13 through I21, a horizontal list of opposing teams 2 through 10 in cells J12 through R12, and a series of formulas to calculate the number of matches between each pair of teams in the "upper right triangular half" of cells J13 through R21 (including the diagonal) by starting with =SUMIFS($E$2:$E$2026,$C$2:$C$2026,$I13,$D$2:$D$2026,J$12) in cell J13 and then copying and pasting.

For Step 2.c), I set up a vertical list of teams 1 through 10 in cells I24 through I33, a horizontal list of rounds 1 through 9 in cells J23 through R23, and a series of formulas to calculate the number of matches played by each team in each round in cells J24 through R33 by starting with =SUMIFS($E$2:$E$2026,$C$2:$C$2026,$I24,$A$2:$A$2026,J$23)+SUMIFS($E$2:$E$2026,$D$2:$D$2026,$I24,$A$2:$A$2026,J$23) in cell J24 and then copying and pasting.

For Step 2.d), I set up a vertical list of teams 1 through 10 in cells I36 through I45, a horizontal list of fields A through B in cells J35 through N45, and series of formulas to calculate the number of matches played by each team at each field in cells J36 through N45 by starting with =SUMIFS($E$2:$E$2026,$C$2:$C$2026,$I36,$B$2:$B$2026,J$35)+SUMIFS($E$2:$E$2026,$D$2:$D$2026,$I36,$B$2:$B$2026,J$35) in cell J36 and then copying and pasting.

For Step 3, I set up a formula to calculate the total number of matches in cell G2 as =SUM($E$2:$E$2026).

For Step 4, in the OpenSolver Model dialog (available from Data, OpenSolver, Model) I set the Objective Cell to $G$2, the Variable Cells to $E$2:$E$2026, and added constraints as described above and detailed below (sorry that the constraints are not listed in the order that I described them):

Note that, for the constraints described in Step 2.b), I needed to add the constraints separately for each row, since OpenSolver raised an error message if the constraints included the blank cells in the "lower left triangular half".

After setting up the model, OpenSolver highlighted the objective, variable, and constraint cells as shown below:

I then solved the problem using OpenSolver (via Data, OpenSolver, Solve). The selected matches are the ones with a 1 in column E. You might get a different solution than I did, as there might be many feasible ones.

Answer 2

come on ... that's an easy one for manual solution ;-)

T1  T2  VE

1   2   A
1   3   A
1   4   B
1   5   B
1   6   C
1   7   C
1   8   D
1   9   D
1   10  E
2   3   A
2   4   B
2   5   B
2   6   C
2   7   C
2   8   D
2   9   D
2   10  E
3   4   C
3   5   C
3   6   D
3   7   D
3   8   E
3   9   E
3   10  B
4   5   C
4   6   D
4   7   D
4   8   E
4   9   E
4   10  A
5   6   E
5   7   E
5   8   A
5   9   A
5   10  D
6   7   E
6   8   A
6   9   A
6   10  B
7   8   B
7   9   B
7   10  A
8   9   B
8   10  C
9   10  C

As far as I have checked no team more then twice on the same venue. Please double check.

To divide it into rounds should be a easy one.

Edit: this time with only 5 venues :-)

Edit 2: now also with allocated rounds :-)

Edit 3: deleted the round allocation again because it was wrong.