Testata Gazzetta
    Riferimenti

La scienza del sudoku
di Jean-Paul Delahaye

Le Scienze – agosto 2006

Per risolvere un sudoku non serve la matematica, e nemmeno l'aritmetica. Eppure questo gioco divenuto così popolare propone molti affascinanti problemi matematici

Si potrebbe pensare che un gioco basato sulla logica attiri pochissime persone. Probabilmente matematici, appassionati di computer, amanti del gioco d'azzardo. schemi Eppure in pochissimo tempo il sudoku è diventato straordinariamente popolare, tanto da ricordare la moda del cubo di Rubik in voga all'inizio degli anni ottanta.
A differenza del cubo di Rubik, tridimensionale, il sudoku è uno schema quadrato a due dimensioni. In genere è composto da 81 caselle (disposte su nove righe e nove colonne) ed è diviso in nove quadrati più piccoli, ciascuno contenente nove caselle, che chiameremo sottogriglie. All'inizio del gioco in alcune caselle sono stampati dei numeri, il giocatore deve riempire le caselle vuote con le cifre da 1 a 9 in modo che nessuna cifra compaia due volte nella stessa riga, colonna o sottogriglia. Ogni schema ha una soluzione unica.
Paradossalmente, nonostante sia un gioco basato sui numeri, il sudoku non richiede da parte dei giocatori neppure un briciolo di conoscenza matematica. Infatti, non è richiesta alcuna operazione per completare uno schema che, in teoria, potrebbe essere composto con un qualsiasi insieme di nove simboli diversi (lettere, colori, icone e così via). Ciò nonostante il sudoku è, per matematici e informatici, fonte di numerosi e stimolanti problemi.
L'antenato del sudoku non è, come di solito si crede, il quadrato magico, ovvero una matrice in cui la somma dei numeri su ogni riga, su ogni colonna e sulle diagonali è sempre la stessa. Anzi, a parte i numeri e lo schema quadrato, il sudoku non ha quasi nulla a che vedere con il quadrato magico, mentre ha moltissimo a che vedere con il quadrato latino (si veda il box a p. 62).
Un quadrato latino di ordine n è una matrice di n2 caselle (n per lato) riempite con n simboli in modo che lo stesso simbolo non compare mai due volte nella stessa riga o nella stessa colonna (quindi ognuno degli n simboli è usato esattamente n volte). Le origini di questi schemi risalgono al Medioevo, ma fu il matematico svizzero Leonhard Euler a chiamarli quadrati latini e a studiarne le proprietà, nel XVIII secolo.
Un sudoku standard è come un quadrato latino di ordine 9, con unica differenza, cioè il vincolo che in ogni sottogriglia devono essere presenti i numeri da 1 a 9. Il primo gioco di questo genere apparve nel numero del maggio 1979 della rivista «Dell Pencil Puzzles and Word Games», e secondo le ricerche svolte da Will Shortz, curatore della rubrica di cruciverba del «New York Times», pare sia stato creato da un architetto in pensione di nome Howard Garns, morto a Indianapolis nel 1989 (o nel 1981, ci sono diverse versioni): troppo presto per assistere al successo mondiale della sua invenzione.

antenati Gli antenati del sudoku
Un sudoku è un tipo speciale di quadrato latino. I quadrati latini, che furono chiamati così da Eulero, matematico svizzero del Settecento, sono matrici n x n in cui compaiono n simboli in modo che lo stesso simbolo non compare mai due volte nella stessa riga o nella stessa colonna. Qui ne mostriamo due esempi. Un sudoku standard completato è un quadrato latino 9 x 9 che soddisfa il vincolo aggiuntivo che ognuno dei suoi nove sottoschemi contiene le cifre da 1 a 9.

