Sudoku è riducibile a SAT quindi è NP-Completo
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 ;)