I grandi appassionati di sudoku da oggi avranno un nuovo numero speciale: il 17. Un matematico irlandese sembra infatti aver dimostrato che questo è il numero minimo di indizi necessari per risolvere una griglia di sudoku: con meno indizi è impossibile riempire in modo univoco la griglia di 81 caselle che caratterizza il gioco numerico che, partito dal Giappone alla metà degli anni Ottanta, ha poi conquistato tutto il mondo.

Il matematico Gary McGuire dello University College Dublin ha annunciato questo risultato durante una conferenza che si è tenuta a Boston, Massachusetts, il 7 gennaio. A darne notizia è la rivista scientifica Nature.

Il sudoku è un ormai un gioco estremamente celebre. Per chi non lo conoscesse, le sue regole sono molto semplici. Si tratta di un gioco di logica che si svolge su una griglia di 9×9 celle, ciascuna delle quali può contenere un numero da 1 a 9. La griglia è suddivisa in 9 righe orizzontali, nove colonne verticali e, da bordi in neretto, in 9 “ sottogriglie”, chiamate “ regioni”, di 3×3 celle contigue. Scopo del gioco riempire le caselle con numeri da 1 a 9, in modo tale che in ogni riga, colonna e regione siano presenti tutte le cifre da 1 a 9 e senza ripetizioni.

Inizialmente, alcune celle contengono un numero, l'indizio di partenza. Mediamente, i sudoku proposti dai giornali hanno una ventina di indizi di partenza, ma nel mondo degli appassionati si aveva da tempo la sensazione che al di sotto dei 17 indizi non si potesse scendere. “E si era anche già scoperto che con 17 indizi, in certe particolari disposizioni, la soluzione era unica”, spiega Roberto Natalini, matematico dell’ Istituto Applicazioni del Calcolo M. Picone del Cnr di Roma.

Ora questa ricerca ha mostrato scientificamente, vagliando schema per schema (o quasi), che effettivamente 16 numeri di partenza sono insufficienti per arrivare a una univoca soluzione. “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” precisa Natalini.

In uno schema classico con 81 caselle, è possibile inserire 16 indizi in 6.670.903.752.021.072.936.960 (ossia circa 6.671 miliardi di miliardi) di modi. I tre ricercatori non hanno dovuto però studiare tutte le configurazioni iniziali possibili, perché molte di esse sono semplici varianti di un’unica configurazione.

Se – ad esempio – in una griglia si sostituiscono tutti gli 1 con un 7, il sudoku che ne risulterà sarà diverso ma la sua struttura geometrica resterà la stessa.

Alla fine, come risultato di uno studio preliminare, gli scienziati hanno mostrato che tutte le griglie possibili di partenza possono essere ridotte a 5.472.730.538 (riducendo il numero di partenza di oltre mille miliardi di volte) griglie “di base”.

Nonostante il numero si fosse ridotto così considerevolmente, non è stato comunque molto semplice per i matematici procedere alla verifica dell’ipotesi che con 16 indizi fosse impossibile venire a capo di uno schema classico di sudoku. Il gruppo di ricercatori ha elaborato un algoritmo capace di analizzare una griglia per determinare se poteva o non poteva essere risolta con soltanto 16 indizi e questo algoritmo è stato messo alla prova sugli oltre 5 miliardi di casi considerabili. 

“Si tratta di un algoritmo cosiddetto di 'forza bruta', 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”, spiega Natalini.  

Le analisi del team di scienziati di McGuire si sono svolte in due anni, accumulando 7 milioni di ore di calcoli, nell’Irish Centre for High-End Computing di Dublino. Precisamente in 7,1 milioni di ore di analisi, il nuovo algoritmo ha provato che nessuno di questi quasi cinque miliardi e mezzo di modelli di griglie poteva avere un’unica soluzione partendo da soli 16 indizi. Il “ numero di Dio” del sudoku sembra dunque essere proprio il 17.

“Algoritmi simili si usano in casi in cui si devono trattare volumi enormi di dati, come nel sequenziamento delle basi del genoma umano. La matematica ha fatto passi da gigante in questi settori e proprio quest'anno, il 2012, è stato non a caso dichiarato 'Anno dei dati' dall'American Mathematical Society”, conclude Natalini.

Fonte: wired.it