Ligaverwaltung, Teil 3: Spielpläne generieren

2019, 6/2019, Lösungen

Lies diesen Artikel und viele weitere mit einem kostenlosen, einwöchigen Testzugang.

Für die meisten Sportarten gibt es Wettbewerbe in Ligen. Oder zumindest Turniere, die ja meist auch als kleine Liga angesehen werden können mit Spielpaarungen und Tabellen. Jedenfalls gibt eine Verwaltung solcher Ligen jede Menge Stoff für eine Datenbankanwendung – mit Datenmodell, Abfragen, Formularen zur Eingabe der Daten und Berichten, um Spielpläne und Tabellen auszugeben. Im dritten Teil der Artikelreihe entwickeln wir einen Algorithmus, der es uns erlaubt, Spielpläne für Ligen mit beliebig vielen Mannschaften zu generieren.

Beispieldatenbank

Die Beispiele dieses Artikels finden Sie in der Datenbank 1906_Ligaverwaltung.accdb.

Aufgabenstellung

Die Aufgabe lautet: Wir wollen für eine Anzahl von Mannschaften, egal ob 4, 6 oder 18, programmgesteuert einen Spielplan erstellen. Dieser Spielplan soll folgene Bedingungen erfüllen:

  • Jede Mannschaft soll ein Heimspiel gegen jede andere Mannschaft haben. Für die Fußball-Bundesliga bedeutet das beispielsweise: Jede Mannschaft macht 17 Heimspiele plus, resultierend aus den 17 Spielen, in denen die anderen Mannschaften ein Heimspiel gegen diese Mannschaft haben, 17 Auswärtsspiele. Dementsprechend gibt es 2 mal n-1 Spieltage, wobei n der Anzahl der Mannschaften entspricht.
  • Jede Mannschaft soll auch nur genau einmal in einem Heimspiel gegen jede andere Mannschaft spielen.
  • Die Spielpaarungen sind auf Spieltage aufgeteilt, wobei an jedem Spieltag jede Mannschaft einmal spielt.
  • Die Spiele sollen in zwei Runden ausgetragen werden, wobei die Hin- und die Rückrunde identisch zusammengestellt werden – nur mit umgedrehtem Heimrecht. Es reicht also prinzipiell, nur die Hinrunde zu generieren und daraus die Spielpaarungen der Rückrunde abzuleiten.
  • Um es nicht zu einfach zu machen: Jede Mannschaft soll maximal einmal pro Spielrunde (also bezogen auf Hin- und Rückrunde) zwei Heim- oder Auswärtsspiele hintereinander bestreiten. Und das soll auch erst ab dem zweiten Spieltag und bis zum vorletzten Spieltag möglich sein (also keine zwei Heim- oder Auswärtsspiele am ersten und zweiten oder vorletzten und letzten Spieltag).
  • Die Krönung wäre – und so ist es in den echten Spielplänen der Fußballbundesliga -, wenn die Abfolge der Gegner einer jeden Mannschaft ungefährt gleich wäre. Also wenn Mannschaft 1 nacheinander gegen Mannschaft 2, Mannschaft 3 und Mannschaft 4 spielt, dann wird Mannschaft 5 auch irgendwann in dieser Abfolge gegen diese Mannschaften spielen. Das funktioniert natürlich nicht durchgehend, denn wenn man die Abfolge der 17 Spiele der Hinrunde einer Mannschaft auf eine andere Mannschaft übertragen wollte, müsste diese ja gegen sich selbst spielen – und spätestens an dieser Stelle müssten wir die Mannschaft dann austauschen.

Ablauf

Wie könnte das programmatisch ablaufen Man könnte auf verschiedene Arten vorgehen. Die erste Idee ist, zuerst alle Spiele für Mannschaft 1 festzulegen, dann die verbleibenden Spiele für Mannschaft 2 und so weiter.

Wir könnten auch einfach alle Spiele von Spieltag 1 an komplett durchbesetzen, indem wir immer die Mannschaft mit dem kleinsten Index eintragen, die noch verfügbar ist. Am erste Spieltag sieht der Spielplan dann so aus:

1-2
3-4
5-6
...