Nel 1984 il gioco, pubblicato dalla Dell Magazines con il nome di «Number Place», approdò a una rivista giapponese che finì con il chiamarlo sudoku, termine che più o meno significa «singoli numeri». La rivista depositò il nome, e così in Giappone gli imitatori usarono il nome «Number Place». Quindi un altro paradosso del sudoku è che i giapponesi lo chiamano con il suo nome inglese, mentre gli anglofoni lo chiamano col nome giapponese.
Il sudoku deve la sua successiva affermazione a Wayne Gould, un magistrato in pensione che oggi vive in Nuova Zelanda, che si imbatté nel gioco mentre visitava il Giappone nel 1997 e scrisse un programma per generare automaticamente griglie di sudoku. Alla fine del 2004 il «Times» di Londra accettò la proposta di Gould di pubblicare il gioco, seguito nel gennaio 2005 dal «Daily Telegraph». Da allora decine di giornali di tutto il mondo hanno iniziato a pubblicare sudoku, in qualche caso mettendolo addirittura in prima pagina come attrattiva promozionale. E sono spuntati libri e riviste, tornei, siti web e blog, tutti dedicati esclusivamente a questo gioco.
Un sudoku per tutti
Non c'è voluto molto perché i matematici si mettessero a giocare con il sudoku. Per esempio si sono subito chiesti quante griglie complete diverse, o «soluzioni», possono essere costruite. Chiaramente la risposta deve essere un numero inferiore a quello dei possibili quadrati latini, a causa del vincolo aggiuntivo delle sottogriglie.
Ci sono solo 12 quadrati latini di ordine 3 e 576 di ordine 4, ma ce ne sono 5.524.751.496.156.892.842.531.225.600 di ordine 9. La teoria dei gruppi, però, dice che uno schema può essere ricavato da un altro se è equivalente all'originale. Se sostituiamo sistematicamente ogni numero con un altro (per esempio, ogni 1 diventa 2, ogni 2 diventa 7 e così via), o se cambiamo di posto due righe o due colonne, gli schemi che otteniamo sono essenzialmente gli stessi. Se si contano solo le forme ridotte, il numero di quadrati latini di ordine 9 è 377.597.570.964.258.816 (risultato pubblicato su «Discrete Mathematics» nel 1975 da Stanley E. Bammel e Jerome Rothstein, all'epoca alla Ohio State University).
E' stato piuttosto difficile stabilire quante griglie di sudoku possono esistere. Oggi solo l'uso della logica (per semplificare il problema) e del computer (per esaminare sistematicamente le tante possibilità) rende possibile una stima del numero di soluzioni, cioè griglie, diverse e valide: 6.670.903.752.021.072.936.960. Questo numero, ricavato da Bertram Felgenhauer del Politecnico di Dresda e da Franz Jarvis dell'Università di Sheffield, comprende tutti quelli derivati da una data griglia con operazioni elementari, ed è stato verificato diverse volte.
Se contiamo solo una volta le griglie che possono essere ridotte a configurazioni equivalenti, il numero si riduce a 5.472.730.538, poco meno del numero di esseri umani sulla Terra: gli appassionati del sudoku, dunque, non devono temere una penuria di giochi.
A una griglia di soluzione finale si può arrivare in più di un modo da una qualsiasi griglia iniziale (cioè da tutte le griglie incomplete la cui soluzione è una specifica griglia completa). Nessuno è ancora riuscito a determinare quanti diversi schemi iniziali esistano. Inoltre, uno schema iniziale del sudoku è interessante per un matematico solo se è minimo, cioè se rimuovere un singolo numero fa sì che la soluzione non sia più unica. Nessuno ha calcolato il numero di possibili schemi minimi esistenti, numero che darebbe la conta definitiva dei diversi sudoku, ma è una sfida che sicuramente sarà raccolta nel prossimo futuro.
C'è un altro problema di minimalità 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 38.000 esempi con questa proprietà che non possono essere ricondotti l'uno all'altro con operazioni come scambi di righe o di colonne.
Gary McGuire della National University of Ireland a Maynooth, 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 e altri in modo indipendente sono riusciti a trovare una griglia con 16 numeri che ha solo due soluzioni, e per ora nessun ricercatore ne ha trovate altre.

cifre Fino a dove si può arrivare?
Sembra che il minimo numero di cifre che devono comparire inizialmente in un sudoku 9 x 9 affinché abbia un'unica soluzione sia 17; qui sotto ne trovate un esempio. Un certo schema completo, noto ai conoscitori del sudoku come Strangely Familiar («stranamente familiare»), o SF, nasconde 29 schemi iniziali non equivalenti con 17 cifre: un numero insolitamente alto. Si pensava che SF fosse il miglior candidato ad avere uno schema iniziale con 16 cifre e un'unica soluzione, ma uno studio approfondito ha infranto questa speranza. In basso è mostrato l'unico sudoku noto che ha 16 cifre e solo due soluzioni; le griglie finali scambiano le posizioni degli 8 e dei 9.

