La scienza del

Per risolvere un sudoku non serve la matematica,

e nemmeno l'aritmetica. Eppure questo gioco divenuto così popolare

propone molti affascinanti problemi matematici

di Jean-Paul Delahaye

SUDOKU PER VOI. Inserite

un numero da la 9 in ogni

casella in modo che nessun

numero compaia due volte nella

stessa riga, colonna o sottogriglia

[quadrato 3 X 3). Le soluzioni del sudoku

di difficoltà media al centro dell'illustrazione

e degli altri che appaiono nell'articolo si

possono trovare sul sito www.lescienzeit.

i potrebbe pensare che un gioco basato sulla logi-ca attiri pochissime persone. Probabilmente mate-matici, appassionati di computer, amanti del giocod'azzardo. Eppure in pochissimo tempo il sudoku èdiventato straordinariamente popolare, tanto da ri-cordare la moda del cubo di Rubik in voga all'iniziodegli 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 è di-viso in nove quadrati più piccoli, ciascuno contenente nove

caselle, che chiameremo sottogriglie. All'inizio del giocoin alcune caselle sono stampati dei numeri, il giocatore

deve riempire le caselle vuote con le cifre da 1 a 9 inmodo che nessuna cifra compaia due volte nella stes-

sa riga, colonna o sottogriglia. Ogni schema ha unasoluzione unica.

Paradossalmente, nonostante sia un gioco ba-sato sui numeri, il sudoku non richiede da parte

dei giocatori neppure un briciolo di conoscen-za matematica. Infatti, non è richiesta alcu-na operazione per completare uno schema

che, in teoria, potrebbe essere composto con unqualsiasi insieme di nove simboli diversi (lettere, colo-

ri, icone e così via). Ciò nonostante il sudoku è, per matema-tici e informatici, fonte di numerosi e stimolanti problemi.

L'antenato del sudoku non è, come di solito si crede, il quadratomagico, ovvero una matrice in cui la somma dei numeri su ogniriga, su ogni colonna e sulle diagonali è sempre la stessa. Anzi, aparte i numeri e lo schema quadrato, il sudoku non ha quasi nullaa che vedere con il quadrato magico, mentre ha moltissimo a chevedere con il quadrato latino (si veda il box a p. 62).

Un quadrato latino di ordine n è una matrice di n2 caselle (nper lato) riempite con n simboli in modo che lo stesso simbolonon compare mai due volte nella stessa riga o nella stessa colon-na (quindi ognuno degli n simboli è usato esattamente n volte).Le origini di questi schemi risalgono al Medioevo, ma fu il ma-tematico svizzero Leonhard Euler a chiamarli quadrati latini e astudiarne le proprietà, nel XVIII secolo.

Un sudoku standard è come un quadrato latino di ordine 9, conunica differenza, cioè il vincolo che in ogni sottogriglia devonoessere presenti i numeri da 1 a 9. Il primo gioco di questo genereapparve nel numero del maggio 1979 della rivista «Dell PencilPuzzles and Word Games», e secondo le ricerche svolte da WillShortz, curatore della rubrica di cruciverba del «New York Times»,pare sia stato creato da un architetto in pensione di nome HowardGarns, morto a Indianapolis nel 1989 (o nel 1981, ci sono diverseversioni): troppo presto per assistere al successo mondiale dellasua invenzione.

Nel 1984 il gioco, pubblicato dalla Dell Magazines con il nomedi «Number Place», approdò a una rivista giapponese che finì conil chiamarlo sudoku, termine che più o meno significa «singoli

LE SCIENZE 6160 LE SCIENZE

3 85 464 5 92 8

8 9 36 2 535 9

3fiT.22 3 43 4 24 32

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 Xn 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.

--E

3Quadrato latino che è anche

un sudoku risolto (n=9)

Piccolo quadrato latino(n=4)

Casella

Sottogriglia —

539

8 6 493

26 5

8

3746

9

52346

4 9 2 8 5 6 1 3 7

8296

4

24

9

3 8

6

2 4

3

5

68

4 2

5

25 4

1

4 6

2 —n

6 2

3

4

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

• iare»), o SF, nasconde 29 schemi iniziali non equivalenti con

