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.