Percorso del cavallo

Da Wikipedia, l'enciclopedia libera.
Un Percorso del Cavallo aperto su di una scacchiera.
Animazione di un Percorso del Cavallo su di 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 sorgente]

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 sorgente]

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 sorgente]

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 sorgente]

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 sorgente]

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 A_1 l'insieme delle case che sarebbero nere e 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 B_1 l'insieme delle case verdi e 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 B_1, il cavallo dovrà saltare su una casa in B_2. E, dato che il cavallo dovrà visitare ogni casa una volta, quando è in B_2 dovrà poi poter passare ad una casa in B_1 (altrimenti il cavallo dopo dovrà passare su due case in 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 A_1 e B_1. Se non fosse così, basta cambiare le definizioni di B_1 e B_2 affinché ciò sia vero.
  2. La seconda dovrà essere una casa di A_2 e B_2.
  3. La terza dovrà essere una casa di A_1 e B_1.
  4. La quarta dovrà essere una casa di A_2 e B_2.
  5. E così via.

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

Condizione 3[modifica | modifica sorgente]

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 sorgente]

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 non soddisfano le tre condizioni sopra elecante hanno dei percorsi del cavallo chiusi.[6]

Note[modifica | modifica sorgente]

  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 in Technical Report TR-CS-97-03, Department of Computer Science, Australian National University, 1997.
  4. ^ Wegener, I., Branching Programs and Binary Decision Diagrams, Society for Industrial & Applied Mathematics, 2000. ISBN 0-898-71458-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 sorgente]

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

Voci correlate[modifica | modifica sorgente]

Altri progetti[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]