Il problema del campionato - Parte 1

Ricordo, come fosse ieri, una mattina negli ultimi mesi del 1982: avevo 11 anni ed ero a casa da scuola con l'influenza. Suonò il campanello: era il postino, con un pacco da consegnare. Scese la mamma a prenderlo, e poi me lo portò. Era il mitico "Almanacco illustrato del calcio", che mi ero conquistato grazie ai "buoni" raccolti con le ancor più mitiche figurine Panini.
Se il concetto di felicità può essere associato ad alcuni particolari giorni della vita, quel giorno fu uno di questi. Ricordo la gioia con cui sfogliai avidamente le pagine, navigando tra campionati d'anteguerra, statistiche, schede dei calciatori, e l'esaltante copertina in cui campeggiava il compianto Enzo Bearzot che alzava al cielo la coppa del mondo appena vinta.
Ora del calcio non mi interessa più nulla, ma allora lo seguivo con entusiasmo (in particolare il Verona, che tre anni dopo avrebbe vinto lo scudetto), e certo uno degli aspetti che mi divertivano maggiormente era il lato statistico, combinatorio dei campionati: insomma mi incuriosiva scoprire come, all'interno di un campionato (ad esempio una stagione di campionato italiano di serie A), si succedessero le giornate, ciascuna costituita da un insieme di partite che, ovviamente, non potevano ripetersi nello stesso torneo, salve le ripetizioni nel girone di ritorno.
Mi sovviene ora un altro ricordo: con un amichetto vicino di casa, compagno di innumerevoli partite a pallone nei cortili di casa, ci eravamo ad un certo punto cimentati nello stilare il calendario di un nostro immaginario campionato. Le partite programmate, poi, le disputavamo noi due e altri amici, non virtualmente ma davvero, nel cortile, con le felpe ammonticchiate a fare da pali per le porte.
Precursori del fantacalcio? Può darsi, ma certamente potete immaginare le difficoltà che due ragazzini di 11 anni potevano trovare nel risolvere a mano, senza computer (era il 1982) e senza sofisticate cognizioni algoritmiche (avevamo 11 anni) un problema complicato come quello della creazione del calendario di un campionato con un numero di squadre non banale.

Naturalmente avevamo inconsapevolmente adottato un approccio che potrei definire di "backtracking": provavamo cioè a stilare, una dopo l'altra, le giornate di campionato, finché incontravamo un ostacolo insormontabile, vale a dire finché ci accorgevamo che le ultime due squadre non ancora accoppiate in una certa giornata si erano già incontrate in una giornata precedente. Allora dovevamo tornare indietro ("backtrack", appunto), ovviamente non si sa bene quanto indietro, e cambiare qualcosa nella speranza di non incontrare più ostacoli del genere.
Non ricordo, francamente, se fossimo a un certo punto riusciti ad arrivare in fondo nella titanica impresa di stilare un calendario completo: mi pare di no (con un numero di squadre realistico, diciamo 16, e con un approccio naif come quello descritto sarebbe stato, credo, quasi impossibile).
Ma mi pare di ricordare di aver escogitato, stremato dai tentativi infruttuosi, un volgare barbatrucco per aggirare l'ostacolo. Avevo preso un calendario reale, ad esempio quello del campionato di serie A in corso, che immaginavo generato da chissà quali fumanti elucubrazioni di fantascientifici cervelloni elettronici; tanto per confondere un po' le acque, l'avevo sottoposto ad una permutazione casuale delle giornate, e infine avevo fatto corrispondere ciascuna squadra del campionato reale con una squadra del nostro campionato immaginario. In questo modo avevo ottenuto un calendario, per le nostre partite in cortile, apparentemente nuovo, ma che in realtà celava la stessa struttura combinatoria di quello reale preso come modello. Furbizie da undicenni.

Il problema del calendario del campionato mi rimase sempre caro, a maggior ragione negli anni successivi quando cominciai a conoscere il mondo dell'informatica e degli algoritmi.
Nei primi anni Novanta scrissi vari programmi in Pascal che affrontavano il problema per via euristica o di backtracking (insomma, per tentativi).
Nel 1996 trovai un algoritmo esatto, cioè che trovava sempre una soluzione ammissibile non per tentativi, ma seguendo una propria logica diretta e andando dritto al risultato. Conservo il codice Pascal di quell'idea, e tornerò sull'argomento.

Per la verità, pare che esista un algoritmo molto vecchio in grado di risolvere il problema (io appresi di ciò piuttosto tardi), e che venne escogitato da uno scacchista austriaco, Johann Berger, vissuto tra il 1845 e il 1933.
Nelle prossime parti di questo "multi-post" toccherò anche questo argomento.
Vi lascio con un'anticipazione della seconda parte: il problema può essere modellato matematicamente anche ricorrendo alla teoria dei grafi, e il rompicapo che ne deriva assomiglia molto al gioco del sudoku.