Am zweiten Spieltag beginnen wir dann wieder mit Mannschaft 1 und suchen die Mannschaft mit dem kleinsten Index, gegen den diese Mannschaft noch nicht gespielt hat – in diesem Fall Mannschaft 3 -, und tauschen das Heimrecht um:

3-1

Dann hätte allerdings Mannschaft 3 direkt an den ersten beiden Spieltagen zwei Heimspiele, was frühestens ab dem zweiten Spieltag möglich sein soll. Mannschaft 1 müsste dann also bei Mannschaft 4 antreten:

4-1

Sie sehen: Es ist nicht einfach. Und das wollen wir gleich auch noch programmieren! Abzusehen ist, dass wir dann irgendwann bei der Ermittlung der Paarungen für die hinteren Spieltage auf das Problem stoßen werden, dass wir je Spieltag nicht mehr ausreichend Spiele zusammenstellen und gleichzeitig alle Bedingungen erfüllen können.

Das heißt, wir können keinen starren Ablauf programmieren, sondern müssen die Möglichkeit der Korrektur vorheriger Spieltage berücksichtigen.

In der Programmierung bekommt man das am besten mit rekursiven Funktionen hin. Das heißt, wir legen ein Spiel an, prüfen, ob wir das nächste Spiel nach anlegen können, und wenn nicht, löschen wir das zuvor angelegte Spiel wieder, um ein anderes Spiel anzulegen. Auf diese Weise arbeiten wir uns durch die Kombinationen, um am Ende einen Spielplan zu erhalten, der alle Bedingungen erfüllt. Gegebenenfalls müssen wir uns dabei bis zurück zum Anfang bewegen.

Alternative: Erst Spiele anlegen, dann auf Spieltage aufteilen

Es gibt allerdings noch andere Herangehensweisen. Eine, die vielleicht etwas anschaulicher ist, sieht so aus: Wir tragen erst einmal alle Paarungen in die Tabelle tblSpielpaarungen ein. Das ist einfach: Wir brauchen ja nur zwei Recordsets mit den Mannschaften der Liga/Spielzeit in zwei verschachtelten Do While-Schleifen zu durchlaufen und darin jeweils die Heim- und die Auswärtsmannschaft in die Felder der Tabelle tblSpielpaarungen einzutragen. Dabei müssen wir nur prüfen, ob die Heim- und die Auswärtsmannschaft identisch sind und in diesem Fall keinen Datensatz anlegen.

Programmierung der Spielplangenerierung

Wir beginnen mit dem Anlegen der Spiele einer Liga. Dazu verwenden wir die Prozedur aus Listing 1. Die Prozedur erwartet die LigaSpieljahrID für die Liga, für deren Mannschaften der Spielplan angelegt werden soll. Wir haben zunächst eine kleine Liga angelegt, die nur vier Mannschaften enthält.

<font color=blue>Public Sub </font>PaarungenAnlegen(lngLigaSpieljahrID<font color=blue> As Long</font>)
     <font color=blue>Dim </font>db<font color=blue> As </font>DAO.Database
     <font color=blue>Dim </font>rstSpielpaarungen<font color=blue> As </font>DAO.Recordset
     <font color=blue>Dim </font>rstHeimmannschaften<font color=blue> As </font>DAO.Recordset
     <font color=blue>Dim </font>rstAuswaertsmannschaften<font color=blue> As </font>DAO.Recordset
     <font color=blue>Set</font> db = CurrentDb
     <font color=blue>Set</font> rstSpielpaarungen = db.OpenRecordset("SELECT * FROM tblSpielpaarungen", dbOpenDynaset)
     <font color=blue>Set</font> rstHeimmannschaften = db.OpenRecordset("SELECT MannschaftID FROM tblLigenSpieljahreMannschaften " _
         & "WHERE LigaSpieljahrID = " & lngLigaSpieljahrID, dbOpenDynaset)
     <font color=blue>Set</font> rstAuswaertsmannschaften = db.OpenRecordset("SELECT MannschaftID FROM tblLigenSpieljahreMannschaften " _
         & "WHERE LigaSpieljahrID = " & lngLigaSpieljahrID, dbOpenDynaset)
     <font color=blue>Do While</font> <font color=blue>Not</font> rstHeimmannschaften.EOF
         <font color=blue>Do While</font> <font color=blue>Not</font> rstAuswaertsmannschaften.EOF
             <font color=blue>If </font><font color=blue>Not</font> rstHeimmannschaften!ID = rstAuswaertsmannschaften!ID<font color=blue> Then</font>
                 rstSpielpaarungen.Add<font color=blue>New</font>
                 rstSpielpaarungen!HeimmannschaftID = rstHeimmannschaften!ID
                 rstSpielpaarungen!AuswaertsmannschaftID = rstAuswaertsmannschaften!ID
                 rstSpielpaarungen.Update
             <font color=blue>End If</font>
             rstAuswaertsmannschaften.Move<font color=blue>Next</font>
         <font color=blue>Loop</font>
         rstAuswaertsmannschaften.MoveFirst
         rstHeimmannschaften.Move<font color=blue>Next</font>
     <font color=blue>Loop</font>
