Sudoku : il gioco che fa impazzire i matematici

SUDOKU : IL GIOCO CHE FA IMPAZZIRE I MATEMATICI

Il giocare per apprendere, per scopi scientifici o medici e comunque tutti i giochi stimolano la curiosità, la voglia di arrivare ad essere sempre più bravi, di vincere se stessi o un ipotetico avversario come il computer; persino il gioco del sudoku ha un potere magico su chi si avvicina anche per puro passatempo.

Sebbene il sudoku sia un gioco basato sui numeri, per risolverlo non serve la matematica e nemmeno l'aritmetica. Eppure questo gioco divenuto popolare è per i matematici e informatici fonte di numerosi e stimolanti problemi. La prima domanda che si sono posti è : quante griglie complete diverse possono essere costruite?

E' piuttosto difficile rispondere; oggi solo l'uso della logica e del computer rende possibile la stima del numero di soluzioni diverse e valide: 6.670.903.752.021.072.936.960, un numero impronunciabile!

Al di là di tutte queste domande, matematici e informatici si divertono a chiedersi che cosa i computer siano in grado di fare per la soluzione e generazione del sudoku. Nel caso di un sudoku standard (9 X 9),è facile scrivere programmi in grado di risolvere tutte le griglie di partenza valide.; il metodo più comune è il " backtracking",un approccio sistematico per tentativi ed errori in cui si provano soluzioni parziali e le si modificano appena si riscontra che sono sbagliate. In un programma ben scritto, questo metodo esplora tutte le possibili ipotesi,fino a trovare la soluzione, se esiste.

Per i giocatori comuni, le tecniche di soluzione basate sul backtracking non sono praticabili, perché richiederebbero una pazienza sovrumana. Gli esseri umani infatti seguono regole più varie e più furbe e ricorrono al metodo per tentativi ed errori solo come ultima possibilità.

Nessuno però è ancora riuscito a determinare quanti diversi schemi iniziali esistano.  C'è poi un altro problema tuttora irrisolto: qual è il più piccolo numero di cifre che un creatore di sudoku deve inserire nello schema iniziale per garantire una soluzione unica? Sembra che la risposta sia 17. Gordon Royle della university of Western Australia ha raccolto più di 38000 esempi. In Irlanda invece Gary McGuire sta conducendo una ricerca per uno schema da 16 numeri, ma ancora non ne ha trovati e qualcuno inizia a pensare che non ne esistano. D'altro canto Royle è riuscito a trovare una griglia con 16 numeri che ha solo due soluzioni. Se anche si potesse analizzare uno schema al secondo ci vorrebbero 173 anni per studiarli tutti. Sfortunatamente non si può ancora fare, ma in futuro, su un computer abbastanza potente sarà possibile esaminare una griglia al minuto,ma a questo ritmo l'impresa richiederebbe comunque 10.380 anni. Le soluzioni sono due; o si riduce lo spazio della ricerca o si deve trovare un algoritmo molto più efficiente.

Comunque l'obiettivo principale dei matematici è di progettare un programma efficiente che risolva sudoku di qualsiasi dimensione,cioè qualsiasi schema della forma n² x n². Tuttavia il tempo necessario per trovare una soluzione aumenta enormemente al crescere di n, quindi nessun programma in grado di risolvere qualsiasi schema funzionerebbe efficacemente.

Se si avesse a disposizione un algoritmo per risolvere i sudoku, si potrebbe usarlo anche per crearli. Si possono trovare anche molti programmi in rete, che generano schemi di difficoltà predefinita. Alcuni permettono anche di inserire nelle caselle dei segni provvisori e di cancellarli, rendendo così inutili gomma e matita. Non è assolutamente da sottovalutare la nuova tecnologia, che liberando il giocatore da attività noiose come la cancellatura, lo spingeranno verso maggiori sottigliezze e virtuosismi in questo gioco logico .

Alla base di tutto l'importante è seguire regole specifiche che ciascuno può individuare come meglio ritiene opportuno per giungere comunque alla soluzione dello schema.

Il rispetto delle regole nei giochi di scienza o di logica, è sempre necessario per arrivare ad una soluzione; quindi non è ammesso barare.

E' stato però dimostrato che barare non è sempre un aspetto negativo, anzi, in alcune situazioni, barare "con stile" può essere vantaggioso.