Qualcuno è vicino a dimostrare che nessuno schema valido di sudoku può avere solo 16 numeri? La risposta di McGuire è negativa. «Se anche potessimo analizzare uno schema al secondo, osserva, ci vorrebbero 173 anni per studiarli tutti… Sfortunatamente non si può ancora fare, neppure con un computer velocissimo».
Presto, secondo McGuire, su un computer abbastanza potente sarà possibile esaminare una griglia al minuto, ma a questo ritmo l'impresa richiederebbe 10.380 anni. «Persino distribuendo l'elaborazione su 10.000 computer ci vorrebbe circa un anno», aggiunge. E specifica: «Ci serve veramente un'innovazione teorica radicale per poter eseguire un'analisi di tutti gli schemi. O dobbiamo ridurre lo spazio della ricerca o dobbiamo trovare un algoritmo molto più efficiente».

Sudoku scientifico
  • Il sudoku non è solo un divertente gioco di logica, ma solleva anche una gran quantità di problemi interessanti per i matematici.
  • Tra questi problemi ci sono: quanti sudoku possono essere costruiti? Qual è il minimo numero di cifre che devono essere presenti all'inizio perché si abbia un'unica soluzione? Il sudoku appartiene a una classe di problemi difficili noti come problemi NP-completi, che pongono ostacoli insuperabili al software.
  • Gli esperti di enigmi hanno messo a punto numerosi metodi per affrontare i sudoku, e parecchie divertenti varianti del gioco.

I matematici conoscono la soluzione al problema opposto del minimo numero di cifre: qual è il massimo numero di cifre che non garantisce una soluzione unica? La risposta è 77. E' molto facile vedere che con 80, 79 o 78 cifre se c'è una soluzione è unica, ma ciò non è detto nel caso di 77 cifre (si veda il box).
Soluzioni con il computer
Al di là delle domande su «quante sono», matematici e informatici si divertono a chiedersi che cosa i computer siano o non siano in grado di fare per la soluzione e la generazione di sudoku. Nel caso dei sudoku standard (9 x 9), è relativamente facile scrivere programmi in grado di risolvere tutte le griglie di partenza valide.
I programmi per trovare soluzioni possono usare vari metodi; il più comune è il backtracking, un approccio sistematico per tentativi ed errori in cui si provano soluzioni parziali e le si modificano leggermente appena si riscontra che sono sbagliate.
L'algoritmo base del backtracking funziona così: il programma mette la cifra 1 nella prima casella vuota. Se la scelta è compatibile con le cifre già esistenti, passa alla seconda casella vuota, dove mette un 1. Quando trova un conflitto (il che può accadere molto presto), cancella l'1 appena inserito e inserisce al suo posto un 2 o, se non va bene, un 3 o la successiva cifra accettabile. Dopo aver inserito la prima cifra che non crea conflitto passa alla casella successiva e ricomincia da 1.

