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 1347 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 1689 persone collegate

< febbraio 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
 
             

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

Latest NEWS @
www.TurismoAssociati.it

Non-Hodgkin lymphoma cured by CANNABIS. The video of Stan and Barb Rutner.

Dr. Joycelyn Elders, U.S. surgeon general: Myths About Medical Marijuana in The Providence Journal, 2004.

Marihuana vindeca CANCERUL: marturii despre uleiul de cocos si canabis.

Yahoo Incorporated Mail. My account recovery information is incorrect. The Password Helper says my password can't be reset online. "First time signing in here?" message.

All information in a video about Donatio Mortis Causa and The Venus Project

What is TOR browser?

Coronavirus on G20 agenda as China reports uptick in cases

Nissan, Honda delay restart of some China plants due to coronavirus

Factbox: Events affected by coronavirus epidemic

Iran holds parliamentary election likely to bolster hardliners

Northwest China's Gansu lowers coronavirus emergency response level

Assange's fate hangs in balance as UK court considers U.S. extradition bid

Ultimele articole - Antena3.roPonta, dupa anun?ul lui Raed Arafat privind privatizarea sanata?ii: Va trata?i acasa ca în Evul Mediu? Sa nu spune?i ca nu a?i ?tiut

Economistul Ben?a, predic?ie dura pentru români dupa prabu?irea leului: Efectele deprecierii monedei na?ionale

Raed Arafat, semnal de alarma privind privatizarea din Sanatate: O vizita la UPU ar putea costa 10.000 de lei!

Un tânar din Bucuresti s-a certat cu iubita si i-a dat foc la masina pentru a se razbuna

Unchiul lui Viorel, tânarul ucis în atentatul din Germania: „Parin?ii sunt în stare de ?oc. El venea de la serviciu ?i s-a oprit sa ia un suc. Atunci a fost împu?cat”

MAE a facut anun?ul! Românul ucis în atentatul din Germania va fi repatriat pe banii statului





21/02/2020 @ 09:07:12
script eseguito in 891 ms