Sudoku: con meno di 17 indizi è impossibile risolverlo

Sudoku-
Il sudoku, S?ji wa dokushin ni kagiru, in italiano si può tradurre come: sono consentiti solo numeri solitari. Al giocatore è proposta una griglia di 9×9 celle, ognuna delle quali può contenere un numero da 1 a 9, oppure può essere vuota; la griglia è suddivisa in 9 righe orizzontali, nove colonne verticali e, dei bordi in neretto, in 9 sottogriglie, chiamate regioni, di 3×3 celle contigue. Le griglie hanno da 20 a 35 celle contenenti un numero. Lo scopo del gioco è quello di riempire le caselle bianche con numeri da 1 a 9, in modo che in ogni riga, colonna e regione siano presenti tutte le cifre da 1 a 9 senza ripetizioni. La versione moderna del Sudoku fu ideata da Howard Garns architetto statunitense e pubblicata da Dell Magazines nel 1979 con il titolo Number Place. Diffuso in Giappone dalla casa editrice Nikoli nel 1984, a partire dal 2005 diventa noto in tutto il mondo.
17 indizi- Il matematico irlandese Gary McGuire dello University College Dublin, ha dimostrato che 17 è il limite cercato nel sudoku: uno schema di sudoku con sedici o meno caselle riempite ha più di una soluzione. Con un numero inferiore di 17 indizi e’ praticamente impossibile risolvere la griglia di 81 caselle che tanto caratterizza il gioco numerico. Le ricerche del team di McGuire si sono verificate nell’arco di due anni, e hanno accumulato circa 7 milioni di ore di calcoli nell’ Irish Centre for High-End Computing di Dublino.E’ stato elaborato un algoritmo elaborato un algoritmo e un programma che sono capaci di analizzare una griglia contenente 81 numeri per capire se era possibile risolverla con soltanto 16 indizi. Il gruppo di scienziati ha mostrato che le griglie possibili possono essere ridotte a 5 472 730 538 di griglie, in un secondo momento, 7,1 milioni di ore di analisi con il nuovo algoritmo sviluppato hanno dimostrato che nessuno di questi quasi cinque miliardi e mezzo di griglie poteva avere un’unica soluzione se si partiva da soli 16 indizi.
Rosanna Pecora

Notizie Correlate

Commenta