metodi Metodi per la soluzione
Ecco alcuni metodi per provare a risolvere un sudoku. I metodi 1 e 2 sono i più semplici, e di solito vengono usati insieme (un po' l'uno e un po' l'altro). Purtroppo spesso non portano lontano, e quindi il giocatore può aiutarsi con il metodo 3 e, se non basta, con il metodo 4, che funziona sempre ma non necessariamente in modo semplice. E' anche possibile inventare metodi propri e provare i numerosi approcci descritti sul Web.
METODO 1. CASELLA «FORZATA»
Questo metodo fissa l'attenzione su una specifica casella. Eliminando dalle possibili soluzioni tutti i numeri che si trovano nella stessa colonna, riga o sottogriglia, si può vedere se rimane un'unica soluzione. Da un'analisi di questo tipo si vede che le caselle che contengono numeri arancioni nello schema b sono «forzate».
METODO 2. CASELLA «UNICA»
In questo metodo ci si concentra su un certo numero, per esempio il 5. Nella prima e nella terza colonna dello schema a il 5 è già presente, ma finora non ce n'è nessuno nella seconda colonna. Dove può essere il 5 di quella colonna? Non nelle prime tre caselle della seconda colonna, perché si trovano in una sottogriglia in cui è già presente. Non nella settima casella della colonna, perché anche la sua sottogriglia ha un 5. Quindi il 5 della seconda colonna si trova nella quarta, quinta o sesta casella della colonna. La quinta è l'unica libera, e quindi il numero va lì. Le caselle con numeri blu nello schema b sono caselle «uniche».
METODO 3. SEMPLIFICARE L'INSIEME DELLE SOLUZIONI POSSIBILI
Questa tecnica è molto potente, ma richiede matita e gomma. In ogni casella si scrivono tutte le possibili soluzioni con numeri molto piccoli o usando puntini le cui posizioni rappresentano i numeri da 1 a 9. Poi si applica la logica per eliminare alcune opzioni. Per esempio, lo schema c raffigura l'aspetto che avrebbe lo schema a se tutte le sue caselle fossero riempite meccanicamente, senza applicare i metodi 1 e 2. Nella terza colonna gli insiemi delle possibili soluzioni (primo ingrandimento) per la seconda, terza, quarta, quinta e sesta casella sono, rispettivamente,(2,3,6,7),(3,6,9),(2,6), (2,6) e (6,7). La colonna deve contenere un 2 e un 6, e quindi questi due numeri devono trovarsi nelle due caselle le cui uniche soluzioni sono 2 e 6 (cerchiati). Di conseguenza, in questa colonna il 2 e il 6 non possono essere da nessun'altra parte e possono essere cancellati dalle altre caselle della colonna (in rosso). Lo spettro delle possibilità per la colonna si è ridotto a (3,7),(3,9),(2,6),(2,6) e (7). Ma non è tutto. Individuare la posizione del 7 ci dà a sua volta le posizioni del 3 e del 9 (secondo ingrandimento). Le possibilità finali sono (3),(9),(2,6),(2,6) e (7). Rimane una sola incertezza: le posizioni del 2 e del 6. La regola generale per semplificare le soluzioni possibili è la seguente: se in un insieme di soluzioni (per una riga, una colonna o una sottogriglia) si trovano m caselle che contengono complessivamente un sottoinsieme fatto di m numeri (non necessariamente tutti in ogni casella), le cifre di questo sottoinsieme possono essere eliminate dalle possibilità per le altre caselle dell'insieme più grande. Per esempio, in d, la situazione (2,3),(1,3),(1,2),(1,2,4,5),(3,5,7) può essere semplificata a (2,3),(1,3),(1,2),(4,5),(5,7) perché le caselle (2,3),(1,3),(1,2) provengono tutte dal sottoinsieme (1,2,3) e non hanno altri numeri.
METODO 4. TENTATIVI ED ERRORI
Applicando i metodi da 1 a 3 si possono risolvere molti sudoku. Ma quelli di livello «diabolico» spesso richiedono una procedura che va per tentativi ed errori. Quando resta un'incertezza si compie una scelta casuale e si applicano tutte le strategie come se fosse la decisione corretta. Se ci si imbatte in una soluzione impossibile (due numeri identici nella stessa colonna) si sa di aver effettuato una scelta scorretta. Per esempio, si potrebbe provare il 2 nella quarta casella della terza colonna dello schema c. Se si rivela sbagliata, si ricomincia dallo stesso punto, ma questa volta ponendo in quella casella il 6.
Purtroppo spesso è necessario provare diverse volte la strategia per tentativi ed errori, e bisogna essere pronti a fare dei passi indietro se si sono compiute scelte sbagliate. L'idea dietro a questo metodo è la stessa usata negli algoritmi di backtracking, che possono essere facilmente implementati nei programmi per computer ma che sono insopportabilmente faticosi per la mente umana. E' singolare che il metodo più efficiente per una macchina sia il meno efficiente per un essere umano.

