Il teorema del Sudoku

Gli appassionati di Sudoku sanno che alcuni quadri sembrano non aver soluzione, e che altri potrebbero averne più di una, se all’inizio del gioco si fosse scelto un numero al posto di un altro.  Ora un teorema matematico dimostra che, per i Sudoku che hanno una sola soluzione, almeno 8 dei 9 numeri devono apparire all’inizio nel puzzle. Se ne sono presenti solo 7, allora il puzzle ha almeno due soluzioni.

A dimostrarlo Agnes Herzberg e Ram Murty della Queens University (Canada), che hanno esplorato alcune curiose questioni connesse con il popolare gioco, e anno pubblicato lo studio “Sudoku squares and Chromatic Polynomials” sul nuovo numero di Notice of the American Mathematical Society. Gli autori hanno utilizzato gli strumenti della teoria matematica dei grafi per analizzare in modo sistematico i rompicapi e hanno trovato che l’analisi dei quadri porta ad alcuni problemi irrisolti della teoria.

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 (partial colorino) in uno completo. Con questa analogia, i due autori hanno trovato un “teorema del Sudoku”: 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. 

Alcuni quadri sono più difficili di altri e la reale difficoltà sta nel fatto che pochi numeri sono presenti all’inizio del gioco. Qual è il numero minimo necessario per essere sicuri che il puzzle abbia una sola soluzione? Gli autori portano un esempio con  un quadro che ha 17 numeri iniziali e che presenta una sola soluzione. Ma varrebbe anche con 16 o con un numero più piccolo? Nessuno è ancora in grado di dirlo. Si potrebbe essere portati a pensare che un puzzle con molti numeri iniziali abbia più verosimilmente un’unica soluzione, ma questo non è necessariamente vero. Un altro esempio nell’articolo, infatti, riporta il caso di un Sudoku con 29 numeri iniziali, che presenta due soluzioni differenti. Se poi vi siete mai chiesti quanti diversi Sodoku esistono, gli autori hanno calcolato che dovrebbero essere possibili circa 5,5 miliardi di quadri diversi (t.m.).