Percorso del cavallo

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca
Un Percorso del Cavallo aperto su una scacchiera.
Animazione di un Percorso del Cavallo su una scacchiera 5x5.
Il grafo del cavallo mostra tutti i possibili cammini per un percorso del cavallo su una scacchiera standard 8x8. I numeri su ogni nodo indicano il numero di possibili mosse che possono essere fatte da quella posizione.
Il percorso del cavallo risolto dal Turco, una fasulla macchina giocatrice di scacchi. Questa particolare soluzione è chiusa (circolare) e può essere completata da ogni punto del bordo della scacchiera.

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.

Teoria[modifica | modifica wikitesto]

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]

Percorsi chiusi[modifica | modifica wikitesto]

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

Teorema di Schwenk[modifica | modifica wikitesto]

Per ogni scacchiera m×n, con mn, 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.

Condizione 1[modifica | modifica wikitesto]

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

Condizione 2[modifica | modifica wikitesto]

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.

Il cavallo deve alternarsi fra case verdi e rosse.

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

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

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

Ne consegue che ha le stesse case di , e ha le stesse case di . 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.

Condizione 3[modifica | modifica wikitesto]

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.

Tutti gli altri casi[modifica | modifica wikitesto]

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]

Storia[modifica | modifica wikitesto]

Nel mondo arabo[modifica | modifica wikitesto]

Soluzione di al-Adli ar-Rumi

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.

Note[modifica | modifica wikitesto]

  1. ^ A. Conrad, T. Hindrichs, H. Morsy e I. Wegener, Solution of the Knight's Hamiltonian Path Problem on Chessboards, in Discrete Applied Mathematics, vol. 50, n. 2, 1994, pp. 125–134, DOI:10.1016/0166-218X(92)00170-Q.
  2. ^ Martin Loebbing; Ingo Wegener, The Number of Knight's Tours Equals 33,439,123,484,294 — Counting with Binary Decision Diagrams, in The Electronic Journal of Combinatorics, vol. 3, n. 1, 1996, pp. R5. Remark: The authors later admitted that the announced number is incorrect. According to McKay's report, the correct number is 13,267,364,410,532 and this number is repeated in Wegener's 2000 book.
  3. ^ Brendan McKay, Knight's Tours on an 8x8 Chessboard (ps), in Technical Report TR-CS-97-03, Department of Computer Science, Australian National University, 1997 (archiviato dall'url originale il 27 gennaio 2012).
  4. ^ Wegener, I., Branching Programs and Binary Decision Diagrams, Society for Industrial & Applied Mathematics, 2000, ISBN 0-89871-458-3.
  5. ^ (EN) Eric W. Weisstein, Knight's Tour, in MathWorld, Wolfram Research.
  6. ^ John J. Watkins, Across the Board: the Mathematics of Chessboard Problems, Princeton University Press, 2004, ISBN 0-691-11503-6.

Bibliografia[modifica | modifica wikitesto]

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

Voci correlate[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]