Sudoku

[pat87]

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

 

Qualche curiosità matematica a proposito (  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  ).

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 ):

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! 

 

 

Giocate a sudoku?

Dove? Su internet? In qualche rivista?

Quali livelli preferite fare? Siete esperti?

Avete fatto anche qualche i sudoku 16x16?

[Almadel]

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

[FreakyFred]

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.

[.Gi@como.]

Io non li sopporto più ç_ç a furia di essere circondato da gente che li fa giorno e sera mi sono diventati indigesti ._.