Loading AI tools
problema matematico Da Wikipedia, l'enciclopedia libera
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:
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 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.
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.
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
