Enciclopedia del Sudoku · Matematica e informatica

La matematica del Sudoku

Aggiornato il 2026-10-05

Un quadrato latino con riquadri

In un quadrato latino, ogni simbolo compare una sola volta in ogni riga e in ogni colonna. Un Sudoku completato è un quadrato latino di ordine 9 con una condizione in più: anche ciascuno dei nove riquadri 3×3 contiene ogni cifra una sola volta.

Fonti: Wikipedia: Latin square

Quante griglie esistono

Bertram Felgenhauer e Frazer Jarvis contarono le griglie 9×9 completate nel 2005: sono 6.670.903.752.021.072.936.960, circa 6,67 × 10²¹. Molte sono la stessa griglia sotto un'altra forma. Se si contano come una sola due griglie quando è possibile trasformare l'una nell'altra cambiando le etichette delle cifre, ruotando o riflettendo la griglia, oppure riordinando righe e colonne nei modi che mantengono valida la griglia, rimangono 5.472.730.538 griglie essenzialmente diverse, un valore calcolato da Ed Russell e Frazer Jarvis.

Fonti: Felgenhauer and Jarvis, Enumerating possible Sudoku grids (2005), OEIS A107739: number of Sudoku grids, Wikipedia: Mathematics of Sudoku

Il minimo di 17 indizi

Nessun Sudoku standard 9×9 con 16 o meno cifre iniziali ha esattamente una soluzione. Gary McGuire, Bastian Tugemann e Gilles Civario lo dimostrarono mediante una ricerca esaustiva al computer e annunciarono il risultato nel gennaio 2012. Diciassette è il minimo, non una garanzia: molte griglie con 17 cifre iniziali hanno comunque più di una soluzione.

Fonti: McGuire, Tugemann and Civario, There is no 16-Clue Sudoku (arXiv 1201.0749)

Il Sudoku come colorazione di un grafo

Disegna un punto per ciascuna delle 81 celle e collega due punti ogni volta che le loro celle condividono una riga, una colonna o un riquadro. Questo grafo del Sudoku ha 810 collegamenti, e ogni punto ha esattamente 20 vicini. Risolvere il gioco significa estendere i colori fissati dalle cifre iniziali in modo che i punti collegati non abbiano mai lo stesso colore. Servono almeno nove colori, perché ogni riga, colonna e riquadro è un gruppo di nove punti tutti collegati tra loro, e qualsiasi griglia completata dimostra che nove sono sufficienti.

Fonti: Wikipedia: Sudoku graph

Difficile in generale, rapido per il 9×9

Per le griglie di Sudoku che possono crescere senza limite (n²×n² con riquadri n×n), stabilire se una griglia parzialmente riempita possa essere completata è un problema NP-completo, un risultato pubblicato da Takayuki Yato e Takahiro Seta nel 2003. I programmi informatici efficienti risolvono in genere i normali Sudoku 9×9 in una frazione di secondo, anche se il tempo dipende dal programma, dal computer e dal gioco.

Fonti: Wikipedia: Mathematics of Sudoku, Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle

Vedi anche

Fonti

Tutti gli articoli →