Il Problema del Salto del Cavallo (Knight’s Tour)
Questo articolo è basato principalmente sulle risorse di mayhematics.com, un sito che consiglio caldamente di visitare se l’argomento vi incuriosisce.
Il Knight’s Tour è uno di quei problemi che sembrano semplici ma nascondono una profondità sorprendente. L’idea di base è questa: prendi un cavallo degli scacchi, mettilo su una scacchiera, e fallo muovere in modo che visiti ogni casa esattamente una volta. Fine. Eppure dietro questa regola elementare si nascondono migliaia di anni di storia, teoremi eleganti e persino arte astratta.
Origini Storiche
La storia del Knight’s Tour è molto più antica di quanto si potrebbe pensare.
Già in Cina, intorno al 2200 a.C., erano noti quadrati magici 3×3 i cui numeri tracciavano percorsi simili a un tour del cavallo. Nel mondo islamico, tra l'840 e il IX secolo, manoscritti di al-Adli e Ali C. Mani riportano tour completi su scacchiere 8×8, anticipando molte soluzioni successive.
Il riferimento più antico conosciuto si trova però nel Kavyalankara, un’opera sanscrita sulla poetica. Qui il percorso del cavallo su una mezza scacchiera viene presentato come una figura poetica chiamata turagapadabandha (“disposizione nei passi di un cavallo”). Poiché il sistema di scrittura sanscrito è sillabico, ogni sillaba rappresenta una casa della scacchiera e il verso può essere letto seguendo il movimento del cavallo — un po’ come una poesia che è anche un puzzle.
In India, nel IX secolo, il poeta Rudrata descrisse tour parziali del cavallo codificati in versi, i cosiddetti cryptotours. Nel XIV secolo, Vedanta Desika compose nel suo Paduka Sahasram due versi consecutivi di 32 lettere ciascuno: il secondo verso può essere derivato dal primo eseguendo un percorso del cavallo su una scacchiera 4×8. Si crede che abbia composto l’intera opera di 1.008 versi in una sola notte come sfida — il che è già di per sé impressionante, con o senza il cavallo.
Nel XII secolo, Somesvara III nel Manasollasa propose tour simili. Tra XIII e XIV secolo emergono i primi esempi europei, come il manoscritto della King’s Library e il Bonus Socius di Nicolas de Nicolai. Nel XVII secolo, Frénicle de Bessy catalogò quadrati magici 4×4 che includevano percorsi geometrici del cavallo.
Il Problema Formale
La prima analisi matematica seria è attribuita a Eulero, che ne scrisse in una lettera a Christian Goldbach nel 1757:
“I found myself one day in a company where, on the occasion of a game of chess, someone proposed this question: To move with a knight through all the squares of a chess board, without ever moving two times to the same square, and beginning with a given square.”
— Eulero, “Solution d’une question curieuse qui ne paroit soumise à aucune analisi”
In termini moderni, il problema si traduce nella ricerca di un cammino o ciclo hamiltoniano in un grafo: i vertici sono le case della scacchiera, gli archi sono le mosse legali del cavallo.
Esistono due tipi di soluzione:
Percorso Aperto: il cavallo attraversa tutta la scacchiera — ogni casella una e una sola volta — senza tornare al punto di partenza.
Enumerazione delle mosse del cavallo che compongono un Tour Aperto
Traiettoria precedente mostrata senza scacchiera
Percorso Chiuso (o rientrante): il cavallo termina in una casa da cui può tornare alla partenza con un’unica mossa, chiudendo il ciclo. Le case numerate 1 e 64 sono quindi separate da esattamente una mossa di cavallo.
Enumerazione delle mosse del cavallo che compongono un Tour Chiuso
Traiettoria precedente mostrata senza scacchiera
Grafi, Complessità e Come Si Risolve
Il collegamento con i problemi hamiltoniani
Il problema si riduce a trovare un cammino hamiltoniano nel grafo del cavallo $G(m,n)$. Questo grafo è bipartito — le case bianche e nere si alternano a ogni mossa — e questa struttura regolare è proprio ciò che lo rende trattabile, a differenza di un grafo arbitrario.
In teoria dei grafi, il problema hamiltoniano generico è NP-hard: non si conosce un algoritmo polinomiale che funzioni su qualsiasi grafo. Ma il grafo del cavallo non è un grafo qualsiasi, e questo fa tutta la differenza. Sulla sola scacchiera 8×8 esistono oltre $19.5 \times 10^{15}$ tour distinti — eppure il problema si risolve in tempo lineare.
Complessità con l’euristica di Warnsdorff
Sia $N = m \cdot n$ il numero totale di celle. Per ogni cella visitata dal cavallo, tutte le operazioni sono a costo costante:
- Controllo delle mosse possibili: al massimo 8 mosse, ogni verifica è $O(1)$.
- Calcolo del grado delle celle candidate: per ciascuna mossa valida si contano le mosse future → $O(1)$.
- Selezione della mossa minima: ordinamento su al massimo 8 elementi → $O(1)$.
Ripetendo per ognuna delle $N$ celle:
$$\text{Complessità totale} = N \cdot O(1) = O(N) = O(m \cdot n)$$
Il problema appartiene alla classe P — risolvibile in tempo polinomiale (anzi, lineare). Attenzione però: generalizzando a scacchiere $n \times n$ con buchi o ostacoli, il problema può tornare NP-completo.
Come si trova concretamente una soluzione?
- Euristica di Warnsdorff (1823): muovi sempre il cavallo verso la casa con il minor numero di mosse successive disponibili. Semplice da implementare, efficiente in pratica.
- Divide-et-Impera: si divide la scacchiera in parti più piccole, si costruisce un tour su ciascuna e poi si collegano. Funziona in tempo lineare per la maggior parte delle scacchiere rettangolari.
- Reti Neurali: ogni mossa legale è un neurone; la rete converge verso uno stato che codifica la soluzione. Meno usato in pratica, ma interessante come approccio.
Quando Esiste un Tour? I Teoremi Principali
Teorema di Schwenk (1991) — tour chiusi
Allen J. Schwenk ha risposto in modo definitivo alla domanda: su quali scacchiere $m \times n$ esiste un tour chiuso? La risposta è: quasi sempre, tranne in tre casi precisi.
Per ogni scacchiera $m \times n$ con $m \leq n$, un tour chiuso non esiste se e solo se vale almeno una di queste condizioni:
-
$m$ e $n$ sono entrambi dispari — il numero totale di case è dispari, e un ciclo hamiltoniano in un grafo bipartito richiede necessariamente un numero pari di vertici.
-
$m = 1, 2$ oppure $4$ — la scacchiera è troppo stretta per le traiettorie a L del cavallo. Per $m = 4$, Louis Posa ha dimostrato l’impossibilità con un elegante argomento di ricolorazione che produce una contraddizione con la bipartizione del grafo.
-
$m = 3$ e $n = 4, 6$ oppure $8$ — dimensioni troppo ridotte. In una scacchiera 3×6, la rimozione di soli due vertici produce tre componenti connesse separate, il che è incompatibile con l’esistenza di un ciclo hamiltoniano.
Tour aperti
Cull et al. e Conrad et al. hanno completato il quadro per i tour aperti: su qualsiasi scacchiera con dimensione minore almeno pari a 5 esiste sempre un tour. Le uniche eccezioni sono:
- $m = 1$ oppure $2$,
- $m = 3$ e $n = 3, 5$ oppure $6$,
- $m = 4$ e $n = 4$.
Tour Magici
Cosa sono
Un tour si dice “magico” se i numeri delle mosse $(1, 2, \ldots, 64)$ formano un quadrato magico: ogni riga e ogni colonna sommano alla costante $260$. È un vincolo molto più stringente rispetto alla semplice visita di tutte le case.
I primi esempi storici risalgono all’Ottocento:
- 1848 — William Beverly pubblica il primo tour magico aperto.
- 1849 — Karl Wenzelides pubblica il primo tour magico chiuso.
Il Teorema di Jelliss — impossibilità su certi tipi di scacchiere
George Jelliss ha dimostrato che un tour magico è impossibile su qualsiasi scacchiera il cui lato sia della forma $4n+2$ — quindi 6×6, 10×10, 14×14 e così via.
Il motivo tecnico è nel Lemma di Jelliss: in un tour magico, il numero di entrate della forma $4k+2$ o $4k+3$ in ogni riga o colonna deve essere pari. Sulle scacchiere $4n+2$ questa condizione non può essere soddisfatta, il che chiude la questione.
Quanti ne esistono sulla scacchiera 8×8?
Nel 2003, un progetto di calcolo distribuito ha risposto in modo definitivo: esistono esattamente 140 tour magici:
- 63 chiusi — il cavallo può tornare alla partenza,
- 77 aperti — ottenuti per differenza (140 − 63).
Tenendo conto degli 8 possibili orientamenti e della possibilità di numerare il percorso da entrambe le estremità, questi 140 tour danno origine a 2.240 diverse matrici aritmetiche.
Vale la pena sottolineare qualche limite ulteriore:
- Nessun tour magico è diagonalmente magico — le diagonali principali non sommano mai a 260. Confermato computazionalmente nel 2003.
- Nessun tour pan-diagonale esiste — la disparità tra numeri pari e dispari nelle diagonali lo rende impossibile.
- Nessuna simmetria oltre il secondo ordine — nessun tour 8×8 può avere simmetria laterale, diagonale o rotazionale superiore a 180°.
Enumerazione delle mosse di un Tour Magico, trovato da Jaenisch nel 1859
Traiettoria del Tour Magico precedente
Il Knight’s Tour come Arte
C’è un aspetto del Knight’s Tour che non è strettamente matematico ma vale la pena menzionare: i percorsi del cavallo, visualizzati come sequenze di linee su una griglia, producono composizioni grafiche sorprendentemente belle. Le traiettorie si intrecciano coprendo uniformemente lo spazio, e il risultato cambia radicalmente in base all’algoritmo usato: con Warnsdorff le curve tendono a essere regolari e distribuite uniformemente, con approcci meno guidati emergono grovigli più densi e apparentemente caotici. L’effetto si amplifica in modo notevole all’aumentare delle dimensioni della scacchiera.
Un Tour Aperto su una scacchiera 32×32
Un Tour Aperto su una scacchiera 100×100