End Sub

Listing 1: Anlegen von Spielpaarungen

Die Prozedur verwendet drei Recordset-Objekte: rstSpielpaarungen liefert die Daten der Tabelle tblSpielpaarungen und rstHeimmannschaften und rstAuswaertsmannschaften jeweils die Daten des Feldes MannschaftID der Tabelle tblLigenSpieljahreMannschaften. Dabei werden die Daten dieser beiden Recordsets nach dem Wert des Parameters lngLigaSpieljahrID gefiltert.

In einer äußeren Schleife durchlaufen wir die Elemente des Recordsets rstHeimmannschaften, in einer inneren die Elemente aus rstAuswaertsmannschaften. Dabei stellen wir den Datensatzzeiger der inneren Schleife immer wieder mit rst.MoveFirst auf den ersten Datensatz zurück, wenn wir alle Auswärtsmannschaften für die aktuelle Heimmannschaft durchlaufen haben. Innerhalb der Schleife prüfen wir dann, ob die aktuelle Heimmannschaft gleich der aktuellen Auswärtsmannschaft ist. In diesem Fall legen wir keine neue Spielpaarung an. Anderenfalls fügt die Prozedur einen neuen Datensatz zum Recordset rstSpielpaarungen hinzu und trägt die jeweiligen IDs für die Felder HeimmannschaftID und AuswaertsmannschaftID ein. Danach sieht die Tabelle tblSpielpaarungen für vier Mannschaften etwa wie in Bild 1 aus.

Spielpaarungen einer Vierer-Liga

Bild 1: Spielpaarungen einer Vierer-Liga

Nun brauchen wir hier nur noch die Spieltage einzutragen. Und das wird eine interessante Aufgabe. Die Grundidee ist: Wir beginnen mit dem ersten Spieltag und suchen uns für diesen Paarungen heraus. Für das erste Spiel am ersten Spieltag kein Problem: Hier können wir einfach das erste Spiel auswählen. Danach wollen wir das erste Spiel aus der Tabelle tblSpielpaarungen suchen, dessen Heimmannschaft und dessen Auswärtsmannschaft nicht am ersten Spiel beteiligt sind. Soweit kein Problem – der erste Spieltag könnte so aussehen:

FC Bayern München - Borussia Dortmund
Eintracht Frankfurt - TSG Hoffenheim 1899

Für den zweiten Spieltag können wir dann eines der verbleibenden Spiele als Startpunkt nehmen, und zwar das nächste verfügbare in der Tabelle. Hier also:

FC Bayern München - Eintracht Frankfurt

Dazu passt dann: 

Borussia Dortmund - TSG Hoffenheim 1899

Damit hat Bayern München allerdings direkt zwei Heimspiele und Hoffenheim gleich zwei Auswärtsspiele. Aber gut, das lässt sich bei einer Vierergruppe nicht vermeiden. Würden wir eine der beiden Paarungen umdrehen, hätten die beiden anderen Mannschaften entweder zweimal zuhause oder auswärts gespielt. Für den dritten Spieltag erhalten wir dann, wenn wir wieder das nächste noch nicht an einen Spieltag vergebene Spiel holen und dann das nächste Spiel mit den übrigen Mannschaften:

Ende des frei verfügbaren Teil. Wenn Du mehr lesen möchtest, hole Dir ...

Testzugang

eine Woche kostenlosen Zugriff auf diesen und mehr als 1.000 weitere Artikel

diesen und alle anderen Artikel mit dem Jahresabo

Schreibe einen Kommentar