Sommige onopgeloste problemen blijven maar terugkomen. Ken je dat? Zo’n probleem dat eens in de zoveel tijd weer terugkomt in je hoofd. Je kauwt er dan weer een tijdje op, komt een stukje verder, maar echt oplossen doe je het niet. En dan is het weer weg. Om veel later opnieuw op te duiken in je hoofd.

Het was een spelletjesmiddag, lang geleden. We waren met 10 teams. Elk team had zijn eigen spel meegenomen. Het idee was dat elk team elk spel zou spelen. Ik zette zo goed en zo kwaad als het kon een schema in elkaar. Dit schema moest voldoen aan de volgende voorwaarden:

  1. Elk team speelt elke ronde één spel tegen één ander team
  2. Elk team speelt elk spel precies één keer
  3. Elk team speelt nooit meer dan één keer tegen een ander team

Voorwaarde 3 kon natuurlijk sowieso niet helemaal: Een team heeft maar 9 unieke tegenstanders, terwijl er 10 unieke spellen zijn. De ‘oplossing’ hiervoor is voorwaarde 3 alleen te laten gelden voor de eerste 9 rondes. In de 10e ronde spelen de teams dan weer tegen hun tegenstander uit de 1e ronde.

Poging 1: Brute force

Typisch iets om door een computer programma uit te laten zoeken. Dit programma moet een schema teruggeven dat aan de bovenstaande voorwaarden voldoet, zoals onderstaand nog open schema.

Elke kolom is een spel, elke rij een ronde en de ?-? zijn twee teams die tegen elkaar spelen.

Mijn eerste poging om dit probleem op te lossen ging ongeveer zo:

 VUL_SCHEMA(schema S, positie P)
   ALS positie > laatste_positie
      ALS schema = geldig
         Geldig schema gevonden!
      ANDERS 
         Helaas, geen geldig schema
   ANDERS
      HERHAAL aantal_teams keer
         MAAK S+ als een kopie van schema S          
         ZET volgende team neer op plek P in nieuw schema S+
         ZET nieuwe plek P+ als de volgende plek
         VUL_SCHEMA(S+, P+)
      ZET niets op deze plek
      ZET nieuwe plek P+ als de volgende plek
      VUL_SCHEMA(S+, P+)
De eerste 1001 stappen van het algoritme (vertraagd) in actie

Dit programma bleef maar draaien, zonder een uitkomst uit te spugen. Logisch, want dit algoritme checkt alle mogelijke manieren en dat zijn er – hou je vast – 1,8×10208 in totaal.

Poging 2: Brute force, met wat slims

Dat is omdat het nogal dom gebeurt. Zoals je hierboven ziet, is het algoritme veel tijd kwijt met het langslopen van onzinnige schema’s. Terwijl je bij bovenstaande schema’s bij de 2e positie al weet dat dit schema nooit kan lukken (hoe kan team 1 nu tegen team 1 spelen?), wat je ook doet met alle andere posities.

Het is dus veel slimmer om bij elk team dat het schema plaatst, direct al te controleren of het conflicten oplevert met het schema tot nu toe, in plaats van alleen aan het einde.

Mijn tweede poging zag er daarom als volgt uit:

VUL_SCHEMA(schema S, positie P)
    ALS positie > laatste_positie
      ALS schema = geldig
         Geldig schema gevonden!
      ANDERS 
         Helaas, geen geldig schema
    ANDERS
      HERHAAL aantal_teams keer
         MAAK S+ als een kopie van schema S
         ZET volgende team neer op plek P in schema S+
         ZET nieuwe plek P+ als de volgende plek
         ALS schema = geldig
            VUL_SCHEMA(S+, P+)
         ANDERS
            Helaas, schema niet geldig meer
      ZET niets op deze plek
      ZET nieuwe plek P+ als de volgende plek
      VUL_SCHEMA(S+, P+)
De eerste 1002 stappen van het algoritme (vertraagd) in actie

Dit algoritme loopt maximaal 4,4×1055 mogelijkheden langs. Dit getal heeft maar liefst 153 nullen minder dan het vorige algoritme! Dat scheelt enorm, maar dit zijn nog altijd gigantisch veel mogelijkheden, te veel voor een computer om door te rekenen.

Poging 3: Brute force, met nog wat meer slims

