La matematica del sudoku porta alla 'scala più ricca' della durezza del puzzle

Il fascino globale del Sudoku ha portato a un improvviso interesse per le proprietà matematiche del puzzle. Negli ultimi mesi su questo blog abbiamo visto come i matematici hanno risolto il problema del sudoku minimo e persino come hanno usato la matematica del sudoku per crittografare le immagini.

Oggi, abbiamo una visione diversa del Sudoku grazie al lavoro di Maria Ercsey-Ravasz presso l'Università Babes-Bolyai in Romania e Zoltan Toroczkai presso l'Università di Notre Dame in Indiana.

Questi ragazzi hanno sviluppato un modo per misurare la difficoltà di un particolare puzzle di Sudoku e dicono che la loro scala Richter di difficoltà del puzzle potrebbe essere applicata a una vasta gamma di altri giochi.

Innanzitutto, un po' di background sul Sudoku. Questo è 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. Inoltre, ogni griglia può avere una sola soluzione.

I puzzle di sudoku sono generalmente classificati come facili, medi o difficili con i puzzle che hanno più indizi di partenza in genere ma non sempre più facili da risolvere. Ma quantificare matematicamente la difficoltà è difficile.

Ora Ercsey-Ravasz e Toroczkai affermano di aver trovato un modo per farlo usando la teoria della complessità algoritmica. Sottolineano che è facile progettare un algoritmo che risolva il Sudoku testando ogni combinazione di cifre per trovare quella che funziona. Quel tipo di soluzione di forza bruta ti garantisce una risposta ma non molto rapidamente.

Invece, i progettisti di algoritmi cercano modi più intelligenti per trovare soluzioni che sfruttino la struttura e i vincoli del problema. Questi algoritmi e il loro comportamento sono più complessi ma ottengono una risposta più rapidamente.

Il punto centrale dell'argomentazione di Ercsey-Ravasz e Toroczkai è che, poiché un algoritmo riflette la struttura del problema, il suo comportamento – i colpi di scena che segue attraverso lo spazio degli stati – è una buona misura della difficoltà del problema.

Per dimostrarlo, affrontano l'esempio del Sudoku. Invece della soluzione della forza bruta, progettano un algoritmo molto più elegante che sfrutta i vari vincoli del puzzle, come il fatto che ogni colonna di riga e sottogriglia deve contenere tutte le cifre da 1 a 9.

In questo modo, trasformano il problema in un tipo noto ai teorici della complessità come problema k-sat.

Iniziano inserendo un insieme casuale di numeri nella griglia e seguono la traiettoria dell'algoritmo attraverso lo spazio degli stati mentre cerca una soluzione. Per un problema semplice, quella traiettoria è semplice, come mostrato nella parte superiore delle due figure nella parte superiore di questo post.

Ma tutto questo cambia per un problema difficile. Ercsey-Ravasz e Toroczkai testano il loro algoritmo contro una griglia di Sudoku così dura da avere un nome proprio: il biondo platino. Il risultato è mostrato nella metà inferiore della figura. È considerevolmente più complesso e richiede dieci volte più tempo per risolverlo.

Ercsey-Ravasz e Toroczkai affermano che per problemi difficili la traiettoria diventa caotica prima di trovare una soluzione. In effetti, il tempo necessario per sfuggire a questo stato caotico è una semplice misura della difficoltà.

Su tale base, creano una 'scala Richter' di difficoltà del puzzle basata sulla velocità di fuga. La scala va da 1 a 4, dove uno è il più facile e 4 è l'ultradifficile.

Dicono che questa scala si correla sorprendentemente bene con le valutazioni umane soggettive con 1 corrispondente a puzzle facili, 2 a puzzle medi e 3 a puzzle difficili. Il biondo platino ha una difficoltà di 3,5789.

Un corollario interessante è che nessun puzzle di Sudoku è conosciuto con una difficoltà di 4. E anche il numero di indizi non è sempre una buona misura della difficoltà. Ercsey-Ravasz e Toroczkai affermano di aver testato molti enigmi, inclusi molti con 17 indizi, il numero minimo e alcuni con 18 indizi.

Questi erano tutti più facili da risolvere rispetto al biondo platino, che ha 21 indizi. Questo perché la durezza del puzzle dipende non solo dal numero di indizi, ma anche dalla loro posizione.

Una domanda interessante ora è se esiste effettivamente un puzzle ultradifficile con una difficoltà di 4 e come può essere trovato.

Più significativo di questo è che il metodo di Ercsey-Ravasz e Toroczkai generalizza a tutti i problemi k-sat della stessa classe del Sudoku. Quindi la difficoltà di questi problemi può essere classificata con scale simili di tipo Richter.

Ciò lascia solo una domanda: come dovrebbe essere chiamata la scala di difficoltà del puzzle? La risposta ovvia è la scala Ercsey-Ravasz e Toroczkai o scala ERT. Eventuali altri suggerimenti nella sezione commenti qui sotto.

Rif: arxiv.org/abs/1208.0370 : Il caos nel sudoku

nascondere