Come emerge l’innovazione?

 

L’innovazione e’ una delle forze trainanti del mondo. La creazione costante di nuove idee e la loro trasformazione in tecnologie e prodotti e’ di sicuro una pietra angolare della nostra societa’. Questo spiega perche’ molte Universita’ e Istituti sono interessati a questo tipo di processo che ancora oggi appare misterioso e poco capito. Molti ricercatori hanno dedicato tempo a questo studio con lo scopo di capire come l’innovazione prende forma e i fattori che la guidano. Ad oggi questo approccio ha avuto un successo limitato. Anche se il tasso con cui avvengono le innovazioni e’ stato attentamente misurato e si e’ visto che segue dei pattern ben definiti in circostanze anche diverse tra loro, nessuno e’ ancora riuscito a spiegare come nascono le nuove idee e perche’ solo certi fattori e non altri ne influenzano la velocita’.

Tutto questo, oggi sembra cambiare grazie ad un lavoro di Vittorio Loreto della Sapienza di Roma che insieme ad altri suoi colleghi tra cui il famoso matematico Steven Strogatz noto per aver pubblicato un libro sul fenomeno della sincronizzazione, hanno creato un modello matematico che riproduce accuratamente i pattern seguiti dall’innovazione. Questo lavoro da’ vita ad un nuovo approccio nello studio dell’innovazione e di come essa emerga da quello che gia’ esiste. La nozione che l’innovazione nasca dall’interazione tra l’attuale e il possibile e’ stata formulata per la prima volta dal teorico Stuart Kauffmann nel 2002 con l’idea dell’ ”adiacente possibile” come strategia seguita dall’evoluzione biologica. L’adiacente possibile e’ l’insieme di tutte le cose (idee, parole, musica, molecole, genoma, tecnologie....) che sono molto vicine (ad un passo) a quello che esiste oggi. Esso connette la realizzazione attuale di un particolare fenomeno e lo spazio delle possibilita’ ancora inesplorate.