Se la cifra da modificare è 9 (che non può essere ulteriormente incrementata in un sudoku standard), il programma fa un passo indietro (backtrack) e incrementa di uno la cifra nella casella precedente (la penultima cifra inserita). Poi ricomincia ad avanzare finché non incontra un nuovo conflitto. (Qualche volta il programma fa diversi passi indietro prima di riprendere ad andare avanti.) In un programma ben scritto, questo metodo esplora tutte le possibili ipotesi fino a trovare la soluzione, se esiste. E se esiste più di una soluzione, il che può succedere per un sudoku imperfetto, il programma le trova tutte.
Naturalmente sono possibili miglioramenti che accelerano la scoperta dell'unica soluzione. Uno molto apprezzato è detto constraint propagation (propagazione del vincolo): ogni volta che si inserisce un nuovo numero, il programma genera una tabella dei numeri ammissibili rimanenti per ogni casella vuota e considera solo i numeri di questa tabella.
Le tecniche di backtracking possono essere incorporate in programmi piuttosto piccoli. In particolare, per il sudoku sono stati scritti programmi molto brevi in Prolog, un linguaggio di programmazione che include un algoritmo di backtracking inventato da Alain Colmerauer e Philippe Roussel dell'Università di Marsiglia alla fine degli anni settanta.
Per i giocatori in carne e ossa, le tecniche di soluzione basate sul backtracking non sono praticabili, perché richiederebbero una pazienza sovrumana. Quindi gli esseri umani usano regole più varie e più furbe, e in genere ricorrono al metodo per tentativi ed errori solo come ultima possibilità. Alcuni programmi cercano di imitare almeno in parte i nostri metodi: sono più lunghi degli altri, ma funzionano altrettanto bene. I programmi che simulano il ragionamento umano sono utili anche per valutare la difficoltà degli schemi, che sono classificati da «facile» (quelli che richiedono solo tattiche semplici) a quello che molti chiamano «diabolico» (a causa della necessità di applicare regole logiche più complesse).
Una delle strategie adottate dagli scienziati per trovare la soluzione di un sudoku consiste nel ricondurre il problema a un problema di colorazione di un grafo, in cui due caselle «vicine» (corrispondenti a due vertici congiunti da un arco) non possono avere lo stesso colore e la tavolozza disponibile è formata da nove colori. Il grafo contiene 81 vertici, di cui alcuni colorati fin dall'inizio. Il problema, noto come «problema della colorazione», in realtà è piuttosto complesso, perché ogni schema 9 x 9 ha centinaia di archi. Ogni casella fa parte di una riga che comprende altre otto caselle, di una colonna che comprende altre otto caselle e di una sottogriglia che ne comprende ancora altre otto (di cui quattro sono già state contate nella colonna o nella riga). Quindi ognuna delle 81 caselle è «adiacente» ad altre 20 (8 + 8 + 4) caselle; si hanno così complessivamente 1620 coppie di caselle adiacenti, il che significa che nel grafo ci sono 810 archi (1620 diviso 2).
Il fatto che i sudoku possano essere tradotti in termini di problema della colorazione è significativo per gli scienziati, perché questa proprietà collega il gioco a una classe di problemi importanti. In particolare, Takayuki Yato e Takahiro Seta, entrambi dell'Università di Tokyo, hanno dimostrato di recente che il sudoku appartiene alla categoria dei «problemi NP-completi», problemi che probabilmente non è possibile risolvere in un arco di tempo realistico. Uno degli esempi più noti è il «problema della 3-colorabilità», in cui ci si chiede se è possibile assegnare a ogni nodo di un grafo un colore scelto fra tre, in modo che a due nodi congiunti da un arco non sia mai assegnato lo stesso colore.
Nel caso del sudoku, l'obiettivo apparentemente impossibile consiste nel progettare un programma efficiente che risolva sudoku di qualsiasi dimensione, cioè qualsiasi schema della forma n2 x n2, e non solo la versione standard 32 x 32 (9 x 9). Nessun programma in grado di risolvere qualsiasi schema funzionerebbe efficientemente, perché il tempo necessario per trovare una soluzione aumenta enormemente al crescere di n.