Het kan nog eenvoudiger. Het maakt namelijk niet uit of je team 1 tegen team 2 laat spelen of team 2 tegen team 1. In beide gevallen spelen de teams tegen elkaar. In plaats van telkens teams neer te zetten, besloot ik unieke teamcombinaties neer te zetten.

Mijn derde poging zag er daarom als volgt uit:

VUL_SCHEMA(schema S, positie P)
   ALS positie > laatste_positie
      ALS schema = geldig
         Geldig schema gevonden!
      ANDERS 
         Helaas, geen geldig schema
   ANDERS
      HERHAAL voor alle unieke teamcombinaties
         MAAK S+ als een kopie van schema S 
         ZET volgende teamcombinatie neer op plek P in schema S+
         ZET nieuwe plek P+ als de volgende plek
         ALS schema = geldig
            VUL_SCHEMA(S+, P+)
         ANDERS
            Helaas, schema niet geldig meer
      ZET niets op deze plek
      ZET nieuwe plek P+ als de volgende plek
      VUL_SCHEMA(S+, P+)

Dit algoritme loopt maximaal 2,4×1022 mogelijkheden langs. Dat scheelt al een stuk, maar erg veel lijkt het niet uit te halen.

Poging 4: Brute force, met nog meer slims

Zoals je hierboven ziet, is het algoritme vooral erg druk in de laatste rij. Dat is eigenlijk een beetje suf, want al in de 4e rij kun je zien dat het niets meer wordt: er zijn maar 8 van de 10 teams geplaatst.

Daarom besloot ik om niet alleen te controleren of het schema geldig is (of het tot nu toe aan de regels voldoet), maar ook of het schema nog wel geldig kan worden (of het nog wel aan de regels kan gaan voldoen met de plekken die nog opgevuld gaan worden).

Mijn vierde poging zag er daarom als volgt uit: 

VUL_SCHEMA(schema S, positie P)
   ALS positie > laatste_positie
      ALS schema = geldig
         Geldig schema gevonden!
      ANDERS 
         Helaas, geen geldig schema
   ANDERS
      HERHAAL voor alle unieke teamcombinaties
         MAAK S+ als een kopie van schema S 
         ZET volgende teamcombinatie neer op plek P in schema S+
         ZET nieuwe plek P+ als de volgende plek
         ALS het schema nog wat kan worden
            VUL_SCHEMA(S+, P+)
         ANDERS
             Helaas, schema kan niets meer worden 
      ZET niets op deze plek
      ZET nieuwe plek P+ als de volgende plek
      VUL_SCHEMA(S+, P+)
De eerste 1000 stappen van het algoritme (vertraagd) in actie

Poging 5: Smart force

Er was nog een slim trucje uit te halen. Tot nu toe probeerde ik het schema van linksboven naar rechtsonder te vullen. Maar het is veel slimmer om elke keer de plek te proberen te vullen waarbij de minste mogelijkheden zijn.

Dat lijkt misschien juist heel onhandig, maar het heeft juist hetzelfde effect als aanpassingen in de pogingen hiervoor: zorgen dat je zo veel mogelijk mogelijkheden niet hoeft langs te lopen.

Mijn vijfde poging zag er daarom als volgt uit:

 VUL_SCHEMA(schema S, positie P, mogelijkheden M)
   ALS de helft van het schema S is gevuld
      Geldig schema gevonden!
   ANDERS
      HERHAAL voor alle unieke mogelijkheden M van deze positie P
         MAAK S+ als een kopie van schema S          
         ZET volgende mogelijkheid neer op plek P in schema S+
         MAAK M+ als een kopie van mogelijkheden M
         VERWIJDER alle onmogelijkheden uit mogelijkheden M+
         ZOEK naar de plek met de minste mogelijkheden in M+
         ZET nieuwe plek P+ als deze plek
         ALS het schema nog wat kan worden
            VUL_SCHEMA(S+, P+, M+)
         ANDERS
            Helaas, schema kan niets meer worden
Het algoritme (vertraagd) in actie

En jawel! Bijna onmiddellijk (in slechts 168 stappen) spuugde het programmaatje de oplossing uit. Yes!

Het uiteindelijke schema:

En als bonus eentje die ‘mee schuift’:

17 jaar te laat…, maar dan heb je ook wat!

Code beschikbaar op: https://github.com/gkruiger/schedulizer

Wat betreft de GIFjes: Bandicam gebruikt voor het opnemen van de output, Online Video Cutter voor het knippen en bijsnijden van de opnames en EZGIF voor het converteren ervan naar het GIF formaat.