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