Il sudoku

Quando uscì questo gioco, una decina di anni fa, si pensò che esso avrebbe attirato poche persone (preferibilmente matematici ed esperti informatici) invece in pochissimo tempo il sudoku è diventato straordinariamente popolare tanto da mettersi in concorrenza con altri passatempi, e primi fra tutti i cruciverba.

Negli ultimi tempi sta ottenendo un travolgente successo internazionale per molti versi inspiegabile, ma certamente favorito dal fatto di basarsi su regole estremamente semplici e di richiedere solo una forma di logica essenziale in possesso di tutte le persone compresi i bambini.

Il sudoku è un gioco solitario nel quale al solutore viene proposta una griglia di 9 x 9 = 81 celle ciascuna delle quali può contenere un numero da 1 a 9 oppure essere vuota. La griglia è a sua volta divisa in 9 sottogriglie di 3 x 3 = 9 celle contigue. La regola è unica e molto semplice: il giocatore deve riempire le celle vuote con le cifre da 1 a 9 in modo che nessuna di esse si presenti due volte nella stessa riga, colonna o sottogriglia. Ogni schema ha una soluzione unica.

Non tragga in inganno il fatto che nel gioco compaiano dei numeri: la matematica non c’entra per nulla. Infatti non è richiesta alcuna operazione per completare lo schema il quale in teoria potrebbe essere composto da qualsiasi insieme di 9 simboli diversi (lettere, colori, figure di animali, ecc.)

Il sudoku tuttavia è per matematici e informatici fonte di numerosi e stimolanti problemi. Prima di parlarne vediamo di fare la storia di questo passatempo.

LA STORIA DEL SUDOKU

Gli antenati del sudoku sono i “quadrati magici” noti in Cina 3000 anni prima di Cristo. La leggenda narra di un pescatore che trovò lungo le rive del fiume Lo (un affluente del fiume Giallo) una tartaruga che portava incisi sul dorso degli strani segni geometrici che i matematici presenti a corte interpretarono come un quadrato di numeri con somma costante 15 su ogni riga, colonna o diagonale. Questo schema di nove numeri venne battezzato LO SHU e diventò uno dei simboli sacri della Cina. Ecco l’esempio classico:

Altro antico antenato del sudoku è il quadrato latino uno schema noto già nel Medioevo ripreso poi ed approfondito nel XVIII secolo dal matematico svizzero Leonhard Euler (più noto con il nome di Eulero), il quale è anche l’ideatore del nome. Si tratta di una griglia quadrata di n x n caselle nella quale compaiono n simboli diversi tali da soddisfare la seguente condizione: in ogni riga e in ogni colonna ogni singolo simbolo deve comparire una sola volta come nell’esempio qui sotto riportato per n = 4.

Ecco un altro esempio di quadrato latino di ordine 3 formato con i simboli a, b, c:

La stessa griglia può essere riempita da lettere greche, invece che latine:

Sovrapponendo i due quadrati latini riportati sopra si ottiene un quadrato greco-latino:

Ecco infine la rappresentazione di un sudoku risolto che è anche un quadrato latino 9 x 9 il quale soddisfa il vincolo aggiuntivo che ciascuno dei suoi nove sottoschemi (3 x 3) contiene le cifre da 1 a 9. Si noti inoltre che la somma dei numeri di ogni riga e di ogni colonna è sempre 45. I numeri in rosso formano un sottoschema (o sottogriglia).

Il gioco è nato in Giappone nel 1984 e il suo nome deriva da una frase in lingua giapponese che significa approssimativamente “sono ammessi solo numeri singoli” (SUji wa DOKU-shin ni kagirua) che è stata abbreviata in SU che significa numero e DOKU che significa solitario. Il gioco in realtà era apparso per la prima volta in una rivista americana nel 1979 con il nome di Number Place(“piazzare il numero”), proposto da un architetto che poco dopo morì senza lasciare eredi. Cinque anni più tardi approdò in una rivista giapponese dove fu notato da un certo Wayne Gould, che faceva il giudice a Hong Kong e non conosceva il giapponese. Senza sapere esattamente di cosa si trattasse lo portò in occidente dove venne pubblicato su alcune riviste con il nome di Sudoku. È interessante notare che la rivista giapponese che per prima pubblicò il gioco depositò il nome così che gli imitatori in Giappone lo chiamano Number Place mentre in occidente è chiamato con il nome giapponese.

