Immagine
 Trilingual World Observatory: italiano, english, română. GLOBAL NEWS & more... di Redazione
   
 
\\ Home Page : Articolo
Quanti indizi servono per risolvere un sudoku? Il numero magico č il 17: con meno indizi di partenza č impossibile trovare una soluzione. Lo svela una ricerca svolta da un matematico
By Admin (from 14/02/2012 @ 08:03:52, in it - Scienze e Societa, read 1437 times)

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

Articolo Articolo  Storico Storico Stampa Stampa  Share
Cannabis seeds, Autoflowering seeds, Greenhouse, Sweet Seeds, Dutch Passion
comments powered by Disqus
 
Nessun commento trovato. No comments found. Nici un comentariu găsit.

Anti-Spam: dial the numbers CAPTCHA
Text (max 5000 characters)
Nome - Name - Nume
Link ( OPTIONAL - visible on the site - NOT a must )


Disclaimer
Tuo commento sarŕ visibile dopo la moderazione. - Your comment will be visible after the moderation. - Comentariul tău va fi vizibil după moderare.
Ci sono 1920 persone collegate

< settembre 2020 >
L
M
M
G
V
S
D
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
       
             

Titolo
en - Global Observatory (605)
en - Science and Society (594)
en - Video Alert (346)
it - Osservatorio Globale (503)
it - Scienze e Societa (555)
it - Video Alerta (132)
ro - Observator Global (399)
ro - Stiinta si Societate (467)
ro - TV Network (149)
z - Games Giochi Jocuri (68)

Catalogati per mese - Filed by month - Arhivate pe luni:

Gli interventi piů cliccati

Ultimi commenti - Last comments - Ultimele comentarii:
Hi, it's Nathan!Pretty much everyone is using voice search with their Siri/Google/Alexa to ask for services and products now, and next year, it'll be EVERYONE of your customers. Imagine what you are ...
15/01/2019 @ 17:58:25
By Nathan
Now Colorado is one love, I'm already packing suitcases;)
14/01/2018 @ 16:07:36
By Napasechnik
Nice read, I just passed this onto a friend who was doing some research on that. And he just bought me lunch since I found it for him smile So let me rephrase that Thank you for lunch! Whenever you ha...
21/11/2016 @ 09:41:39
By Anonimo


Titolo





20/09/2020 @ 11:46:04
script eseguito in 743 ms