Tutte le sfumature del sudoku

Per molte persone, e chi scrive è tra queste, passare in edicola prima di iniziare una vacanza è diventata una piacevole consuetudine. Che sia mare o montagna, risolvere giochi di enigmistica nei momenti di relax è un passatempo divertente e gratificante. Tra i vari giochi a disposizione, il sudoku ha il più grande seguito di appassionati. Nel sudoku classico viene fornita una griglia 9 × 9, suddivisa in 9 blocchi 3 × 3, in cui alcune caselle contengono un numero compreso tra 1 e 9. L’obiettivo del gioco è riempire le caselle vuote con numeri compresi tra 1 e 9 in modo che in ogni riga, ogni colonna e ogni blocco non ci siano numeri ripetuti. A un occhio inesperto, il legame tra sudoku e matematica sembra evidente: come potrebbe non essere legato alla matematica un gioco basato sull’inserimento dei numeri? Le cifre, in realtà, non hanno alcun significato per chi intende risolvere l’enigma, visto che vengono utilizzate solo in quanto diverse tra loro. Provate a pensarci: cosa cambierebbe se i numeri da 1 a 9 fossero sostituiti dalle prime 9 lettere dell’alfabeto? Oppure da altrettanti oggetti diversi qualsiasi o, più semplicemente, da dei colori? Le tecniche risolutive rimarrebbero le stesse. Sostituire le cifre con dei colori non è un suggerimento casuale. Le griglie di sudoku da completare sono infatti considerate problemi di colorazione all’interno di uno specifico ambito disciplinare della matematica, la teoria dei grafi. In matematica, un grafo è una struttura caratterizzata da un certo numero di punti, detti vertici, che possono essere collegati tra loro da linee, dette lati. In quest’ottica, colorare un grafo significa assegnare un colore a ogni vertice, facendo attenzione che quelli adiacenti (cioè collegati da un lato) non abbiano lo stesso colore. Diventa così evidente il collegamento tra sudoku e colorazioni: un sudoku non è altro che un grafo in cui ogni casella rappresenta un vertice e un lato tra due caselle viene costruito ogni volta che queste si trovano sulla stessa riga, sulla stessa colonna oppure nello stesso blocco. Il riempimento del sudoku è considerato valido quando in ogni riga, casella o blocco non ci sono numeri (colori) ripetuti, esattamente come richiesto dalla colorazione di un grafo. Finora abbiamo soltanto accennato al fatto che i sudoku hanno una rappresentazione analoga in teoria dei grafi, ma in che modo la matematica viene effettivamente in aiuto dell’enigmistica? In questo ambito, è importante produrre sfide sempre nuove e accattivanti. I sudoku, dal canto loro, sono estremamente prolifici. Esistono tantissime varianti ma anche limitandosi alle sole griglie 9×9 è impressionante sapere che quelle complete sono ben 6.670.903.752.021.072.936.960, cioè circa 6.67 × 1021, anche se possono essere ridotte a 5.472.730.538 (5.47×109) se consideriamo uguali griglie simmetriche o con permutazioni delle cifre. In ogni caso, un numero gigantesco! Il problema allora è capire come ottenere le griglie incomplete, in cui siano presenti soltanto alcuni indizi e che abbiano un’unica soluzione valida. Per risolvere questo problema, torniamo alla teoria dei grafi. Per semplicità, immaginiamo i classici sudoku di 9×9 caselle, ma teniamo a mente che ragionamenti completamente analoghi possono essere svolti con griglie quadrate di lato n2 per un qualsiasi intero positivo n: si creano allora sudoku 4×4, 16×16, 25×25 e così via. Utilizzando la terminologia introdotta in precedenza, avere un sudoku parzialmente riempito significa aver assegnato un colore solamente ad alcuni vertici (le caselle già riempite) del grafo corrispondente. Quella appena creata è detta colorazione parziale del grafo. Perché diventi a tutti gli effetti un problema per le riviste di enigmistica, il sudoku deve avere una soluzione univoca, cioè la colorazione parziale fornita dallo schema iniziale deve avere un solo modo di essere estesa ad una colorazione di tutto il grafo. Anche se abbiamo l’impressione che il linguaggio sia cambiato, la soluzione del problema rimane sempre lontana. È qui che la matematica dà il suo contributo: è possibile scrivere per ogni grafo una legge che, supponendo di voler colorare i vertici con x diversi colori, determina quante sono le colorazioni distinte possibili. In più, questa legge è data da un polinomio, che prende il nome di polinomio cromatico del grafo. Nel caso del sudoku classico, l’obiettivo è utilizzare x=9 colori: se con questo dato il polinomio cromatico fornisce un risultato di 1, allora il grafo è pronto per essere trasformato in enigma di logica. In situazioni semplici, comunque, potrebbe non essere necessario l’utilizzo del polinomio cromatico. Ad esempio, un sudoku incompleto in cui manchino inizialmente almeno 2 delle 9 cifre non è possibile che abbia un sola soluzione, visto che le cifre mancanti possono essere scambiate tra loro a piacimento permettendo diverse possibilità. Allo stesso tempo, è stato dimostrato che tutti i sudoku con al massimo 16 indizi non portano a un unico risultato e quindi non è possibile trovare in giro griglie con meno di 17 cifre inserite all’inizio. Non è comunque corretto affermare che solamente la teoria dei grafi abbia dato una mano all’enigmistica, perché è avvenuto anche il contrario. Le diverse varianti di sudoku continuano a fornire idee per diversi problemi nell’ambito della teoria dei grafi e, più in generale, della matematica combinatoria. Inoltre, problemi come il sudoku possiamo incontrarli nella vita di tutti i giorni, mentre cerchiamo di destreggiarci tra i vari impegni della quotidianità. Per fare un esempio pratico, pensiamo di dover pianificare incontri per diversi gruppi di lavoro di una stessa società. Un impiegato può essere coinvolto in più progetti e quindi è necessario che le riunioni avvengano nello stesso momento solo se i gruppi non hanno membri in comune. Tradotto nel linguaggio della teoria dei grafi, significa che i gruppi di lavoro sono considerati vertici collegati tra loro da un lato se hanno membri in comune. Colorare i vertici significa quindi assegnare una fascia oraria ad ogni assemblea in modo che si possa svolgere la riunione, ma facendo attenzione a non far coincidere la fascia oraria (il colore) per gruppi che condividono impiegati (sono adiacenti). Aggiungendo a questo contesto la condizione che alcuni incontri siano già stati fissati, si tratta allora di estendere una colorazione parziale a tutto il grafo, esattamente come avviene con una griglia di sudoku con soltanto alcuni indizi. É proprio grazie anche a problemi e giochi come questi che la matematica trova spunti interessanti. Le strategie risolutive dei sudoku richiedono l’utilizzo di ragionamenti tipici della logica e possono essere trasformate in algoritmi utilizzabili da un computer per risolvere problemi di colorazione anche più complessi. Ecco allora che il sudoku, nella sua semplicità, è diventato un ponte verso un mondo decisamente più vasto, in cui si può venire catapultati nei modi più impensati.