Round Robin Tournament Scheduling

Bridge scheduling

JudithF · 13 · 13710

JudithF

  • Newbie
  • *
    • Posts: 2
on: August 12, 2006, 05:31:49 PM
I am in a state of consternation. I have to schedule a bridge tournament consisting of 24 couples playing once a month for seven months (four couples at each site).  It would be great if there were some way to do this without people playing each other very often. I have looked everywhere and yuur site seems to be the only one that even attempts to answer scheduling questions.  Can anybody help me?

Judith


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1140
Reply #1 on: August 14, 2006, 04:48:38 AM
Judith,

Thanks for bringing your tournament question here, as this is an interesting problem.  If I understand correctly your "couples" are permanent bridge parnternships who always play together against another couple.  At the top level the problem is to find a schedule for 24 couples, that I have labelled A to X, and then arrange them in groups of 4, over 6 sites and 7 rounds, in such a way the number of times the same two couples meet is minimised.

Round   Site 1     Site 2     Site 3     Site 4     Site 5     Site 6
  1   (P K C N)  (B R X H)  (T A Q J)  (U G E L)  (M F W O)  (V D S I)
  2   (O H D E)  (P I F T)  (L B C J)  (N G R A)  (V U X M)  (Q S K W)
  3   (G Q M C)  (N H V F)  (O I B K)  (U T R D)  (L X A S)  (J P E W)
  4   (T N O L)  (C D X W)  (A U K F)  (S P R M)  (I J H G)  (V B E Q)
  5   (L K H M)  (X Q I N)  (W V G T)  (F E R C)  (U J O S)  (A P B D)
  6   (C O V A)  (M J N D)  (F S B G)  (R L W I)  (U P H Q)  (X E K T)
  7   (W N B U)  (T S H C)  (R J V K)  (Q L F D)  (O X P G)  (M E I A)


In fact this is the same problem as arranging golf foursomes. So the schedule above could be used for arranging 24 golf players for rounds of 6 social foursomes, or for arranging your 24 bridge couples at 6 sites.  The important property of the schedule is that no two couples meet together more than once, so every couple meets with exactly 21 out of the 23 other couples over the course of the 7 rounds.

Now consider what happens when 4 couples meet at a site, you are free to play as many or as few of the three possible bridge matches as you like.  For example if the four couples at a site are 1,2,3 and 4.  Then you could play upto three mini-rounds from the following list:

Mini-round   Table 1     Table 2
    1       ( 1 vs 2)   ( 3 vs 4)
    2       ( 1 vs 3)   ( 2 vs 4)
    3       ( 1 vs 4)   ( 2 vs 3)


None of these bridge matches can occur again in another main-round since no two of these 4 couples will meet again at the same site.

In the schedule the assignment of groups of 4 couples to sites is purely at random, so some couples will play more than once at a site and others not at all.  I believe it is not possible to have a schedule with the additional property that all couples play at least once at a site.

I hope that's clear.

Ian.

----------------------
Note added August 15th.

The following set of triples contain the couples who never meet in the schedule above.

 (A H W)  (B M T)  (C I U)  (D G K)  (E N S)  (F J X)  (L P V)  (O Q R)

for example H and W are the couples that A never meets. If the schedule is being used for golf, this could be used for a final round of 8 threesomes and would ensure that all possible pairs of players occur exactly once.  The triples could also be used to divide the 24 couples/players into 8 teams of 3, then no matches with couples/players from the same team would be scheduled.
« Last Edit: August 15, 2006, 12:41:23 PM by Ian »


JudithF

  • Newbie
  • *
    • Posts: 2
Reply #2 on: August 14, 2006, 11:22:06 AM

Thank you so much for the bridge scheduling.  I am really grateful and I'm sure it will be helpful.
Yours was the only website I could find that even attempted to solve such problems.
You and the internet are miraculous!
Judith


ZugZug

  • Newbie
  • *
    • Posts: 2
Reply #3 on: August 31, 2009, 06:48:47 PM
I have a very similar problem I have not been able to find the answer for. I have to schedule a round robin bridge tournament consisting of 12 couples (four couples at each site).  The important property of the schedule is that no two couples meet together more than once. I have looked everywhere and your site seems to be the only one that even attempts to answer scheduling questions.  Can anybody help me and how many rounds would we be able to play before those couples would have to meet again?  We are planning on doing 7 rounds if that is possible.

Clint


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1140
Reply #4 on: September 01, 2009, 03:10:52 AM
Please have a read of this thread and also follow the links that it makes.  Unfortunately there are no nice solutions as you have to start repeating pairings as soon as the second round.

For seven rounds you could use something like this:

  10   5  12   7
   3   4   1   2
   6   8   9  11

   2   9  10   7
   3  12   8  11
   4   6   5   1

   1   8   3  10
   2   6  12   5
   4   7   9  11

  12   4   2   8
   1   5  11  10
   7   3   6   9

   9   8   2   5
   1   7  12  11
  10   4   6   3

   5   3   2  11
   6   8   7   1
  10   4  12   9

   2  11   6  10
   5   8   4   7
   9  12   3   1

where most pairs of couples meet twice, 9 pairs meet only once, and 3 pairs meet 3 times.  I think that is about the best that can be done with only 12 couples.
« Last Edit: September 01, 2009, 03:12:26 AM by Ian »


