I matematici risolvono il problema del sudoku minimo

Il sudoku è un puzzle numerico costituito da una griglia 9 x 9 in cui alcune celle contengono indizi sotto forma di cifre da 1 a 9. Il compito del risolutore è riempire le celle rimanenti in modo che ogni riga, colonna e casella 3×3 in la griglia contiene tutte e nove le cifre.

C'è un'altra regola non scritta: il puzzle deve avere una sola soluzione. Quindi le griglie non possono contenere solo pochi indizi di partenza.

È facile capire perché. Una griglia con 7 indizi non può avere una risposta univoca perché le due cifre mancanti possono sempre essere scambiate in qualsiasi soluzione. Un argomento simile spiega perché le griglie con meno indizi devono avere anche più soluzioni.

Ma non è così facile capire perché una griglia con 8 indizi non può avere una soluzione univoca, o addirittura una con 9 o più indizi.

Ciò solleva una domanda interessante per i matematici: qual è il numero minimo di indizi di Sudoku che produce una risposta univoca?

Questa è una domanda che ha pesato pesantemente sulla comunità di Sudoku, anche perché pensano di conoscere la risposta. I fanatici del sudoku hanno trovato numerosi esempi di griglie con 17 indizi che hanno una soluzione unica ma non ne hanno mai trovata una con 16 indizi.

Ciò suggerisce che il numero minimo è 17, ma nessuno è stato in grado di dimostrare che non esiste una soluzione a 16 indizi in agguato da qualche parte nello spazio dei puzzle.

Entrano Gary McGuire e compagni all'University College di Dublino. Questi ragazzi hanno risolto il problema usando la collaudata tecnica matematica della pura forza bruta.

In sostanza questi ragazzi hanno esaminato ogni potenziale soluzione a 16 indizi per ogni possibile griglia di Sudoku. La nostra ricerca non ha prodotto enigmi a 16 indizi adeguati, ma se ne fosse esistito uno, l'avremmo trovato, dicono.

È un'impresa impressionante. Ci sono esattamente 6, 670, 903, 752, 021, 072, 936, 960 possibili soluzioni per il Sudoku (circa 10^21) . È molto più di quanto possa essere verificato in un ragionevole periodo di tempo.

Ma per fortuna non è necessario controllarli tutti. Vari argomenti di simmetria dimostrano che molte di queste griglie sono equivalenti. Ciò riduce il numero che deve essere controllato a soli 5, 472, 730, 538.

Quindi McGuire e co hanno scritto un programma chiamato Checker per controllare ognuna di queste griglie per una soluzione a 16 indizi.

Ma il processo di controllo di una singola griglia è di per sé complicato. Un modo per farlo è esaminare ogni possibile sottoinsieme di 16 indizi per vedere se qualcuno di essi porta a una soluzione unica. Il problema è che ci sono circa 10^16 sottoinsiemi per ogni griglia.

Ancora una volta, un po' di matematica torna utile. McGuire e co hanno usato un ragionamento intelligente per dimostrare che alcuni sottoinsiemi sono equivalenti a molti altri e questo riduce drasticamente il numero di sottoinsiemi che devono essere controllati.

Tuttavia, il calcolo risultante è ancora un mostro. Il team di Dublino afferma che ci sono voluti 7,1 milioni di ore core di tempo di elaborazione su una macchina con 640 processori Intel Xeon hex-core. Sono iniziati a gennaio 2011 e terminati a dicembre.

L'intero esercizio può sembrare un po' di divertimento matematico, ma questo tipo di risoluzione dei problemi ha molte applicazioni importanti. McGuire e colleghi affermano che il problema del controllo della griglia di Sudoku è formalmente equivalente ai problemi nell'analisi dell'espressione genica e nei test di reti di computer e software.

Quindi i metodi del team di Dublino per accelerare il calcolo avranno un impatto diretto anche in queste aree.

Ma mentre il risultato è chiaramente impressionante, il problema del Sudoku minimo non è del tutto messo a tacere.

Questo problema richiede una dimostrazione elegante che ci permetta di vedere perché il numero minimo deve essere 17; piuttosto come la prova che non ci possono essere soluzioni univoche per 7 o meno indizi.

Una grande domanda, lo so, ma sicuramente vale la pena mirare.

Rif: arxiv.org/abs/1201.0749 : Non esiste un sudoku a 16 indizi: risolvere il problema del numero minimo di indizi del sudoku

Correzione: questo post è stato modificato il 6 gennaio per riflettere l'argomento secondo cui se una griglia di n indizi è risolvibile in modo univoco, anche l'aggiunta di una cifra per creare una griglia di n+1 indizi deve essere risolvibile in modo univoco. Quindi, se non ci sono griglie a 16 indizi risolvibili in modo univoco, non possono esserci griglie con meno indizi risolvibili in modo univoco. Grazie a RealMurph e abooij.

nascondere