Percorso del cavallo

Il percorso del cavallo è un problema matematico riguardante lo spostarsi di un cavallo su una scacchiera. Il cavallo è posizionato sulla scacchiera vuota e, spostandosi secondo le regole degli scacchi, deve occupare ogni casa esattamente una volta. Un percorso del cavallo si dice "chiuso" se l'ultima casa su cui si posiziona il cavallo è vicina alla casa da cui è partito, in modo tale che il cavallo, dalla posizione finale, possa compiere da capo lo stesso percorso (ad esempio, se il cavallo inizia in d8 e conclude il suo percorso in f7). In caso contrario il percorso del cavallo è detto "aperto". Il numero esatto di possibili percorsi del cavallo aperti è ancora sconosciuto. Le variazioni del problema del percorso del cavallo prevedono scacchiere di dimensioni diverse dalla classica 8x8, e anche di forma rettangolare.

Il problema del percorso del cavallo è un esempio del più generale "problema del cammino hamiltoniano", nella teoria dei grafi. Similmente, trovare un percorso del cavallo chiuso è un esempio del "problema del ciclo hamiltoniano". Notare, tuttavia, che, a differenza del generale problema del cammino hamiltoniano, il problema del percorso del cavallo può essere risolto in tempo lineare.^[1]

Su una scacchiera 8x8, ci sono esattamente 26.534.728.821.064 percorsi chiusi "diretti" (due percorsi lungo lo stesso cammino che procedono in direzioni opposte sono contati separatamente, essendo rotazioni e riflessioni).^[2][3][4] Il numero dei percorsi chiusi "indiretti" è la metà di questo numero, dato che ogni percorso può essere tracciato all'inverso. Ci sono 9.862 percorsi chiusi indiretti su una scacchiera 6x6.^[5] Non esistono percorsi chiusi per scacchiere più piccole, ad eccezione del caso 1x1 (questo è un corollario del teorema seguente).

Per ogni scacchiera m×n, con m ≤ n, un percorso del cavallo chiuso è sempre possibile a meno che una o più delle seguenti condizioni sia soddisfatta:

1. m e n sono entrambi dispari; m e n sono entrambi diversi da 1
2. m = 1, 2 o 4; m e n sono entrambi diversi 1
3. m = 3 e n = 4, 6 o 8.

La condizione 1 impedisce l'esistenza di percorsi chiusi per una questione di parità e colore. In una scacchiera standard a case bianche e nere, il cavallo si dovrà muovere necessariamente sia da una casa bianca a una nera che da una casa nera a una bianca. Perciò, in un percorso chiuso, il cavallo dovrà visitare lo stesso numero di case bianche e nere, e il numero totale di case visitate dovrà quindi essere pari. Però, se m e n sono entrambi dispari, il numero totale di case della scacchiera (ovvero il prodotto m×n) è dispari (ad esempio, in una scacchiera 5x5 ci sono 13 case di un colore e 12 di un altro colore), perciò non può esistere un percorso chiuso. I percorsi aperti possono invece esistere (con l'unica eccezione del caso 1x1).

La condizione 2 afferma che, se il lato minore conta 1, 2 o 4 case, allora nessun percorso chiuso è possibile.

Quando m = 1 o 2, nessun percorso chiuso è possibile perché il cavallo non sarebbe in grado di raggiungere ogni casa (ancora una volta, con l'eccezione del caso 1x1). Può essere verificato, utilizzando dei colori, che neanche una scacchiera 4×n può avere un percorso chiuso.

Cominciamo assumendo che una scacchiera 4×n abbia un percorso del cavallo. Siano ${\displaystyle A_{1}}$ l'insieme delle case che sarebbero nere e ${\displaystyle A_{2}}$ l'insieme delle case che sarebbero bianche, se fossero colorate secondo lo schema della scacchiera bianca-nera. Consideriamo la figura a destra. Siano ${\displaystyle B_{1}}$ l'insieme delle case verdi e ${\displaystyle B_{2}}$ l'insieme delle case rosse. C'è lo stesso numero di case verdi e case rosse. Notiamo che, a partire da una casa in ${\displaystyle B_{1}}$, il cavallo dovrà saltare su una casa in ${\displaystyle B_{2}}$. E, dato che il cavallo dovrà visitare ogni casa una volta, quando è in ${\displaystyle B_{2}}$ dovrà poi poter passare ad una casa in ${\displaystyle B_{1}}$ (altrimenti il cavallo dopo dovrà passare su due case in ${\displaystyle B_{1}}$).

Se seguissimo l'ipotetico percorso del cavallo, troveremmo una contraddizione.

1. La prima casa in cui il cavallo andrà sarà una casa di ${\displaystyle A_{1}}$ e ${\displaystyle B_{1}}$. Se non fosse così, basta cambiare le definizioni di ${\displaystyle B_{1}}$ e ${\displaystyle B_{2}}$ affinché ciò sia vero.
2. La seconda dovrà essere una casa di ${\displaystyle A_{2}}$ e ${\displaystyle B_{2}}$.
3. La terza dovrà essere una casa di ${\displaystyle A_{1}}$ e ${\displaystyle B_{1}}$.
4. La quarta dovrà essere una casa di ${\displaystyle A_{2}}$ e ${\displaystyle B_{2}}$.
5. E così via.

Ne consegue che ${\displaystyle A_{1}}$ ha le stesse case di ${\displaystyle B_{1}}$, e ${\displaystyle A_{2}}$ ha le stesse case di ${\displaystyle B_{2}}$. Ma questo ovviamente non è vero, dato che le case rosse e verdi mostrate sopra non sono le stesse dello schema di una scacchiera; l'insieme delle case rosse non è lo stesso dell'insieme delle case nere (o bianche, se per quello).

Perciò, la nostra ipotesi di sopra era falsa e quindi non c'è alcun percorso chiuso per alcuna scacchiera 4×n, per ogni n.

La condizione 3 può essere provata per tentativi: nel costruire un percorso chiuso su una scacchiera 3x4, 3x6 o 3x8 ci accorgeremmo che ciò è impossibile. Si può dimostrare, per induzione (con uno schema ripetuto), che una scacchiera 3×n, con n pari e maggiore di 8, ha al contrario dei percorsi chiusi.

Dimostrare le tre condizioni precedenti, però, non basta a dimostrare il teorema nella sua interezza. Infatti, è ancora da dimostrare che tutte le scacchiere rettangolari che non soddisfano le tre condizioni sopra elencate hanno dei percorsi del cavallo chiusi.^[6]

Il percorso del cavallo, o anche conosciuto come il cavaliere di Euler, fu conosciuto da molto tempo nella storia. Verso l'anno 840, il giocatore e teorico arabo di Scacchi al-Adli ar-Rumi ne aveva già dato una soluzione.

• (EN) Martin Gardner, Knight of the Square Table, in Mathematical Magic Show, 1990, pp. 188-203.
• (EN) Richard W. Henderson, Eugene Roger Apodaca, A Knight of Egodeth: Zen Raptured Quietude, 2008, ISBN 978-0-9797630-0-7.

• George Koltanowski

• Wikimedia Commons contiene immagini o altri file sul percorso del cavallo

• (EN) Eric W. Weisstein, Percorso del cavallo, su MathWorld, Wolfram Research.
• (EN) Warnsdorff's Rule, su warnsdorff.com.
• Dan Thomasson, (EN) The Knight's Tour
• Sequenza A001230 dell'On-Line Encyclopedia of Integer Sequences
• Ira Pohl, (EN) A Method for Finding Hamilton Paths and Knight's Tour

Portale Matematica

Portale Scacchi