Il problema del campionato - Parte 3 (con un algoritmo originale dell'autore)

Lasciamo quindi da parte tutte le complicate questioni sulla colorazione dei grafi, anche perché non sono poi così utili per affrontare praticamente la questione del calendario di un girone all'italiana. Vediamo invece alcune tecniche che possiamo davvero utilizzare.
Avevo accennato ad un algoritmo che avevo ideato nel 1996, e che sembra in grado di trovare sempre un calendario valido, con l'unica condizione che il numero di squadre sia pari.
L'idea mi venne, dopo una serie di infruttuosi tentativi, pasticciando sulla matrice di cui abbiamo ampiamente parlato nei post precedenti. Ricordo che la matrice viene riempita con numeri che corrispondono al numero della giornata in cui è programmata la partita tra le due squadre corrispondenti alla riga e alla colonna.
Pensai subito, tuttavia, di semplificare la questione trascurando una delle due sezioni triangolari, cioè considerando soltanto la sezione in alto a destra della diagonale principale: i gironi di andata e di ritorno, infatti, sono una la ripetizione dell'altro, per cui è sufficiente programmarne uno per avere automaticamente anche l'altro.
L'algoritmo parte quindi con la matrice vuota, o meglio con degli zeri nelle caselle che dovremo riempire (supponiamo sempre N=4).


A questo punto ha inizio il ciclo principale dell'algoritmo.
Prenderemo, una dopo l'altra, alcune "coppie" formate da una riga e da una colonna della matrice, dove la riga e la colonna corrispondono alla stessa squadra. Per ciascuna di queste coppie, possiamo immaginare di scendere dall'alto verso il basso lunga la colonna, "rimbalzare" sulla diagonale principale, e dirigerci verso destra lungo la riga gemella.
A cosa serve questo "cammino" lungo colonne e righe? Ovvio: a riempire le caselle che troviamo ancora a zero lungo il nostro cammino.
E come eseguire questo riempimento? Per ogni coppia, la prima volta che troviamo una casella da riempire, proviamo a metterci un 1, se lungo il cammino sulla "coppia" non abbiamo trovato che zeri, altrimenti proviamo con il numero successivo all'ultimo trovato prima della casella da riempire: se il numero può starci, nel senso che su nessuna riga o colonna della matrice si creano ripetizioni, e inoltre il numero inserito non era già stato scritto sulla stessa "coppia", allora passiamo alla prossima casella da riempire, altrimenti tentiamo con il numero successivo, e così via. Ovviamente quando arriviamo a N-1, il numero successivo da provare sarà di nuovo 1.
Eseguendo questo procedimento sulla coppia formata dalla prima colonna e dalla prima riga, si ottiene la matrice seguente:



Proseguendo con altre due passate, si ottiene il risultato finale:


Gli incontri della prima giornata saranno quindi A-B e C-D, quelli della seconda A-C e B-D, mentre nella terza e ultima giornata si disputerranno le partite A-D e B-C.



Un altro algoritmo, sicuramente più famoso del mio, in grado di risolvere il problema, è quello cui accennavo nella prima parte di questo ormai estenuante post (pazientate, siamo ormai alla fine!). A inventarlo fu un maestro di scacchi austro-ungarico, Johann Nepomuk Berger.
Prendiamo le nostre N=4 squadre: A, B, C e D, e scriviamole in una tabellina così strutturata:


La prima giornata sarà allora costituita dagli incontri A-B e C-D.
Ora manteniamo fissa la squadra in alto a sinistra, mentre nella colonna "CASA" facciamo scorrere le squadre verso l'alto e nella colonna "TRASFERTA" facciamo scorrere le squadre verso il basso. Le squadre che fuoriescono da una colonna passeranno nell'altra colonna. Otteniamo la tabella seguente, corrispondente alla seconda giornata:


Ripetendo per un'ultima volta lo stesso procedimento di rotazione in senso orario, si ottiene la terza giornata:



Guarda caso, abbiamo ottenuto la stessa programmazione generata dal mio algoritmo.
Provate con un numero maggiore di squadre, ad esempio 6, oppure 8, o anche di più: con ogni probabilità otterrete con i due algoritmi calendari diversi.
Buon divertimento!