Jump to content

Sudoku


pat87

Recommended Posts

Ho messo la domanda qui perché sinceramente io faccio sudoku in internet :)

 

Qualche curiosità matematica a proposito (  :love: non la potevo non mettere, saltate queste righe se non sopportate la matematica):

è stato dimostrato che "risolvere" un sudoku in generale, dato un numero casuale di numeri per iniziare, è relativamente lungo e dispendioso. Matematicamente il problema in questione è un problema NP completo. Cosa vuol dire? Vuol dire che  è relativamente semplice VERIFICARE che una soluzione è CORRETTA, ma relativamente difficile TROVARE QUESTA SOLUZIONE. In altre parole è difficile trovare un algoritmo che in "poco" tempo risolva un qualsiasi sudoku, ma è semplice trovarne uno che ti dica se quella soluzione è esatta (in poco tempo).

Se qualcuno riuscisse a trovare un algoritmo che risolvesse in "poco" tempo (un tempo polinomiale) un qualsiasi sudoku, allora per un teorema sarebbe possibile TROVARE LA SOLUZIONE in "poco" tempo di TUTTI i problemi aventi questa proprietà (cioè di classe NP= Nondeterministic Polinomial Problems). Se qualcuno ci riesce vince 1 milione di dollari (non sto scherzando eh  :bah:).

Questo è il più grande problema dell'informatica teorica aperto: P=NP?, (P = Polinomial Problems) ovvero:

"se una data soluzione si può VERIFICARE che è corretta in poco tempo, allora è possibile anche CALCOLARLA in poco tempo?"

Per maggiori informazioni (se la cosa non vi spaventa :D):

http://it.wikipedia.org/wiki/Complessit%C3%A0_P_e_NP

http://programmazione.it/index.php?entity=eitem&idItem=34766

http://freeuser.org/2008/01/03/sudoku-e-riducibile-a-sat-quindi-e-np-completo/

Ok chiudo le parentesi matematiche e informatiche.

Potete riaprire gli occhi!  :bah:

 

 

Giocate a sudoku? :eek:

Dove? Su internet? In qualche rivista?

Quali livelli preferite fare? Siete esperti?

Avete fatto anche qualche i sudoku 16x16?

Link to comment
Share on other sites

Ero un grande appassionato di Sudoku.

 

Ho comprato anche un libretto con un centinaio di griglie, stanco di aspettare l'uscita del quotidiano.

 

Appena il libro è arrivato in casa mia, la passione per il Sudoku è svanita

e ora è nella mia libreria, ancora intonso...

Link to comment
Share on other sites

Faccio i classici 9x9 che trovo sulle riviste, alla difficoltà più elevata (che comunque non è particolarmente impegnativa). Generalmente ne risolvo uno in una mezzoretta, non credo di essere esperto.

Link to comment
Share on other sites

  • 2 weeks later...

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Unfortunately, your content contains terms that we do not allow. Please edit your content to remove the highlighted words below.
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...