Va di moda nelle keyword più usate per accede al mio sito la tupla "Sudoku np-completo" e devo dire che la curiosità per questo rompicapo si fa risentire.
Già nel novembre del 2005 scrissi qualcosa sulla NP-Completezza di Sudoku, senza approfondire troppo in verità, ora è il caso di aggiornare un pò di link
Innanzi tutto sempre grazie al fidato Google Scholar scopro una interessante articolo che generalizza il problema sudoku su di una matrice n x n e lo riduce a SAT (vi fornisco un link per scoprire cosa questo comporti).
Da qui ovviamente riesumando Cook possiamo asserire che Sudoku è un problema NP-Completo.
Per approfondire l'argomento vi lascio il link alla tesi di Takayuki Yato dell'Università di Tokyo o se volete potete dare uno sguardo all'algoritmo risolutivo, magari capite che l'informatica teorica è pane per il vostro futuro ;)
Popular Posts
-
Introduzione: Ma Non Eravamo Tutti sull'AI? Parliamoci chiaro: nel 202X (o quando diavolo state leggendo), mettersi qui a disquisire sul...
-
Questa sera rileggevo uno sfogo fatto sui social in merito a tante situazioni vissute negli ultimi anni. Situazioni che hanno fatto emergere...
-
Facebook è di sicuro il social network più diffuso in Italia ( sono in molti a dirlo ) e quasi tutti noi lo percepiamo viste le conversa... -
Passerotto in pieno stato d’estasi Riflessione semiseria sulla politica, sul divismo e sull’alimentazione dei passeri. politica (diri...
-
Ci sono molte cose che ruotano attorno al tema della Security (o per chi ama il marketing Cyber Security), una di queste è il Patching Manag...
-
Indegnamente sentiamo parlare sempre più spesso di “hacker”. “Hacker ” che violano i sistemi informatici degli utenti per rubare carte di...
-
Significato della vita. Qual è il senso della nostra esistenza, qual è il significato dell'esistenza di tutti gli esseri vivent... -
La Trusteer ha pubblicato un articolo sul funzionamento di Tatanga (trojan) che dimostra come questa minaccia sia in grado di aggirare ... -
Riflessione su alcuni fatti personali Di cyberbullismo e stalking oramai abbiamo quasi le orecchie sature e sistematicamente si rie...
-
Ne avete mai sentito parlare? Sapete cosa sono? Semplice, sono uno strumento per organizzare il proprio lavoro (che siate manager o operati...
[...] Date un’occhiata al nuovo post [...]
RispondiEliminaTu va a vedere che si scopre che il Sudoku appartiene anche a P e ti porti a casa pure un milione di $ (con 6 zeri :o )
RispondiEliminaNel caso questo succeda... ricordati di chi t'ha sempre voluto bene!! ;)
beh...non c'è che dire....io ero un appassionato del gioco, ora da informatico ho l'obbligo morale di lavorarci sopra, perchè se trovo un algoritmo polinomiale per risolverlo divento ricco!!!!!!!!!!!
RispondiElimina[Yoga mode=on]
RispondiEliminaLimitarti tu non devi, un novello Turing milionario magari sarai
[/Yoda]
Quote: [Innanzi tutto sempre grazie al fidato Google Scholar scopro una interessante articolo che generalizza il problema sudoku su di una matrice n x n e lo riduce a SAT (vi fornisco un link per scoprire cosa questo comporti).
RispondiEliminaDa qui ovviamente riesumando Cook possiamo asserire che Sudoku è un problema NP-Completo.]
Il sudoku è NP-Completo se troviamo una trasformazione polinomiale dal SAT al sudoku, non dal sudoku al SAT.
Avendo dimostrato in precedenza che ogni problema NP è riducibile polinomialmente al SAT questo diventa NP-C.
In teoria il sudoku è solo NP...ma neanche questo è detto...
P (è contenuto in) NP quindi anche un problema in P si può ridurre polinomialmente in un problema NP.
Per transitività x~y e y~z => x~z e non x~y e z~y => x~z dato che non è stato dimostrato che la trasformazione polinomiale è simmetrica.