variazioni 1 variazioni 2 Variazioni sul tema
Siete alla ricerca di qualcosa che vada degli usuali sudoku diabolici? Nei giochi illustrati qui accanto si applicano le regole abituali del sudoku, ma con qualche trovata in più. In a le lettere delle parole MARTIN GARDNER, indimenticato autore di una rubrica di giochi matematici su queste pagine, sostituiscono i numeri, e le forme geometriche sostituiscono i sottoschemi quadrati. L'inventore ha chiamato il gioco «Du-Sum-Oh». In b, una stella con solo sei sottogriglie, alcune righe e colonne sono interrotte al centro, e le punte completano le righe più corte. In c i numeri di tre cifre delle prime due sottogriglie nelle righe contras- segnate dai segni aritmetici hanno come somma i numeri nella terza sottogriglia. In d i segni di maggiore e minore servono a trovare le posizioni delle cifre. In e bisogna inserire negli spazi vuoti i pezzi del dominio che si trovano in basso. In f si sovrappongono tre schemi.

Se avessimo un algoritmo in grado di risolvere i sudoku, potremmo usarlo per ottenere un algoritmo in grado di crearli. Infatti, anche se i primi sudoku erano costruiti «a mano», oggi quasi tutti sono generati da programmi basati sull'approccio che sto per descrivere o su uno simile. Si dispongono a caso alcuni numeri in uno schema vuoto e si applica un algoritmo per la ricerca di soluzioni (per esempio il backtracking). Se lo schema ha un'unica soluzione, il programma si arresta. Se lo schema completato parzialmente non ammette soluzioni, si toglie un numero e il programma ricomincia. Se lo schema ha più di una soluzione, se ne sceglie una e l'algoritmo aggiunge allo schema iniziale tutti i numeri che servono per garantire che la soluzione scelta sia unica.
Strategie umane
Gli appassionati che si divertono a risolvere il sudoku a mano possono scegliere tra molte tattiche, ma ci sono due approcci fondamentali che offrono un buon punto di partenza. Il primo consiste nel cercare tra le caselle vuote quelle con più vincoli: cioè quelle che appartengono a una riga,colonna o sottogriglia che sia già in buona parte riempita. Qualche volta, eliminando le cifre non valide (i numeri che già occupano caselle della stessa riga, colonna o sottogriglia), si scopre l'unico numero che va bene in quella casella; in ogni caso, questo metodo riduce di molto le opzioni.

massimo Il massimo per più soluzioni Non è detto che 77 numeri siano sufficienti a garantire un'unica soluzione. Nonostante abbia solo quattro caselle vuote, questo schema ha due soluzioni: nelle prime due colonne i numeri 1 e 2 mancanti sono intercambiabili.

Nel secondo approccio, si cerca dove può stare una data cifra in una certa colonna, riga o sottogriglia (per esempio, cercare gli unici posti in cui il 3 possa trovarsi nella quarta riga). Qualche volta c'è un'unica risposta, altre volte ci si accorge che è utile anche sapere semplicemente che il 3 può andare solo in due o tre posti specifici. Nel box alle pagine 64-65 ci sono ulteriori dettagli; visitando i siti web elencati qui sopra, si troverà una gran quantità di strategie, alcune delle quali hanno nomi fantasiosi come swordfish (pesce spada) e golden chain (catena d'oro).
Molti programmi che si possono trovare facilmente in rete generano schemi di difficoltà predefinita e aiutano a trovare la soluzione (senza risolvere il gioco al vostro posto!). Alcuni per esempio permettono di inserire nelle caselle dei segni provvisori e di cancellarli, rendendo così inutili gomma e matita, altri permettono persino di creare collegamenti tra caselle. Non sottovalutate questi programmi. Liberandovi da attività noiose come le cancellature, vi spingeranno verso maggiori sottigliezze e virtuosismi in questo gioco logico.
Una volta che vi sarete annoiati del sudoku tradizionale, potrete dare un'occhiata alle sue innumerevoli varianti: alcune sovrappongono diversi schemi, altre usano strutture diverse al posto delle sottogriglie quadrate e altre ancora usano vincoli aggiuntivi. L'attrattiva di queste varianti consiste nel costringere a esplorare nuove strategie. E gli appassionati che impiegano cinque minuti per risolvere un gioco tradizionale possono immergersi nelle delizie che si scoprono combinando caselle e numeri in versioni gigantesche del sudoku.
Ma ora basta. Al prossimo sudoku!

© La Gazzetta di Santa