Verso la fine del 2004 il “Times” di Londra accettò la proposta di Gould, che nel frattempo aveva elaborato un programma per generare automaticamente griglie di sudoku, di pubblicare il gioco sul giornale. Al Times seguì il Daily Telegraph e subito dopo altre decine di giornali di tutto il mondo. Oggi, in Italia, questo gioco è pubblicato su quasi tutti i quotidiani e settimanali riscuotendo molti consensi. Frattanto Gould grazie al sudoku è diventato milionario: egli è probabilmente l’unica persona al mondo che si è arricchita traendo profitto da un gioco che non ha inventato.

LA MATEMATICA LEGATA AL SUDOKU

Non c’è voluto molto tempo perché i matematici si interessassero al sudoku. Essi si chiesero innanzitutto quante griglie diverse potessero essere costruite. La cosa non è semplice ma attraverso l’uso del computer si è riusciti a calcolare il numero di soluzioni diverse e valide. Esse dovrebbero essere molte migliaia di miliardi di miliardi: un numero  ben superiore a quello delle stelle presenti nell’Universo o delle molecole che compongono una mole di sostanza (6,02 x 10²³).

Altro problema affrontato e risolto dai matematici riguarda il più piccolo numero di cifre che un creatore di sudoku deve inserire nello schema iniziale per garantire una soluzione unica. Sembra che questo numero sia 17. E’ provato infatti che se le cifre preventivamente inserite nello schema fossero 16 le soluzioni possibili sarebbero già due e il numero aumenterebbe in modo esponenziale con il diminuire di tale cifra. Normalmente i numeri inseriti nello schema sono da 20 a 35: naturalmente più basso è il numero delle cifre già stampate più la soluzione del gioco è difficile.

I matematici hanno risolto anche il problema opposto e cioè quello di stabilire quale è il numero massimo di cifre che non garantisce una soluzione unica: la risposta è 77. E’ facile verificare che con 80, 79, o 78 cifre se c’è una soluzione essa è unica mentre non è detto che lo sia con 77.

Un altro problema che affascina matematici e informatici è quello di stabilire che cosa il computer sia in grado di fare per la soluzione e la programmazione del gioco. Grazie al computer è relativamente semplice elaborare programmi in grado di risolvere tutte le griglie di partenza valide. I programmi per trovare soluzioni possono essere di vario genere il più comune dei quali è l’approccio sistematico con simulazioni per tentativi ed errori. Esso prevede soluzioni parziali che vengono via via modificate appena si riscontra la loro inesattezza. Il programma, se accurato, esplora tutte le possibili ipotesi fino ad individuare la soluzione giusta, se questa esiste.

La tecnica di soluzione applicata al computer non è praticabile dalle persone fisiche perché richiederebbe da parte degli operatori la pazienza di Giobbe. Quindi gli esseri umani usano metodi risolutivi più sbrigativi e intuitivi rispetto a quelli analizzati dal computer.

Del gioco esistono numerose varianti: alcune sovrappongono diversi schemi, altre usano strutture diverse al posto delle sottogriglie quadrate ed altre ancora usano vincoli aggiuntivi. Esistono anche esempi di sudoku con schemi superiori a quello classico di 9 x 9 e gli informatici sono impegnati nello sviluppo di programmi in grado di risolvere e quindi di creare sudoku di complessità sempre maggiore, ma il tempo necessario al computer per trovare una soluzione al gioco aumenta enormemente al crescere del numero di celle di partenza.

METODOLOGIE RISOLUTIVE

Gli appassionati utilizzano tecniche di vario tipo per pervenire alla soluzione del gioco ma vi sono due approcci fondamentali che offrono un buon punto di partenza. Prima di parlarne è opportuno indicare il criterio che adotteremo per individuare le caselle e le sottogriglie. Noi individueremo la generica casella, analogamente a quanto avviene nel gioco della battaglia navale, mediante coordinate (riga, colonna) mentre ogni sottogriglia 3 x 3 è evidenziata da un numero in grassetto: da 1 a 9 come si può vedere nella sottoindicata tabella.