Illustrazione matematica dell’adiacente possibile in termini di grafo che si espande dalla situazione (a) a quella in (b) ogni volta che un passante visita un nodo per la prima volta (il nodo in bianco in (a).

Questa idea nonostante il suo fascino e’ difficile da modellizzare in quanto lo spazio delle possibilita’ inesplorate include non solo tutte le cose immaginate e aspettate ma anche quelle che sono inaspettate e difficili da immaginare. Inoltre mentre la prima e’ difficile da realizzare la seconda e’ molto prossima all’impossibile. Per non parlare del cambiamento continuo dello spazio delle possibilita’ inesplorate. Anche se la potenza creativa dell’ “adiacente possibile” e’ largamente apprezzata a livello di curiosita’ la sua importanza nella letteratura scientifica e’ sottostimata stando a quello che dice Loreto. Nonostante tutta questa complessita’, l’innovazione comunque sembra seguire dei pattern prevedibili e facilmente misurabili conosciuti oggi come leggi grazie alla loro ubiquita’. Una di questi leggi e’ quella che prende il nome di “legge di Heaps”; essa stabilisce che il numero di cose nuove cresce a un tasso sottolineare o in altre parole secondo una legge di potenza della forma:

V(n) = kn^β          dove β e’ compreso tra 0 e 1.

Questa legge attribuita ad Heaps ma in realta’ scoperta da Gustav Herdan stabilisce che in linguistica il numero di parole distinte V (asse y del grafico sotto) presenti in un documento dipende dalla sua lunghezza n (numero totale di parole – asse x del grafico). In altre parole se supponiamo di avere una lista ordinata di parole in un testo, man mano che la scorriamo troveremo delle parole nuove che non saranno mai occorse prima e quindi riportando il numero di parole diverse in funzione del numero di tutte le parole occorse fino ad un dato punto si ottiene per grandi numeri la legge di potenza di Heaps.

Le parole spesso vengono pensate come una sorta di innovazione, e il linguaggio si evolve costantemente man mano che appaiono nuove parole e quelle vecchie vanno in disuso. E questa evoluzione segue la legge di Heaps con un coefficiente β compreso tra 0 e 1. Pensiamo ad un vocabolario degli inizi del 1900 e confrontiamolo con uno dei giorni nostri. Sicuramente in quello del 1900 non troveremo termini come internet, rete sociali, crowdfunding, computer e cosi via. Il numero di parole totali contenute nel vocabolario di oggi e’ decisamente maggiore di quello del 1900 e la differenza tra i due vocabolari e’ guidata dalla legge di Heaps.

Un altro pattern statistico seguito dal processo di innovazione e’ quello della legge di Zipf’s che descrive come la frequenza di una innovazione e’ legata alla sua popolarita’. Questa legge venne descritta per la prima volta dal linguista e filologo statunitense G. K. Zipf ed oggi essa trova applicazione nei campi piu’ svariati essendo diventata la controparte della distribuzione Gaussiana nell’ambito delle scienze sociali. Questa legge mette in relazione la frequenza di un evento con la posizione in classifica del verificarsi di questo evento, in un ordinamento decrescente (rango). Fra i casi piu’ famosi in cui la legge viene verificata abbiamo le frequenze delle parole negli scritti e la distribuzione della popolazione nelle varie citta’ di uno stato. La legge matematica e’ scritta in questo modo:

f(n)=c/n

dove f e’ la frequenza, c una costante e n il rango, cioe’ la posizione in classifica. All’interno di un testo per esempio la parola piu’ frequente si presenta quasi il doppio delle volte rispetto alla parola in seconda posizione , il triplo della parola in terza posizione e cosi via. In inglese la parola piu’ frequente e’  “the” con una frequenza del 7% seguita da “of” con un 3.5%, da “and,” e cosi via. Ovviamente se un testo fosse scritto disponendo le parole in modo del tutto casuale allora la legge di Zipf non sarebbe valida. Ma non e’ cosi essendo le parole nei testi vincolate da regole (sintassi, grammatica, estetica, ecc) e quindi si ribellano alla legge Gaussiana. Zipf spiega la legge trovata che in seguito prendera’ il suo nome ricorrendo al cosiddetto principio del minimo sforzo che descrive la normale tendenza di certi fenomeni a cercare di ottenere il massimo risultato con il minimo impiego di forze. Facciamo un esempio considerando il romanzo dei promessi Sposi. Qui di seguito la classifica della parole piu’ usate dal Manzoni con la colonna E ed F del file excel contente il logaritmo in base 2 del rango e della frequenza relativa. Prendiamo il logaritmo perche’ essendo una legge di potenza in questo modo avremo una retta come si vede nel grafico qui sotto.

Sia la legge di Zipf che quella di Heaps sono leggi empiriche nel senso che le conosciamo solo perche’ le misuriamo. Ma perche’ i pattern prendono proprio questa forma nessuno lo sa. Quello che serve non e’ tanto modellizzare l’innovazione inserendo i numeri osservati in equazioni matematiche quanto avere un modello che produce questi numeri a partire da principi primi (postulati). E qui entra in gioco il lavoro di Loreto e colleghi. Il concetto di base e’ proprio quello dell’adiacente possibile. Come sappiamo l’evoluzione non procede per salti. La natura come anche la tecnologia cerca di innovare partendo dal materiale che ha gia’ a disposizione attraverso una sua opportuna ricombinazione. L’innovazione quindi puo’ essere rappresentata come l’esplorazione di uno spazio fittizio (biologico, fisico, tecnologico ecc.) possibile che si allarga di volta in volta con nuovi elementi. E’ come dire che da cosa nasce cosa.

Il team di ricercatori per la prima volta ha creato un modello di questo tipo che spiega i pattern dell’innovazione. Sono partiti da quella che e’ conosciuta come Urna di Polya: un’urna riempita con palline di diversi colori. Una pallina viene pescata a caso, esaminata e reinserita nell’urna insieme ad una certa quantita’ di nuove palline dello stesso colore. Questo aumenta la probabilita’ che nelle successive estrazioni venga selezionata una pallina proprio di questo colore. Questo modello viene utilizzato dai matematici per esplorare il cosiddetto effetto di rinforzo o del “ricco che diventa sempre piu’ ricco” da cui emerge la legge di potenza. Qui di seguito il risultato di due simulazione dell’urna di Polya partendo con 5 palline rosse, 4 nere, 3 gialle, 2 verdi e una blu. Nel primo caso (grafico a sinistra) anche se inizialmente le palline verdi sono meno di quelle rosse a partire dalla decima estrazione circa il loro numero inizia ad aumentare e da quel momento in poi’ cresce sempre di piu’ diventando quello dominante. Sulla destra una seconda simulazione dove si vede che addirittura le palline blu (le minoritarie inizialmente) iniziano a competere con quelle rosse (all’inizio quelle maggioritarie). In questo caso vediamo al lavoro il meccanismo di rinforzo ma non c’e’ nessun elemento di innovazione, cioe’ nessuna novita’.

L’urna di Polya quindi e’ un buon punto di partenza per costruire un modello dell’innovazione anche se essa non produce la crescita sottolineare di Heaps. In altre parole il modello di Polya permette tutte le conseguenze aspettate per l’innovazione (quelle di scoprire un certo colore) ma non considera le conseguenze inaspettate di come l’innovazione influenza l’adiacente possibile. Per questo motivo il gruppo di fisici ha modificato il modello dell’urna di Polya per avere la possibilita’ che una volta scoperto un nuovo colore nell’urna questo possa innescare tutta una serie di conseguenze inaspettate. Questo nuovo modello e’ stato chiamato urna di Polya che innesca innovazione.

Si parte con un’urna riempita con palline colorate. Una pallina viene prelevata a caso dall’urna, esaminata, e rimessa nell’urna. Se il colore e’ gia’ stato visto prima, allora un certo numero di palle dello stesso colore viene inserito nell’urna. Ma se il colore e’ nuovo (cioe’ visto per la prima volta) allora un certo numero di palline di un nuovo colore viene aggiunto all’urna. Nel disegno seguente a sinistra viene riportato quello che accade con il semplice modello dell’urna di Polya e a destra con quello modificato da Loreto e colleghi. Le palline colorate rappresentano canzoni che abbiamo ascoltato, pagine web visitate, invenzioni, idee o qualsiasi altra esperienza umana o prodotti della nostra creativita’. Una serie di invenzioni viene idealizzata con una sequenza S di elementi generati tramite estrazioni successive dall’urna U. Esattamente come l’adiacente possibile quando capita qualche cosa di nuovo (una pallina di colore mai visto prima), i contenuti dell’urna stessa cambiano (si allargano). Matematicamente viene considerata una sequenza ordinata S costruita prelevando le palline dall’urna contenente inizialmente un certo numero di palline distinte. Sia il numero di palline nell’urna che nella sequenza aumentano nel tempo. A sinistra vediamo come dopo l’estrazione di una pallina di colore grigio, questa viene rimessa nell’urna insieme a 4 palline dello stesso colore grigio. A destra invece il nuovo modello fa vedere come dopo l’estrazione di una pallina di colore rosso dall’urna, questa viene rimessa dentro insieme ad una copia di 4 palline dello stesso colore rosso e 4 palline di colore non contenuto nell’urna.

Eseguendo le simulazioni al computer, Loreto e i suoi colleghi hanno calcolato come cambia nel tempo il numero di nuovi colori presi dall’urna e la loro frequenza. La sorpresa e’ stata che questo modello riproduce entrambe la legge di Heaps e quella di Zipf e quindi per la prima volta sono state riprodotte le osservazioni empiriche partendo da un postulato. Il team ha mostrato anche che il modello predice come le innovazioni compaiono nel mondo reale. Il modello infatti, predice accuratamente come si presentano gli eventi di modifica delle pagine di Wikipedia, la sequenza delle parole nei testi e di come gli umani scoprono nuove canzoni in un catalogo online di musica. Qui di seguito la legge di Heap e di Zipf predette dai risultati analitici e confermati dai risultati numerici delle simulazioni.

Questi sistemi coinvolgono 2 diverse forme di scoperta. Da una parte, ci sono cose che gia’ esistono ma sono nuove per l’individuo che le trova come per esempio le canzoni online e dall’altra le cose che non esistevano prima e che sono nuove per il mondo intero come per esempio le modifiche delle pagine di Wikipedia. Il team parla di novita’ nel primo caso (una cosa nuova per l’individuo) e di innovazione nel secondo caso (una cosa nuova per il mondo). Curiosamente lo stesso modello spiega entrambi i fenomeni. Sembra che il pattern di come si scoprono le novita’ e’ lo stesso che regola l’emergenza dell’innovazione dall’adiacente possibile. Questo solleva delle questioni interessanti, non ultima quella del perche’ le cose dovrebbero andare proprio in questo modo. Ma apre anche un interno nuovo modo di pensare all’innovazione e agli eventi che portano alle novita’. Questi risultati forniscono un punto di partenza per un’analisi piu’ approfondita dell’adiacente possibile e la diversa natura degli eventi di innesco nell’evoluzione biologica, linguistica, culturale e tecnologica. Non ci resta che aspettare e vedere come lo studio dell’innovazione evolvera’ dall’adiacente possibile come risultato di questo lavoro.

Qui l’articolo di Loreto e colleghi per chi vuole approfondire l’argomento: Link

La matematica del Sudoku

 

Il gioco giapponese del sudoku, affonda le sue radici nei quadrati magici studiati da Eulero.

Un quadrato magico è uno schieramento di numeri interi distinti in una tabella quadrata tale che la somma dei numeri presenti in ogni riga, in ogni colonna e in entrambe le diagonali dia sempre lo stesso numero; tale intero è denominato la costante magica del quadrato.

Il Sudoku si e’ subito diffuso in tutto il mondo, come era gia’ successo per il cubo di Rubik, il gioco del 15 e altri puzzles che periodicamente ritornano di moda.

Le regole sono molto semplici e occorre soltanto una matita e un foglio di carta. Si gioca su una tabella di nove per nove caselle in ognuna delle quali si deve inserire una cifra, da uno a nove. Ogni riga e ogni colonna deve contenere tutte le cifre da uno a nove senza ripetizioni. Condizione ulteriore, e questa è la novità, anche ogni blocco di caselle tre per tre, contrassegnato da linee più marcate, deve contenere le nove cifre, senza ripetizioni. Il Sudoku si presenta con una parte delle cifre già inserite nelle caselle (vedi figura 1). Per essere un vero Sudoku, deve inoltre avere un’unica soluzione. Richiede normalmente dai dieci minuti alla mezz’ora per essere risolto. Il nome originale del gioco, lanciato vent’anni fa dalla Nikoli, una casa editrice giapponese specializzata in giochi, era Suji wa dokushin ni kagiru ovvero “Numeri limitati ad una sola persona”, un nome sintetizzato in Sudoku, “Numeri unici”.

 

Figura 1: Raffigurazione di un sudoku come si presenta al giocatore e la usa soluzione.

Per risolvere un Sudoku, esistono diverse tecniche a seconda della difficolta’ del Sudoku stesso. Una delle tecniche piu’ semplici e’ quella della “Singola posizione”.

Si sceglie una riga, una colonna o un box (il quadrato 3x3) e si analizzano i numeri che ancora non sono stati inseriti. A causa della presenza dei numeri iniziali, le posizioni dove poter inserire un nuovo numero sono limitate. Spesso ci sono 2 o 3 celle dove poter inserire un numero ma se si e’ fortunati ce ne sara’ solo una. Per esempio nel sudoku della figura 2, scegliendo la riga verde si vede subito che il numero 7 puo’ essere inserito solo sull’ultima celle verde verso destra.

Questo perche’ in qualsiasi altra cella verde lo avremmo inserito avrebbe generato delle colonne con due cifre 7.

 Figura 2: Tecnica della singola posizione.

Un'altra tecnica semplice e’ quella del “singolo candidato”. In questo caso ce' bisogno di una matita per scrivere in ogni cella i possibili candidati, esaminando le colonne, righe e box circostanti. Nel caso in cui il candidato e’ unico, immediatamente puo’ essere associato alla cella. In figura 3, viene mostrato un esempio di questa tecnica.

 Figura 3: Tecnica del singolo candidato (da sinistra verso destra).

Nella cella indicata in verde nel sudoku di centro, l’unico candidato e’ il 2, mentre nella cella sopra quella contenente il numero 8, i possibili candidati sono 1 e 2. A destra viene mostrato il sudoku dopo l’inserimento di tutti i candidati. Si vede immediatamente che, ci sono 3 celle (in verde) dove c’e’ un unico candidato che quindi puo’ essere associato definitivamente alla cella.

Esiste una tecnica che non dice quale numero inserire in una cella, ma aiuta invece a determinare quali sono le celle dove non e’ possibile inserire un numero. Con l’esempio riportato in figura 4, e’ facile capire come funziona questa tecnica chiamata la tecnica delle linee candidate.

 Figura 4: Tecnica della singola linea (da sinistra verso destra).

Nel quadrato indicato in verde ci sono due possibili celle (indicate in verde piu’ scuro) dove poter inserire il numero 4. Questo automaticamente fa si che e’ possibile rimuovere qualsiasi altro 4 lungo la colonna individuata dai due 4 del box in basso a sinistra come mostrato in figura 4 nelle ultime due griglie a destra.

Esistono altre tecniche simili che qui non vedremo.

Ma nel caso in cui il Sudoku sia particolarmente complicato quale tecnica usare? Ce ne sono alcune che sono molto semplici da capire ma complicate da applicare. Partiamo con la prima, la cosiddetta tecnica delle “catene forzate”. Per applicarla e’ necessario avere a disposizione piu’ di un foglio per prendere appunti.

   Figura 5: Tecnica della catena forzata (da sinistra verso destra).

Osservando la figura 5, si capisce in che modo la scelta del valore 1 nella cella C3R1 (colonna terza e riga 1) forza il valore della cella C1R4 a 5. Infatti nel primo passaggio la scelta iniziale del 1, forza il valore 4 nella cella C3R4, che a sua volta forza il valore 7 nella cella C6R4 e quindi il valore 5 nella cella C1R4.

Si ripete poi la stessa operazione ma anziche’ partire col numero 1, si parte col numero 2 (vedi figura 6).

 Figura 6: Tecnica della catena forzata (da sinistra verso destra).

In questo caso la catena che viene fuori e’ molto lunga, ma alla fine forza sempre il numero 5 nella cella C1R4. Poiche’ due diverse scelte portano allo stesso numero nella cella C1R4 questo significa che il 5 e’ il numero da associare a questa cella.

La seconda tecnica normalmente utilizzata per risolvere Sudoku complessi e’ quella che va sotto il nome di X-Wing. Osserviamo la figura 7, partendo dalla riga 4 e 9 dove abbiamo 4 celle con il 6 un possibile candidato.

   Figura 7: Tecnica X-Wing

Il trucco per capire la tecnica del X-Wing e’ quello di immaginare cosa succederebbe se uno scegliesse il 6 in una di queste quattro celle. Se scegliamo il 6 in C3R4 questo implica che non e’ possibile avere lo stesso numero in C9R4 e C3R9 come si puo’ vedere dalla griglia centrale in alto della figura 7. Questa scelta forza la cella C9R9 ad avere 6 come candidato. In altre parole un 6 nella cella in alto a sinistra del quadrato iniziale (vedi griglia in basso a sinistra) forza lo stesso valore nella cella in basso a destra. Esattamente con la stessa logica, un 6 nell’angolo in alto a destra del quadrato dovrebbe forzare lo stesso valore nella cella in basso a sinistra (vedi griglia centrale in basso della figura 7). Detto cio’ e’ chiaro che non e’ possibile avere altri 6 nelle due colonne C3 e C9. Questo ci permette di cancellare quasiasi numero 6 che compare come possibile candidato. Nell’esempio di figura 7, e’ possibile rimuovere il 6 da due celle della colonna C9, che lascia la cella C9R1 con un 8.
A causa della grande popolarita’ del Sudoku, diversi matematici e scienziati del computer hanno lavorato su diverse questioni emerse da questo gioco. La prima di queste riguarda il possibile numero di griglie. In altre parole, stabilire qual’e’ il numero di griglie possibili di Sudoku che possono essere create o equivalentemente il numero di modi in cui e’ possibile riempire una griglia 9x9 con i numeri da 1 a 9 soddisfando le regole del Sudoku.

Per rispondere a tale domanda e’ necessario utilizzare tutte le possibili permutazioni e le proprieta’ di simmetria della griglia del Sudoku.

Bertram Felgenhauer del Dipartimento di Scienza dei computer dell’Universita’ di Dresda e Frazer Jarvis del Dipartimento di Matematica dell’Universita’ di Sheffield in Inghilterra, usando la forza-bruta dei computer sono arrivati a calcolare il numero di griglie valide di Sudoku. Un numero veramente grande: 6670903752021072936960 (circa 6.67*10²¹). Senza considerare le regole del Sudoku elencate all’inizio del capitolo, il numero di possibili griglie sarebbe 9⁸¹ . Ovviamente per contare le possibili griglie questo numero dovrebbe essere ridotto eliminando tutte quelle configurazioni che non soddisfano le regole.

Se consideriamo un qualsiasi blocco del Sudoku, questo puo’ avere 9! (362880) possibili configurazioni. I possibili modi con cui arrangiare la “banda” in alto (l’insieme dei tre blocchi da 3x3 celle) saranno dati dal prodotto di 9! del primo blocco per il numero di modi in cui e’ possibile arrangiare il blocco 2 della banda superiore e il numero di modi in cui e’ possibile arrangiare il blocco 3 (quello a destra in alto della griglia del Sudoku).

Questo prodotto e’ uguale a 6.67*10²¹. Comunque se consideriamo la simmetria della griglia del Sudoku questo numero e’ destinato a diminuire. Per simmetrie, intendiamo quelle operazioni che quando applicate alla griglia del Sudoku, esse creano un’altra griglia che e’ essenzialmente equivalente all’originaria. Per prima cosa etichettiamo una griglia del Sudoku come riportato in figura 8.

 

 Figura 8: Griglia del Sudoku etichettata con le lettere.

La colonna ADG e’ chiamata una “pila”, mentre la riga ABC e’ detta una “striscia”.La selezione di specifici valori per uno qualsiasi dei quadrati e’ conosciuta come “Ri-etichettatura”. L’arrangiamento delle cifre da 1 a 9 nel blocco A, e’ un esempio di operazione di ri-etichettatura. Oltre questa operazione, sono possibili anche le:

· Permutazioni delle “strisce”

· Permutazioni delle “pile”

· Permutazioni delle colonne all’interno delle “pile”

· Permutazioni delle righe all’interno delle “strisce”

· Riflessione o rotazione della griglia.

Frazer Jarvis e Ed Russel, in un lavoro intitolato “Mathematics of Sudoku”, hanno individuato 3359323 simmetrie. Una di queste e’ quella rappresentata in figura 9, dove la griglia riportata rimane praticamente la stessa se sottoposta ad una rotazione di 90 gradi e di ri-etichettatura 1—>3—>9—>7—>1 e 2—>6—>8—>4—>2. Il 5 rimane fisso.

 Figura 9: Griglia di Sudoku che rimane la stessa in seguito ad operazione di rotazione e ri-etichettatura

Tenendo conto di tutte le simmetrie, gli autori sono arrivati a stabilire che tutte le possibili griglie differenti del Sudoku sono 5472730538.

Normalmente, il Sudoku deve avere una sola soluzione, altrimenti il puzzle non e’ valido. Per essere sicuri di cio’, i puzzles sono presentati con un numero di cifre gia’ presenti nella griglia iniziale, lasciando al giocatore la deduzione delle rimanenti cifre da inserire nelle celle libere. Al momento il migliore risultato ottenuto sul minimo numero richiesto nella griglia iniziale e’ di 17 cifre. Questo e’stato ottenuto dal professore Gordon Royle dell’Universita’ dell’Australia. Attualmente non si sa se con 16 cifre iniziali il Sudoku ammette una singola soluzione. Tutte le griglie con 17 entrate iniziali, vengono chiamate i Sudoku minimi. Al momento si conoscono 47793 diversi Sudoku minimi.

Per analizzare il gioco del Sudoku e’ possibile anche utilizzare la teoria dei grafi. E’ quello che hanno fatto Agnes M. Herzberg e M. Ram Murty in un loro lavoro apparso sul giornale Notices of the AMS di Giugno/Luglio 2007. E’ possibile pensare alla griglia del Sudoku, come agli 81 nodi di un grafo. Ogni cifra da 1 a 9 puo’ essere colorato in modo diverso, e due nodi possono essere connessi se e solo se le due celle che essi rappresentano si trovano nella stessa riga, colonna o quadrato 3x3. Poiche’ nessuna riga, colonna o blocco 3x3 puo’ contenere piu’ di una volta lo stesso numero, questo significa che il grafo non avra’ connessioni tra nodi dello stesso colore. Nel linguaggio della teoria dei grafi, un grafo colorato senza connessioni tra nodi dello stesso colore si chiama un “grafo colorato proprio”.

Quello che i giocatori di Sudoku, quindi, fanno tutti i giorni, e’ cercare di estendere un grafo parzialmente-colorato (la griglia iniziale) ad un grafo colorato proprio.
Grazie a questa analogia tra Sudoku e grafi, Herzberg e Murty hanno utilizzato le tecniche dei grafi per provare alcuni teoremi riguardanti il Sudoku.

Per esempio, hanno provato che il numero di modi per trasformare un grafo parzialmente colorato e’ dato da un polinomio. Se il valore di questo polinomio e’ zero per una certa griglia Sudoku, allora il puzzle non ha soluzione. Se il valore e’ 1, allora il puzzle ha una sola soluzione e cosi via. Essi hanno anche dimostrato che affinche’ un Sudoku abbia un’unica soluzione, ci devono essere almeno 8 delle 9 cifre presenti nella griglia iniziale come entrate. Se vengono dati solo 7 numeri, allora il puzzle ha almeno due soluzioni.

Tenendo presente, quindi, il risultato di G. Royle, per avere un’unica soluzione dobbiamo garantirci che nella griglia iniziale ci siano almeno 17 numeri e che questi siano rappresentati da 8 diverse cifre. Per esempio con una sequenza del tipo:

1, 2, 3, 4, 5, 6, 9, 2, 2, 3, 4, 1, 1, 9, 4, 7, 2

come entrate iniziali il puzzle avra’ sicuramente una soluzione unica.

E’ possibile pensare che nel caso ci sia un numero di entrate superiore a 17, sia abbastanza probabile avere un’unica soluzione del Sudoku. E invece non e’ sempre cosi. L’articolo di Herzberg e Murty, riporta un esempio di una griglia con 29 numeri iniziali che ha due differenti soluzioni. Niente male per un rompicapo come il Sudoku. Un altro ricercatore, David Eppstein dell’Universita’ della California, ha applicato anche lui la teoria dei grafi per costruire nuovi metodi di soluzione.

Supponiamo di avere un Sudoku che e’ stato risolto parzialmente. Assegniamo ad ogni cella vuota un nodo del grafo, e connettiamo i nodi con archi etichettati coi numeri candidati per la cella. Eppstein definisce un ciclo non ripetitivo, un tour chiuso che non ha due archi (edge) consecutivi con la stessa etichetta e ciclo ripetitivo uno in cui e’ possibile trovare due archi consecutivi con la stessa etichetta. I connettori consecutivi sono quelli che condividono uno stesso nodo (per esempio A e B sotto).

Vediamo come funziona il metodo nel caso di cicli non ripetitivi. In questo caso, per qualsiasi cella C del ciclo, con due archi etichettati con A e B che insistono su di essa, il valore di C puo’ essere solo A o B. Nell’esempio della figura 10, la cella C e’ quella sulla sinistra in basso della griglia. Poiche’ i due archi che insistono su questa cella hanno come numeri 2 e 3 significa che la cella C dovra’ avere uno di questi due numeri. La griglia in alto a sinistra e’ il Sudoku parzialmente completato con altri metodi. In basso a destra invece viene mostrato il puzzle risolto.

 Figura 10: Metodo del ciclo non ripetitivo di Eppstein.

In caso di ciclo ripetitivo, se ad un nodo confluiscono due archi con la stessa etichetta, la cella associata al nodo del grafo non puo’ che avere come valore l’etichetta delle connessioni. Nell’esempio di figura 11, il nodo indicato in nero non puo’ che avere come valore il numero 4.

Figura 11: Metodo del ciclo ripetitivo di Eppstein.

La camminata del cavallo ovvero la matematica della scacchiera

 

  Nel gioco degli scacchi, il cavallo e’ uno dei pezzi a disposizione dei giocatori. Insieme all’alfiere e’ uno dei cosiddetti “pezzi leggeri” in contrapposizione alla regina e la torre che invece vengono chiamati “pezzi pesanti”. La mossa del cavallo puo’ essere descritta come un passo in orizzontale o in verticale seguito da un passo in diagonale in direzione opposta alla casa d’origine. Nella figura 1, sono indicate le mosse ammesse nell’ipotesi che il cavallo occupi una posizione centrale.

 

Figura 1. Le mosse del cavallo.

Fin dall’antichita’ c’e’ stato un grande interesse per quello che va sotto il nome del puzzle del tour del cavallo: determinare  la sequenza di movimenti fatti su una scacchiera da un cavallo in modo che ogni quadrato venga visitato una ed una sola volta.

Esiste una soluzione a questo puzzle? E se si, quanti possibile tour ci sono?

I primi risultati furono riportati in un manoscritto arabo dall’autore Abu Zakaria Yahy intorno al 900 dc (vedi figura 2). Tra le due soluzioni mostrate in figura 2, c’e’ una notevole differenza. Infatti il punto iniziale per la soluzione sulla sinistra non puo’ essere raggiunto dal punto finale con una mossa del cavallo, mentre questo e’ vero per la soluzione di destra. Nel caso della soluzione di destra si parla di tour del cavallo chiuso. In figura 3, vengono riportati due esempi di tours chiusi.

 

Figura 2. Due soluzioni per il puzzle del cavallo.

 

Figura 3. Due tours chiusi.

La prima analisi matematica di questo puzzle, comunque, fu eseguita nel 1759 dal grande Eulero. L’accademia delle scienze di Berlino, aveva istituito un premio di 4000 franchi per chi riusciva a dare una soluzione matematica del puzzle, premio che molto probabilmente Eulero non prese mai in quanto essendo il direttore del dipartimento di matematica, non era tra gli eleggibili. In figura 4, vengono riportate alcune soluzioni trovate da Eulero. Partendo da qualsiasi quadrato lungo il cammino si otterra’ sempre un tour chiuso.

 

Figura 4. Alcune soluzioni trovate da Eulero.

Ma quanti tours esistono? Questo numero e’ sorprendentemente grande. In effetti e’ cosi grande che un semplice conteggio e’ al di fuori della portata dei computer piu’ veloci. Il problema e’ stato comunque affrontato in modo diverso da Martin Lobbing e Ingo Wegener che nel 1995 comunicarono che, il numero possibile di tours del cavallo era uguale a 33439123484294.

Nel 1997, Brendan McKay, usando un metodo diverso, ha stabilito che il numero possibile di tours e’ dato da 13267364410532, che se anche  piu’ piccolo di quello precedente rimane comunque un numero elevatissimo.

Esistono anche tours magici di cavalli, nel senso che se ogni passo del cammino del cavallo viene numerato, il quadrato risultante e’ magico, cioe’ la somma di tutte le righe, di tutte le colonne e delle diagonali principali e’  uguale ad una costante (vedi per esempio la figura 5).

 

Figura 5 . Due tours magici.

I tours magici non sono possibili su scacchiere n x n con n dispari. Il primo tour magico fu pubblicato nel 1848 dal suo scopritore, William Beverley (vedi figura 6) anche se si tratta nella realta’ di un tour semimagico in quanto, la somma delle diagonali non e’ uguale a 260 che e’ invece la somma delle righe e delle colonne.

 

Figura 6 . Il primo tour magico scoperto da W. Beverley.

Il quadrato di Beverley ha delle proprieta’ interessanti. Per esempio, come mostrato in figura 7 a sinistra, in ogni quadrante, la somma dei numeri corrisponde a 520 e la somma di ognuna delle righe e delle colonne equivale a 130. Inoltre la somma dei numeri in ogni quadrato 2x2 e’ uguale a 130 (figura 7 a destra).

 

Figura 7. Quadrato di Beverley

Solo dopo 62 giorni di calcoli, nel 2003 e’ stato mostrato che per una scacchiera 8x8 non esiste nessun tour magico, mentre ne esistono in totale 140 di semimagici.

Nel diciannovesimo secolo, H.C. Warnsdorff presento’ un metodo pratico per costruire dei tours del cavallo. Lo scopo era quello di evitare di creare delle estremita’ morte, cioe’ quadrati da cui il cavallo non puo’ piu’ andare avanti senza visitare un quadrato gia’ visitato in anticipo. Per questa ragione, prima di ogni mossa vengono analizzati i possibili quadrati in cui muoversi nel passo successivo, ed una volta contato il numero di nuove scelte possibili, ci si muove nel quadrato con il numero minore.

La regola di Warnsdorff, genera delle soluzioni, ma non tutte le possibili soluzioni. In figura 8, viene riportato un inizio di tour ottenuto con la regola di Warnsdorff.

 

Figura 8. La regola di Warnsdorff al lavoro

Oggi, comunque, la tecnica piu’ utilizzata per trovare i tours del cavallo su scacchiere molto grandi e’ quella della decomposizione, cioe’ quella di suddividere la scacchiera in rettangoli piccoli per i quali la soluzione e’ gia' conosciuta. Queste soluzioni sono, quindi, combinate insieme per ottenere tutti i possibili cammini del cavallo. In figura 9, viene riportato un possibile cammino del cavallo per una scacchiera 60x60.

Figura 9. Cammino del cavallo per una scacchiera 60x60 ottenuto col metodo della decomposizione.

I tours del cavallo possono anche essere rappresentati tramite i grafi, dove ogni nodo rappresenta i quadrati della scacchiera e le connessioni (o edge) corrispondono ad una mossa legale del cavallo (vedi figura 10).

 

Figura 10. Grafi per tours del cavallo su scacchiere di diverse dimensioni nxn.

Si puo’ dimostrare che se il grafo associato al movimento del cavallo su una scacchiera mxn ha un cammino Hamiltoniano allora esiste per certo un tour, e se il grafo ha un ciclo Hamiltoniano allora il tour e’ chiuso. Vediamo cosa si intende per grafo Hamiltoniano. Un grafo si dice contenere un cammino Hamiltoniano quando e’ possibile visitare tutti i vertici del grafo una e una sola volta. Per esempio in figura 10 , si vede chiaramente, che su una scacchiera 3x3 non esiste nessun tour del cavallo, in quanto non c’e’ un cammino Hamiltoniano.

Si parla invece di ciclo Hamiltoniano quando nel cammino Hamiltoniano esiste un arco che congiunge l’ultimo vertice con il primo, realizzando cosi un ciclo che visita tutti i vertici per poi ritornare al punto di partenza (vedi figura 11).

 

Figura 11. Grafo contenente un ciclo Hamiltoniano indicato con le frecce in grassetto.

Per ogni classe di grafi e’ possibile calcolare il numero di possibili cammini Hamiltoniani come nel caso della classe mostrata in figura 12. Si tratta di grafi completi con n vertici. Un grafo si dice completo quando per ogni coppia di vertice esiste una connessione o edge. La sequenza dei possibili cammini Hamiltoniani per la classe procede in questo modo (considerando anche il verso):

0, 2, 6, 24, 120, 720, ...

 

Figura 12. Classe dei Grafi cosiddetti completi.

Il numero di connessioni in un tour del cavallo su una scacchiera nxn e’ dato dalla seguente formula:

4(n-2)(n-1)

che equivale a 8 volte i numeri triangolari.

I cammini del cavallo su una scacchiera possono essere utilizzati anche per tassellare il piano. Usando i 4 insiemi di 16 movimenti illustrati nella figura 13 e’ possibile costruire 4 poligoni, che insieme possono tassellare il piano.

 

Figura 13. I 4 poligoni colorati ottenuti con i cammini del cavallo e la tassellazione del piano.