solitamente alto. Si pensava che SF fosse il miglior candidato

iniziale con 16 cifre e un'unica soluzione, ma uno studio

nto questa speranza. In basso è mostrato l'unico sudoku noto che

ha 16 cifre soluzioni; le griglie finali scambiano le posizioni degli 8 e dei 9.

Un sudoku con 17 cifre

oku con 16 c

• • -

Lo schema «Stranamente familiare»

639 24

78 5

2 8 4

6 5

9 3

51

9 8 3

2 4

123 85

94 6

9 6 4 3 2 8 5 1

4 5 8 6 1 9 2 3

342 17 8 56 9

6

5 9 4 3

2

, 9 7 5 32 6 41 8

e soluzioni

562

139 9 a 47 1

139 4 9 8

6 2 5 3

13 7 4 2 5 139 9 9

6

3 5 89 9 4 6 29 a

4 2 6 3

9 5

216 89 5

3 4 9 9

6 99 1 5 4 2

3 $39

2 5 6 3 9 9 4

4 89 3 9

5 6 2

FINGA DOVE SI PUÒ ARRIVARE?

Qual è il numero di cifre più piccolo che sideve inserire nello schema iniziale di unsudoku per avere un'unica soluzione?

• 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.

numeri». La rivista depositò il nome, e così con un altro (per esempio, ogni 1 diventa 2,in Giappone gli imitatori usarono il nome«Number Place». Quindi un altro paradossodel sudoku è che i giapponesi lo chiamanocon il suo nome inglese, mentre gli anglo-foni lo chiamano col nome giapponese.

sudoku deve la sua successiva affer-mazione a Wayne Gould, un magistrato inpensione che oggi vive in Nuova Zelanda,che si imbattè nel gioco mentre visitava ilGiappone nel 1997 e scrisse un program-ma per generare automaticamente grigliedi sudoku. Alla fine del 2004 il «Times» diLondra accettò la proposta di Gould di pub-blicare il gioco, seguito nel gennaio 2005dal «Daily Telegraph». Da allora decine digiornali di tutto il mondo hanno iniziato apubblicare sudoku, in qualche caso met-tendolo addirittura in prima pagina comeattrattiva promozionale. E sono spuntatilibri e riviste, tornei, siti web e blog, tuttidedicati esclusivamente a questo gioco.

Un sudoku per tutti

Non c'è voluto molto perché i matema-tici si mettessero a giocare con il sudoku.Per esempio si sono subito chiesti quan-te griglie complete diverse, o «soluzioni»,possono essere costruite. Chiaramente larisposta deve essere un numero inferiore aquello dei possibili quadrati latini, a causadel vincolo aggiuntivo delle sottogriglie.

Ci sono solo 12 quadrati latini di or-dine 3 e 576 di ordine 4, ma ce ne sono5.524.751.496.156.892.842.531.225.600di ordine 9. La teoria dei gruppi, però, diceche uno schema può essere ricavato da unaltro se è equivalente all'originale. Se so-stituiamo sistematicamente ogni numero

ogni 2 diventa 7 e così via), o se cambiamodi posto due righe o due colonne, gli sche-mi che otteniamo sono essenzialmente glistessi. Se si contano solo le forme ridotte,il numero di quadrati latini di ordine 9 è377.597.570.964.258.816 (risultato pub-blicato su «Discrete Mathematics» nel 1975da Stanley E. Bammel e Jerome Rothstein,all'epoca alla Ohio State University).

È stato piuttosto difficile stabilire quan-te griglie di sudoku possono esistere. Oggisolo l'uso della logica (per semplificare ilproblema) e del computer (per esamina-re sistematicamente le tante possibilità)rende possibile una stima del numero disoluzioni, cioè griglie, diverse e valide:6.670.903.752.021.072.936.960. Questonumero, ricavato da Bertram Felgenhauerdel Politecnico di Dresda e da Franz Jarvisdell'Università di Sheffield, comprendetutti quelli derivati da una data griglia conoperazioni elementari, ed è stato verificatodiverse volte.

Se contiamo solo una volta le griglieche possono essere ridotte a configura-zioni equivalenti, il numero si riduce a5.472.730.538, poco meno del numero diesseri umani sulla Terra: gli appassionatidel sudoku, dunque, non devono temereuna penuria di giochi.

A una griglia di soluzione finale si puòarrivare in più di un modo da una qual-siasi griglia iniziale (cioè da tutte le griglieincomplete la cui soluzione è una speci-fica griglia completa). Nessuno è anco-ra riuscito a determinare quanti diversischemi iniziali esistano. Inoltre, uno sche-ma iniziale del sudoku è interessante perun matematico solo se è minimo, cioè se

rimuovere un singolo numero fa sì chela soluzione non sia più unica. Nessunoha calcolato il numero di possibili schemiminimi esistenti, numero che darebbe laconta definitiva dei diversi sudoku, ma èuna sfida che sicuramente sarà raccoltanel prossimo futuro.

C'è un altro problema di minimalità tut-tora irrisolto: qual è il più piccolo numerodi cifre che un creatore di sudoku deveinserire nello schema iniziale per garantireuna soluzione unica? Sembra che la rispo-sta sia 17. Gordon Royle della Universityof Western Australia ha raccolto più di38.000 esempi con questa proprietà chenon possono essere ricondotti l'uno all'al-tro con operazioni come scambi di righeo di colonne.

Gary McGuire della National Universityof Ireland a Maynooth, sta conducendouna ricerca per uno schema da 16 nume-ri, ma ancora non ne ha trovati e qual-cuno inizia a pensare che non ne esista-no. D'altro canto, Royle e altri in modoindipendente sono riusciti a trovare unagriglia con 16 numeri che ha solo due so-luzioni, e per ora nessun ricercatore ne hatrovate altre.

Qualcuno è vicino a dimostrare che nes-suno schema valido di sudoku può averesolo 16 numeri? La risposta di McGuireè negativa. Se anche potessimo analiz-zare uno schema al secondo, osserva, civorrebbero 173 anni per studiarli tutti...Sfortunatamente non si può ancora fare,neppure con un computer velocissimo».Presto, secondo McGuire, su un compu-ter abbastanza potente sarà possibile esa-minare una griglia al minuto, ma a que-sto ritmo l'impresa richiederebbe 10.380

anni. «Persino distribuendo l'elaborazio-ne su 10.000 computer ci vorrebbe circaun anno», aggiunge. E specifica: «Ci serveveramente un'innovazione teorica radica-le per poter eseguire un'analisi di tutti glischemi. O dobbiamo ridurre lo spazio dellaricerca o dobbiamo trovare un algoritmomolto più efficiente».

I matematici conoscono la soluzione alproblema opposto del minimo numero dicifre: qual è il massimo numero di cifreche non garantisce una soluzione unica?La risposta è 77. È molto facile vedere checon 80, 79 o 78 cifre se c'è una soluzioneè unica, ma ciò non è detto nel caso di 77cifre (si veda il box in basso a p. 66).

Soluzioni con il computer

Al di là delle domande su «quante sono»,matematici e informatici si divertono achiedersi che cosa i computer siano o nonsiano in grado di fare per la soluzione e lagenerazione di sudoku. Nel caso dei sudo-ku standard (9 x 9), è relativamente facilescrivere programmi in grado di risolveretutte le griglie di partenza valide.

I programmi per trovare soluzioni pos-sono usare vari metodi; il più comune èil backtracking, un approccio sistematicoper tentativi ed errori in cui si provanosoluzioni parziali e le si modificano leg-germente appena si riscontra che sonosbagliate.

L'algoritmo base del backtracking fun-ziona così: il programma mette la cifra 1nella prima casella vuota. Se la scelta ècompatibile con le cifre già esistenti, passaalla seconda casella vuota, dove mette un1. Quando trova un conflitto (il che puòaccadere molto presto), cancella 1'1 appe-na inserito e inserisce al suo posto un 2 o,se non va bene, un 3 o la successiva cifraaccettabile. Dopo aver inserito la prima ci-fra che non crea conflitto passa alla casellasuccessiva e ricomincia da 1.

Se la cifra da modificare è 9 (che nonpuò essere ulteriormente incrementata inun sudoku standard), il programma fa unpasso indietro (backtrack) e incrementa diuno la cifra nella casella precedente (la pe-nultima cifra inserita). Poi ricomincia adavanzare finché non incontra un nuovoconflitto. (Qualche volta il programma fadiversi passi indietro prima di riprenderead andare avanti.) In un programma benscritto, questo metodo esplora tutte le pos-

8 263174

3

62 LE SCIENZE

456 /agosto 2006

www.lescienze.it

LE SCIENZE 63

METODO 4

TENTATIVI ED ERRORI

Applicando i metodi da 1 a 3 si possono risolveremolti sudoku. Ma quelli di livello « diabolico » spessorichiedono una procedura che va per tentativi ederrori. Quando resta un'incertezza si compie unascelta casuale e si applicano tutte le strategie comese fosse la decisione corretta. Se ci si imbatte in unasoluzione impossibile (due numeri identici nella stessacolonna) si sa di aver effettuato una scelta scorretta.Per esempio, si potrebbe provare il 2 nella quartacasella della terza colonna dello schema c. Se si rivelasbagliata, si ricomincia dallo stesso punto, ma questavolta ponendo in quella casella il 6.

Purtroppo spesso è necessario provare diverse volte lastrategia per tentativi ed errori, e bisogna essere pronti

a fare dei passi indietro se si sono compiute sceltesbagliate. L'idea dietro a questo metodo è la stessausata negli algoritmi di backtracking, che possonoessere facilmente implementati nei programmi per

computer ma che sono insopportabilmente faticosiper la mente umana. È singolare che il metodo piùefficiente per una macchina sia il meno efficiente perun essere umano.

L

a

5 1 9 5

9 5

5 2

4 9 1 Caselle«uniche»

4(in blu)

Caselle«forzate» (inarancione)

1 3 2 1

3 4 5 9 3

2 8 1 4 96 5 8 2

/St

—n

7

METODO 3

SEMPLIFICARE L'INSIEME DELLE SOLUZIONI POSSIBILI

Questa tecnica è molto potente, ma richiede matita e gomma. In ogni casella si scrivonotutte le possibili soluzioni con numeri molto piccoli o usando puntini le cui posizionirappresentano i numeri da la 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 suecaselle fossero riempite meccanicamente, senza applicare i metodi 1 e 2. Nella terzacolonna 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,?). La colonna deve contenere un 2 e un 6, e quindi questi due numeri devono trovarsinelle 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 cancellatidalle 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(?). Ma non è tutto. Individuare la posizione del ?ci dà a sua volta le posizioni del 3 e del 9 (secondo ingrandimento). Le possibilità finalisono (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 uninsieme di soluzioni (per una riga, una colonna o una sottogriglia) si trovano mcaselle che contengono complessivamente un sottoinsieme fatto di m numeri (non

necessariamente tutti in ogni casella), le cifre di questo sottoinsieme possono essereeliminate dalle possibilità per le altre caselle dell'insieme più grande. Per esempio, ind, la situazione (2,3),(1,3),(1,2),(1,2,4,5),(3,5,?) 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 dalsottoinsieme (1,2,3)e non hanno altri numeri.

METODO 2 •CASELLA «UNICA»

In questo metodo ci si concentra su un certo numero, per esempio il 5. Nella prima e nellaterza colonna dello schema a il 5 è già presente, ma finora non ce n'è nessuno nella secondacolonna. Dove può essere il 5 di quella colonna? Non nelle prime tre caselle della secondacolonna, perché si trovano in una sottogriglia in cui è già presente. Non nella settima caselladella colonna, perché anche la sua sottogriglia ha un 5. Quindi il 5 della seconda colonna sitrova nella quarta, quinta o sesta casella della colonna. La quinta è l'unica libera, e quindi il

k numero va lì. Le caselle con numeri blu nello schema b sono caselle «uniche».

1 9 6

9 5

5 2

1

7 2

4 6 5 9 7 28 1 4

5 8 2

METODO 1.

5 78W.I I 2 3

4 73

84 823 3

48 9 6

268

47 2367

23647 9

24638

'34 5 '3

4689 4,9 369

346

14 3648 5 2 38

4 9 2 6 1 3682368

356 8

359266

26

234569

3468

1345669

'368

/3'5 8‘1

1 3 6 74569

4684ce

4 6859 2 45

89

3 '4 6 5 9/678

1 68128

9 28 3 6. 1 3569 4

359

76 5 8 2 31 39 13

13,

CASELLA «FORZATA»

Questo metodo fissa l'attenzione su una specificacasella. Eliminando dalle possibili soluzioni tuttii numeri che si trovano nella stessa colonna, rigao sottogriglia, si può vedere se rimane un'unicasoluzione. Da un'analisi di questo tipo si vede chele caselle che contengono numeri arancioni nello

, schema b sono «forzate».

9

3

t2

6

2.3

3

1 2

Ecco alcuni metodi per provare

a risolvere un sudoku. I metodi 1.

2 sono i più semplici, e di solito

vengono usati insieme (un po' l'uno

po spesso

quindi il

con il metodo

I metodo

ma non

do semplice.

tare metodi

rosi approcci

METODI PER LA SOLUZIONE

L'obiettivo apparentemente impossibileconsiste nel progettare un programma cherisolva sudoku di qualsiasi dimensione

sibili ipotesi fmo a trovare la soluzione, seesiste. E se esiste più di una soluzione, ilche può succedere per un sudoku imper-fetto, il programma le trova tutte.

Naturalmente sono possibili migliora-menti che accelerano la scoperta dell'uni-ca soluzione. Uno molto apprezzato è det-to constraint propagation (propagazionedel vincolo): ogni volta che si inserisce unnuovo numero, il programma genera unatabella dei numeri ammissibili rimanentiper ogni casella vuota e considera solo inumeri di questa tabella.

Le tecniche di backtracking possonoessere incorporate in programmi piutto-sto piccoli. In particolare, per il sudokusono stati scritti programmi molto brevi inProlog, un linguaggio di programmazioneche include un algoritmo di backtrackinginventato da Alain Colmerauer e Philippe

Roussel dell'Università di Marsiglia allafine degli anni settanta.

Per i giocatori in carne e ossa, le tecni-che di soluzione basate sul backtrackingnon sono praticabili, perché richiedereb-bero una pazienza sovrumana. Quindi gliesseri umani usano regole più varie e piùfurbe, e in genere ricorrono al metodo pertentativi ed errori solo come ultima possi-bilità. Alcuni programmi cercano di imi-tare almeno in parte i nostri metodi: sonopiù lunghi degli altri, ma funzionano al-trettanto bene. I programmi che simulanoil ragionamento umano sono utili ancheper valutare la difficoltà degli schemi, chesono classificati da «facile» (quelli che ri-chiedono solo tattiche semplici) a quelloche molti chiamano «diabolico» (a causadella necessità di applicare regole logichepiù complesse).

Una delle strategie adottate dagli scien-ziati per trovare la soluzione di un sudokuconsiste nel ricondurre il problema a unproblema di colorazione di un grafo, in cuidue caselle «vicine» (corrispondenti a duevertici congiunti da un arco) non possonoavere lo stesso colore e la tavolozza dispo-nibile è formata da nove colori. Il grafocontiene 81 vertici, di cui alcuni colora-ti fin dall'inizio. Il problema, noto come«problema della colorazione», in realtà èpiuttosto complesso, perché ogni schema9 x 9 ha centinaia di archi. Ogni casellafa parte di una riga che comprende altreotto caselle, di una colonna che compren-de altre otto caselle e di una sottogrigliache ne comprende ancora altre otto (di cuiquattro sono già state contate nella colon-na o nella riga). Quindi ognuna delle 81caselle è «adiacente» ad altre 20 (8 + 8 + 4)

caselle; si hanno così complessivamente1620 coppie di caselle adiacenti, il chesignifica che nel grafo ci sono 810 archi(1620 diviso 2).

11 fatto che i sudoku possano essere tra-dotti in termini di problema della colo-razione è significativo per gli scienziati,perché questa proprietà collega il giocoa una classe di problemi importanti. Inparticolare, Takayuki Yato e TakahiroSeta, entrambi dell'Università di Tokyo,hanno dimostrato di recente che il sudo-ku appartiene alla categoria dei «problemiNP-completi», problemi che probabilmen-

te non è possibile risolvere in un arco ditempo realistico. Uno degli esempi piùnoti è il «problema della 3-colorabilità»,in cui ci si chiede se è possibile assegnarea ogni nodo di un grafo un colore sceltofra tre, in modo che a due nodi congiuntida un arco non sia mai assegnato lo stes-so colore.

Nel caso del sudoku, l'obiettivo ap-parentemente impossibile consiste nelprogettare un programma efficiente cherisolva sudoku di qualsiasi dimensione,cioè qualsiasi schema della forma n2 x n2,e non solo la versione standard 3 2 x 32

(9 x 9). Nessun programma in grado dirisolvere qualsiasi schema funzionerebbeefficientemente, perché il tempo neces-sario per trovare una soluzione aumentaenormemente al crescere di n.

Se avessimo un algoritmo in grado dirisolvere i sudoku, potremmo usarlo perottenere un algoritmo in grado di crearli.Infatti, anche se i primi sudoku erano co-struiti «a mano», oggi quasi tutti sono ge-nerati da programmi basati sull'approccioche sto per descrivere o su uno simile. Sidispongono a caso alcuni numeri in unoschema vuoto e si applica un algoritmoper la ricerca di soluzioni (per esempio ilbacktracking). Se lo schema ha un'unicasoluzione, il programma si arresta. Se loschema completato parzialmente non am-mette soluzioni, si toglie un numero e ilprogramma ricomincia. Se lo schema ha

64 LE SCIENZE

456 /agosto 2006

www.lescienze.it

LE SCIENZE 65

1

5 2

6 4 3

oo

000O Oer e

0 0 o00000

oo

008

oo

oo

o o

o o 9 5O 000

o000

9

5

6

3 4

2

6 50000000

000 00

000 8oo oce°000

5 18 2

O Oo00

o0 0OO

0o0

0000

o

000000000

oO O

O O

00000000000O O O

o

oo

oo

o

0000 °O

0 00000000O O O000

o

o0 0

00

00000 0

oO O

0 0000O O

0000 0000

o

00o

0 0

0 0

000 000O

O00000000000000

00O O0 0

0 0

00

O

0 0000

O O O

O O O O 00

000 000 000

000

9 3

6 4 15 2

2 9

3 1 6

5 8 19 3

L

O 0 O 0o o

O 0o

• o 000 O 0

000 OO0 000 Oo 000 o

000 000 000 o

O 0

O 0O 000

O 00O O O O O

000O 00

000

e

a

oo

o

o

oo

o

0 0o

O O

o

0OO O0 0

oo

O

0000000

oO

o00000000

000000000

O VO

o 00

oo o

0 000O O

0 0 00 00o

0 0o

00 00 00 00 0 0

000000

0000

0 0000

00o

000O O O

O O O o o O O O O 000

o o o

O 0O 0

alla ricerca di qualcosa che vada

degli usuali sudoku diabolici?

hi illustrati qui accanto

o le regole abituali del

a con qualche trovata in

lettere delle parole MARTIN

indimenticato autore di

di giochi matematici su

sostituiscono i numeri,

etriche sostituiscono

quadrati. L'inventore ha

ato il gioco «Du-Sum-Oh». In

stella con solo sei sottogriglie,

e righe e colonne sono interrotte

e le punte completano le

e. In ci numeri di tre cifre

sottogriglie nelle righe

e dai segni aritmetici

mma i numeri nella

ha. In disegni di

re servono a trovare

re. In e bisogna

vuoti i pezzi del

no in basso. Inf

re schemi. Nel sito

tete trovare le

sti schemi.

N

T

E

A N

DM

A

r.

9

6 5 8 24 9

61 855 88 14 56

5 98

3

98

65

4

32

1

PER APPROFONDIRE

Il sito del primo campionato mondiale di sudoku, svoltosi a Lucca il 10-11 marzo 2006: http://

www.wsc2006.com/eng/index.php.

Giochi matematici di Ed Pegg,Jr.: http://www.maa.org/news/mathgames.html.

La matematica del sudoku, di Sourendu Gupta: http://theory.tifr.res.in/-sgupta/sudoku/ .

Matematica del sudoku, di Tom Davis: http://www.geometer.org/mathcircles.

Tecniche per il sudoku (Sad Man Software): http://www.sadmansoftware.com/sudoku/tech-

niques.htm.

Sudoku in generale: http://www.sudoku.com/howtosolve.htm.

Voce «sudoku» di Wikipedia: http://it.wikipedia.org/wiki/Sudoku.

Varianti del sudoku: http://www.sudoku.com/forums/viewtopic.php?t=995.

e??

sufficienti

e

abbia solo quattro

caselle vuote, questo

schema ha due

soluzioni: nelle prime

due colonne i numeri

le 2 mancanti sono

intercambiabili.

3 4 5 6

8 94 5 6

8 9

2 38 9

2 3 4 5 64 3 9 8 5 6

8 6 5 2 1 3 9 4

9 3

6 4

8

23 4 1 8 6 2 9

55

2 9 1 4 6 3 86 9 8 5 3 7 2 4 1

1 2 2 1 314 5 6

8 92 1 1 2 4

•

VARIAZIONI SUL TEMA

più di una soluzione, se ne sceglie una el'algoritmo aggiunge allo schema inizialetutti i numeri che servono per garantireche la soluzione scelta sia unica.

Strategie umane

Gli appassionati che si divertono a risol-vere il sudoku a mano possono sceglieretra molte tattiche, ma ci sono due approccifondamentali che offrono un buon puntodi partenza. 11 primo consiste nel cercaretra le caselle vuote quelle con più vincoli:cioè quelle che appartengono a una riga,colonna o sottogriglia che sia già in buonaparte riempita. Qualche volta, eliminandole cifre non valide (i numeri che già oc-cupano caselle della stessa riga, colonnao sottogriglia), si scopre l'unico numeroche va bene in quella casella; in ogni caso,questo metodo riduce di molto le opzioni.

Nel secondo approccio, si cerca dovepuò stare una data cifra in una certa colon-

IL MASSIMO PER PIÙ SOLUZIONI

L'AUTORE

JEAN-PAUL DELAHAYE è professore di informatica all'Université des Sciences et Technologies

di Lille, in Francia, e ricercatore presso il Laboratoire d'Informatique Fondamentale de Lille del

Centre National de la Recherche Scientifique che ha sede presso la stessa università. Le sue

ricerche si concentrano sulla teoria dei giochi computazionale (per esempio sul dilemma del

prigioniero iterato), sulla teoria della complessità (complessità di Kolmogorov) e sulle appli-

cazioni di queste teorie all'analisi genetica e, di recente, all'economia.

na, riga o sottogriglia (per esempio, cercaregli unici posti in cui il 3 possa trovarsi nellaquarta riga). Qualche volta c'è un'unica ri-sposta, altre volte ci si accorge che è utileanche sapere semplicemente che il 3 puòandare solo in due o tre posti specifici. Nelbox alle pagine 64-65 ci sono ulteriori det-tagli; visitando i siti web elencati qui sopra,

si troverà una gran quantità di strategie,alcune delle quali hanno nomi fantasio-si come swordfish (pesce spada) e goldenchain (catena d'oro).

Molti programmi che si possono trova-re facilmente in rete generano schemi didifficoltà predefinita e aiutano a trovare lasoluzione (senza risolvere il gioco al vostro

posto!). Alcuni per esempio permettono diinserire nelle caselle dei segni provvisori edi cancellarli, rendendo così inutili gommae matita, altri permettono persino di crearecollegamenti tra caselle. Non sottovalutatequesti programmi. Liberandovi da attivitànoiose come le cancellature, vi spingeran-no verso maggiori sottigliezze e virtuosi-smi in questo gioco logico.

Una volta che vi sarete annoiati delsudoku tradizionale, potrete dare un'oc-chiata alle sue innumerevoli varianti: al-cune sovrappongono diversi schemi, altreusano strutture diverse al posto delle sotto-griglie quadrate e altre ancora usano vinco-li aggiuntivi. L'attrattiva di queste varianticonsiste nel costringere a esplorare nuovestrategie. E gli appassionati che impieganocinque minuti per risolvere un gioco tra-dizionale possono immergersi nelle delizieche si scoprono combinando caselle e nu-meri in versioni gigantesche del sudoku.Ma ora basta. Al prossimo sudoku!

oo

66 LE SCIENZE

456 /agosto 2006

www.lescienze.it

LE SCIENZE 6?