Come primo esempio di risoluzione si osservi lo schema riportato qui sotto che contiene 28 numeri predeterminati. All’inizio conviene partire dal numero maggiormente ripetuto che nel nostro caso è il 6. Prendendo in esame la sottogriglia 8 si vede come il 6 debba essere posizionato nella casella (9,5) essendo già presente un 6 nella riga 7, nella riga 8 e nella colonna 4. Si passi ora alla sottogriglia 5 dove l’unica possibilità per il 6 è offerta dalla casella (6,6), essendo già presente un 6 nella colonna 4, nella colonna 5 (dove è stato appena posizionato), nella riga 4 e nella riga 5. Inmodo analogo è possibile fissare un 6 nella casella (3,2) ed infine l’ultimo nella casella (2,8). Posizionati quindi tutti i 6 si passa ai prossimi numeri maggiormente ripetuti: essi sono il 4, il 7 e l’8. Iniziamo dal 7.

Continuando nell’osservazione dello schema proposto si nota che un 7 deve essere posizionato nella casella (9,9) della sottogriglia 9 mentre un secondo 7 va messo nella casella (4,4) della sottogriglia 5. Restano da individuare le caselle dove collocare il 7 nelle sottogriglie 1, 3 e 7. Osservando la sottogriglia 1 il 7 non può trovar posto nella colonna 2 essendo essa già occupata da tre numeri né nella colonna 3 trovandosi già un 7 nella casella (6,3). Il 7 potrà quindi andare o nella casella (1,1) o nella casella (3,1): esso andrà inserito in ogni caso nella colonna 1. Questa informazione permette di posizionare un 7 nella casella (8,2) della sottogriglia 7. Per quanto riguarda la sottogriglia 3 il 7 si colloca nella casella (1,8) e dunque nella sottogriglia 1 il dubbio iniziale viene risolto in quanto ora solo la casella (3,1) può ospitare il 7.

Proseguendo con la risoluzione dello schema è immediato posizionare all’interno della sottogriglia 5 il numero 1 nella casella (5,6), il 3 nella casella (5,1) e di conseguenza lo stesso numero nella casella (6,7) e nella casella (2,9).

La determinazione del 2 nella casella (5,2) si deduce dal fatto che nella sottogriglia 5 il 2 è sicuramente posizionato in una casella della riga 4, non potendo trovarsi nella riga 6 per la presenza del 2 nella casella (6,9). Nelle due caselle della riga 5 infatti si dovranno posizionare il 4 e l’8, presenti nella sottogriglia 4 alla riga 6 e nella sottogriglia 6 alla riga 4. Pertanto, nella sottogriglia 4 il 2 si troverà nella riga 5 dove resta libera solo la casella (5,2). A questo punto, procedendo con il metodo indicato, dovrebbe essere semplice completare lo schema.

La soluzione definitiva è la seguente:

Passiamo ora ad un nuovo esempio di soluzione che prende avvio da uno schema che contiene 27 numeri iniziali:

La sottogriglia 1 contiene i numeri 1,3,5,6 e 9. Rimangono da sistemare i numeri 2,4,7 e 8. Nella colonna 2 le prime due caselle dovranno contenere il 4 e l’8 in quanto più sotto sono presenti il 2 e il 7. I numero 8 dovrà collocarsi nella casella (1,2) in quanto nella seconda riga è già presente l’8 nella casella (2,6). Il 4 troverà quindi sistemazione nella casella (2,2). Proseguendo con la sistemazione dei numeri si nota che un 1 va sistemato nella casella (3,9) in quanto questa cifra presente nelle sottogriglie 1 e 2 manca nella sottogriglia 3 dove non può trovar sede se non nella terza riga, un 5 nella casella (1,7) e un 7 nella casella (9,4). A questo punto si osservino le sottogriglie 7, 8 e 9. Nella sottogriglia 8 il 6 potrebbe trovare sistemazione solo in una delle ultime due caselle della colonna 5 in quanto questo numero è presente nella riga 7 e nella colonna 6.

Ora, una volta stabilito che il 6 può trovar sede nella colonna 5 della sottogriglia 8, si osservi la sottogriglia 2 in cui il 6 non potrà che sistemarsi nella casella (2,4) poiché questo numero è già presente nelle colonne 5 (dove deve essere definita con precisione la posizione) e 6. Proseguendo si può posizionare un 6 nella casella (3,7).

Nella sottogriglia 9 il 9 potrà collocarsi in una delle due caselle finali della colonna 8 essendo già presente questo numero nella riga 7 e nella colonna 9. Il 9 relativo alla sottogriglia 3 si posiziona pertanto nella casella (2,7) non potendo trovar sede né nella colonna 8 (dove la posizione precisa deve essere ancora definita ) né nella colonna 9.