La Matematica e il sudoku

Sulla prestigiosa rivista scientifica Nature si legge che il gruppo di matematici diretto da Gary McGuire dell’Università di Dublino ha dimostrato che il numero minimo di indizi necessari per risolvere una griglia di sudoku è 17, infatti con meno indizi è impossibile riempire univocamente la griglia del gioco su cui giornalmente milioni di persone si cimentano. Il sudoku è un rompicapo nato in Giappone verso la metà degli anni Ottanta e negli ultimi dieci anni si è diffuso in tutto il mondo. Consiste di una matrice 9×9 a sua volta suddivisa in 9 sottomatrici 3x3 adiacenti e in ciascuna delle 81 posizioni è possibile inserire un numero da 1 a 9. Lo scopo del gioco è riempire le caselle in modo tale che in ogni riga, colonna e sottomatrice siano presenti tutte le cifre da 1 a 9 ma senza ripetizioni. Le matrici contengono già dei numeri (gli “indizi” di partenza) e solitamente sono una ventina . Ma gli enigmisti già da tempo avevano la sensazione che al di sotto dei 17 dati iniziali non si potesse scendere. Roberto Natalini, matematico presso l’Istituto Applicazioni del Calcolo “M. Picone” di Roma, in un’intervista al giornale on-line Daily Wired ha affermato che “già si era scoperto che con 17 indizi, in certe particolari disposizioni, la soluzione era unica”. Questo nuovo risultato, ottenuto vagliando schema per schema, mostra che 16 numeri di partenza sono insufficienti per giungere ad un’unica soluzione. Continua Natalini: “La novità in questo caso è proprio questa: mentre prima, con 17 indizi, in alcune condizioni c'era l'univocità della soluzione, ma in generale le soluzioni non si trovavano, si è visto che con 16 indizi non è mai possibile arrivare a un'unica soluzione. Questo è l'annuncio che è stato fatto, poi attualmente è in corso la verifica del peer-review”.

In uno schema come quello descritto sopra è possibile inserire 16 indizi in oltre 6 mila miliardi di miliardi di modi. I ricercatori però non hanno analizzato tutte le configurazioni iniziali possibili perché molte di queste sono varianti semplici di un’unica configurazione (ad esempio quella dove al posto del 5 compare il 2). Al netto delle configurazioni utili gli scienziati hanno considerato circa 5 miliardi di condizioni iniziali. Il team di ricercatori ha così implementato un algoritmo capace di analizzare l’unicità della soluzione per una matrice con 16 indizi. Dunque, dopo oltre 7 milioni di ore di calcoli, i matematici irlandesi sono giunti alla conclusione che il numero minimo di dati iniziali per giungere ad un’unica configurazione finale è 17 in quanto con 16 risulta impossibile risolvere unicamente il puzzle. “Si tratta di un algoritmo cosiddetto di 'forza bruta' – ha spiegato Natalini - cioè che va a vagliare tutti i casi possibili - nell'ambito di questa cerchia ristretta - e che al matematico classico abituato a dimostrazioni eleganti a tavolino potrebbe far storcere il naso. Ma nella matematica moderna, a partire dal famoso problema dei Quattro colori risolto negli anni Settanta, il brute-force è ormai diventato una pratica corrente”.