Ai livelli di difficoltà più elevata, le domande logiche a cui bisogna rispondere sono tutt'altro che banali.
Il Sudoku non è un "cruciverba di numeri", né ha niente a che vedere con l'aritmetica: non si deve fare alcun tipo di addizione, sottrazione, moltiplicazione o divisione.
Le questioni più discusse sul Sudoku sono le seguenti: una combinazione di numeri assegnata in partenza ammette effettivamente una soluzione? C'è una tecnica sistematica che permette di risolvere ogni Sudoku? Quando la soluzione è unica? Quanti sono i Sudoku che ammettono una sola soluzione?
La qualità di un Sudoku, infatti, è data principalmente da questa caratteristica: la soluzione deve essere univoca. Ma allora qual è il numero minimo di numeri assegnati in partenza che rendono un Sudoku univoco? La risposta a questa domanda è tutt'altro che semplice. Mentre il numero massimo di “indizi” di partenza non conta, se ce ne sono troppi il gioco diventa banale e si riduce a una procedura meccanica di riempimento senza che occorra alcun procedimento logico. La quantità minima di numeri di partenza è invece importante, perché sotto una certa soglia il rompicapo diventa impossibile da risolvere, perché ammette più di una soluzione e ciò lo rende esteticamente poco interessante.
Nel numero di giugno 2007 del notiziario della Società Americana di Matematici, Agnes Herzberg e Ram Murty della Queens University (Canada) hanno pubblicato uno studio su queste complesse questioni. 
Il paper si chiama “Sudoku e polinomi cromatici" [http://www.ams.org/notices/200706/tx070600708p.pdf]. I due autori sono riusciti a dimostrare che un Sudoku, per avere una sola soluzione, deve presentare all'inizio del gioco almeno 8 dei 9 numeri. Se ne sono presenti solo 7, allora il puzzle ha almeno due soluzioni.
La dimostrazione di ciò si basa sulla teoria matematica dei grafi. Un grafo è uno schema creato da una serie di nodi connessi da un segmento. Nel contesto del Sudoku, le 81 caselle del puzzle possono essere pensate come gli 81 nodi di un grafo e due nodi sono considerati connessi da un segmento quando si trovano su una stessa riga, colonna o diagonale. Se si rappresenta ciascuno numero (da 1 a 9) con un colore diverso - poiché per regola nel Sudoku non possono esserci numeri uguali sulla stessa riga, colonna o diagonale - il grafo non può presentare connessioni tra nodi dello stesso colore.
Nel linguaggio di questa teoria, un grafo in cui non ci sono connessioni tra nodi dello stesso colore si dice “colorato completo”. Quello che i solutori di Sudoku fanno a ogni partita è quindi cercare di estendere un grafo colorato parziale in uno completo.
Con questa analogia, i due autori hanno provato che il numero di modi di estendere un grafo parziale in uno completo è dato da un polinomio. Se il valore del polinomio è zero per un dato Sudoku, allora il rompicapo non ha soluzione. Se il polinomio è 1, la soluzione è una sola, e così via. Infine gli autori hanno calcolato che dovrebbero essere possibili circa 5,5 miliardi di Sudoku diversi. Chissà se qualcuno riuscirà a risolverli tutti…
Per divertirti con i nostri sudoku vai alla sezione dei sudoku.
