Sudoku è riducibile a SAT quindi è NP-Completo
Posted on January 3rd, 2008 by Andrea L. in didattica, softwareVa 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 
Lorenzo 
piciola86 
Entries (RSS)
Tu 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
)
Nel caso questo succeda… ricordati di chi t’ha sempre voluto bene!!