ZugZug

  • Newbie
  • *
    • Posts: 2
Reply #5 on: September 05, 2009, 08:25:32 PM
Is there a way to have play 12 teams (4 teams at 3 different locations) evenly regardless of how many or few rounds we were to play?  Your reply works very well but I am looking for the perfect scenario.  i.e all teams play each other 3 times evenly or whatever.  Thanks again for my earlier solution and quick response!!


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1140
Reply #6 on: September 08, 2009, 03:11:35 AM
Yes, you can indeed have all teams play each other exactly 3 times each.  Here is a solution in 11 rounds that is cyclic, if you look closely you will see that given the first round all other rounds can be generated from it using a few simple rules.

1 2 4 8
3 5 10 11
12 6 7 9

2 3 5 9
4 6 11 1
12 7 8 10

3 4 6 10
5 7 1 2
12 8 9 11

4 5 7 11
6 8 2 3
12 9 10 1

5 6 8 1
7 9 3 4
12 10 11 2

6 7 9 2
8 10 4 5
12 11 1 3

7 8 10 3
9 11 5 6
12 1 2 4

8 9 11 4
10 1 6 7
12 2 3 5

9 10 1 5
11 2 7 8
12 3 4 6

10 11 2 6
1 3 8 9
12 4 5 7

11 1 3 7
2 4 9 10
12 5 6 8


thebaxter2

  • Newbie
  • *
    • Posts: 3
Reply #7 on: October 27, 2009, 09:12:19 PM
Hello, this is wonderful to find such brilliance here! I have a very similar problem to these stated above:

I need to schedule a bridge tournament where
- there are 12 couples (or teams)
- there are 6 rounds
- each couple plays every other couple exactly once

for the first 5 rounds:
    - each round consists of 3 sites; where each site has 4 couples
    - at each site each couple will play 2 of the 4 couples present
for the 6th round:    
    - all 12 couples gather at the same location and finish their remaining game(s)

attached is a more formal description.

I would be so grateful if I could someone had a solution to this, or even that someone could say for sure that this is not possible. Thank you so much for taking the time to look at this.


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1140
Reply #8 on: October 30, 2009, 01:27:58 PM
This is definitely possible as here is a solution that I have just found.

Round     Site  1         Site  2         Site  3
----------------------------------------------------
 1a     (K F) (A B)     (E C) (J L)     (H I) (G D)
 1b     (K B) (A F)     (E L) (J C)     (H D) (G I)

 2a     (K G) (B C)     (A D) (F L)     (I J) (H E)
 2b     (K C) (B G)     (A L) (F D)     (I E) (H J)

 3a     (K H) (C D)     (B E) (G L)     (J F) (I A)
 3b     (K D) (C H)     (B L) (G E)     (J A) (I F)

 4a     (K I) (D E)     (C A) (H L)     (F G) (J B)
 4b     (K E) (D I)     (C L) (H A)     (F B) (J G)

 5a     (K J) (E A)     (D B) (I L)     (G H) (F C)
 5b     (K A) (E J)     (D L) (I B)     (G C) (F H)

 6          (A G) (B H) (C I) (D J) (E F) (K L)


Note all the pairings in round 6 are between couples who have never previously attended the same site together.

May I ask who set the problem?


thebaxter2

  • Newbie
  • *
    • Posts: 3
Reply #9 on: October 30, 2009, 09:06:59 PM
Thank you soooo much, I was very unsuccessful in my programmatic and poor clever algorithmic attempts to solve this. What do you mean by who "set" this?

Baxter


Ian Wakeling

  • Forum Moderator
  • God Member
  • *****
    • Posts: 1140
Reply #10 on: October 31, 2009, 02:32:41 AM
I see now that it must be your own problem, I just thought that you might have seen it somewhere as you had included the scan of the sheet of paper.  The first time I read it, I thought that no solution would exist, so as problems go I like it a lot.

My solution owes a little to the computer, however I have used some combinatorics also, assuming that the schedule has a cyclic nature where the players in the 5 'a' rounds cycle using the following permutations (ABCDE) (FGHIJ) (K) (L). The 'b' round is always generated from the 'a' round by keeping the first couples constant and swapping the other two.  I tried the same approach for 8, 16 & 20 couples and was able to find solutions, so my conjecture would be that a schedule like this is always possible where there are 4n players.

Are you going to use the schedule for a bridge club, or is your interest mainly in constructing computer search algorithms?

Ian.


thebaxter2

  • Newbie
  • *
    • Posts: 3
Reply #11 on: November 01, 2009, 08:09:32 PM
Yes actually, a neighbor wanted to a schedule for a bridge tournament, and since it is not a trivial problem and I was a fresh undergrad student in Computer Science, I was asked. Unfortunately it was a little over my head, I tried many (probably foolish) variations of algorithms and couldnt get it so I had started to attempt a somewhat smart brute force algorithm, which naturally would have taken years, lol.

Well your solution sounds fascinating and indeed worked so again I am thankful to have had your brilliant mind to help me. Thank you again very much. Id love to understand exactly how your algorithm worked.


tourjay

  • Newbie
  • *
    • Posts: 4
Reply #12 on: November 05, 2009, 11:01:15 PM
I set up the questions on 10/31/09.  Thank you very much for the kind answer!

Jay Van Cura