Il problema del cavaliere (o anche la poligrafia o l'algoritmo del cavaliere o del cavaliere di Eulero) è un problema matematico-logico basato sui movimenti del cavaliere del gioco degli scacchi (un quadrato che condivide un lato comune quindi un quadrato diagonale nella stessa direzione). Un cavaliere posto su una qualsiasi casella di una scacchiera deve visitare tutte le sue caselle senza passare due volte sulla stessa.
Mentre l'obiettivo è generalmente quello di coprire tutte le caselle del tabellone con un cavaliere, una variante è stata studiata nel Medio Oriente medievale dove il pezzo alterna tra il movimento di un cavaliere e un movimento diagonale ( vedi sotto ).
Il problema inizialmente riguardava il percorso di una scacchiera quadrata di 64 quadrati o su una mezza scacchiera di 32 quadrati; ma successivamente è stato studiato per altre dimensioni e anche per forme non rettangolari, croci comprese.
Esistono diversi modi di attraversare la scacchiera: il percorso può essere aperto o chiuso su se stesso, nel qual caso si parla di turno del cavaliere . Possiamo anche cercare soluzioni con particolari simmetrie o anche le soluzioni più lunghe senza incrociarsi.
Circuito del jumper su una scacchiera di dimensioni 24 × 24 ottenuta da una rete neurale .
Corso aperto su una scacchiera di dimensioni 130 x 130 ottenuta utilizzando l'euristica di Warnsdorf.
Corso aperto su una scacchiera di dimensioni 5 x 5.
Torre del cavaliere su una tavola a forma di croce.
Circuito chiuso senza attraversamento massimo su tavola taglia 49; la sua lunghezza è di 24 salti.
Campo aperto senza incrocio massimo su scacchiera taglia 64; la sua lunghezza è di 35 salti.
La prima occorrenza si trova in un trattato sull'ornamento poetico indiano, il Kavyalankara del poeta Rudrata.
Una soluzione al problema del corso di un'intera mezza scacchiera di 32 caselle è stata trovata in un manoscritto degli inizi del X ° secolo ; questa soluzione può essere facilmente adattata per ottenere per giustapposizione il percorso completo di una scacchiera di 64 caselle. Questa soluzione non è un circuito perché non consente di tornare al punto di partenza.
Un'enciclopedia risalente indiano dal XVII esimo secolo esemplifica percorso chiuso su una tavola di 64 caselle. Charles Monneron riporta dall'India un'altra soluzione al problema, che sarà stampata più avanti nell'Enciclopedia .
|
|
|
Raja Krishnaraja Wodeyar III (in) era interessato al soggetto nella prima metà del XIX ° secolo , si deve a lui la prima di un pilota ovviamente noto i cui numeri di blocco formare un quadrato magico.
Il cavaliere Euler è conosciuto da molto tempo. Intorno all'840 , il giocatore di scacchi arabo e teorico al-Adli ar-Rumi diede già una soluzione.
Mezzi mnemoniche per lo svolgimento di una soluzione al circuito ponticello sono documentate in un manoscritto copiato in 1141 , che contiene i testi l'aggiunta al X ° secolo ; si tratta di poesie di 64 versi , ognuno dei quali è associato alle coordinate di un quadrato sulla scacchiera. Sono note quattro poesie di questo tipo, il che porta alla conclusione che il problema del circuito dei motociclisti era popolare nel mondo arabo-musulmano e che non si conosceva alcun metodo generale per costruire un tale percorso.
Altre regole del corsoStudiosi arabi hanno anche studiato un problema correlato in cui il pezzo da spostare adotta alternativamente il movimento del cavaliere e quello di un altro pezzo, consigliere o elefante, del chatrang (la versione degli scacchi praticata nel mondo arabo medievale). Il consigliere (antenato della signora ) e l'elefante (antenato del pazzo ) si muovono rispettivamente di un quadrato in diagonale e due quadrati in diagonale. Sono state composte anche poesie per memorizzare soluzioni.
|
|
Si trova in un manoscritto anglo-normanna del XIV ° secolo un fairway che mira a portare il pilota da un angolo all'altro. Diversi altri manoscritti successivi danno anche corsi aperti su scacchiere o mezze tavole.
Soluzione datata XIV ° secolo. | |||||||
---|---|---|---|---|---|---|---|
23 | 26 | 11 | 4 | 49 | 52 | 45 | 40 |
10 | 3 | 22 | 25 | 46 | 41 | 48 | 51 |
27 | 24 | 5 | 12 | 53 | 50 | 39 | 44 |
2 | 9 | 28 | 21 | 42 | 47 | 54 | 59 |
29 | 20 | 13 | 6 | 61 | 58 | 43 | 38 |
8 | 1 | 16 | 19 | 32 | 35 | 60 | 55 |
17 | 30 | 7 | 14 | 57 | 62 | 37 | 34 |
. | 15 | 18 | 31 | 36 | 33 | 56 | 63 |
Pierre Rémond de Montmort ha studiato questo problema e fornisce una soluzione citata da Martin Grandin . Quest'ultimo utilizza anche altre due soluzioni ottenute da Abraham de Moivre e da de Mairan .
|
|
|
Il matematico Leonhard Euler riprese gli studi scientifici nel 1759 . La "Soluzione di una domanda curiosa che non appare soggetta ad alcuna analisi" fu pubblicata , tuttavia , solo nel 1766 . Côme Alexandre Collini ne pubblicò uno sull'Encyclopedic Journal nel 1773.
Eulero mostra lì la soluzione di diversi problemi:
Una soluzione pubblicata da Eulero.
Una soluzione proposta da Eulero. Questa è simmetrica rispetto al centro della scacchiera, e attraversa prima la metà inferiore di quest'ultima, poi la parte superiore.
Soluzione del trucco su una scacchiera 10x10, proposta da Eulero.
Anche Eulero ha commesso degli errori, affermando così che nessun percorso chiuso è possibile su una scacchiera di larghezza 3; un controesempio fu dato nel 1917 su una scacchiera 3 × 10.
Corso chiuso su scacchiera 3 × 10. | |||||||||
---|---|---|---|---|---|---|---|---|---|
1 | 28 | 25 | 6 | 19 | 4 | 21 | 10 | 13 | 16 |
26 | 7 | 30 | 3 | 24 | 9 | 18 | 15 | 22 | 11 |
29 | 2 | 27 | 8 | 5 | 20 | 23 | 12 | 17 | 14 |
Nel corso dei secoli, i matematici hanno studiato questo tema variando:
Si è proposto di studiare i percorsi del ciclista in cui la somma dei numeri di passaggio di un box è costante secondo le linee e le colonne. Nel 1888, 83 di questi corsi (di cui 27 chiusi) furono depositati presso il Conservatorio Nazionale di Arti e Mestieri ; nessuno di questi percorsi dà un quadrato magico perché la somma non è la stessa seguendo le diagonali. Un 84 ° percorso è stato scoperto negli anni '70. Ricerche approfondite avviate nel 2003 come una scacchiera ci sono un totale di 108 percorsi diversi che formano quadrati magici nessuno dei quali ha uguale diagonale
Corso chiuso che è anche un quadrato magico. (Tranne le diagonali) | |||||||
---|---|---|---|---|---|---|---|
42 | 59 | 2 | 17 | 40 | 15 | 22 | 63 |
3 | 18 | 41 | 60 | 21 | 64 | 39 | 14 |
58 | 43 | 20 | 1 | 16 | 23 | 62 | 37 |
19 | 4 | 57 | 44 | 61 | 38 | 13 | 24 |
56 | 45 | 6 | 29 | 12 | 25 | 36 | 51 |
5 | 30 | 55 | 48 | 33 | 52 | 11 | 26 |
46 | 7 | 32 | 53 | 28 | 9 | 50 | 35 |
31 | 54 | 47 | 8 | 49 | 34 | 27 | 10 |
Va notato che un certo lavoro è stato fatto sul tema del golf pilota XXI ° secolo .
La ricerca della svolta di un ciclista è un caso speciale di grafici hamiltoniani nella teoria dei grafi . Inoltre, poiché un cavaliere passa sempre da una scatola nera a una bianca e viceversa , ne consegue che il grafico dei movimenti del cavaliere è un grafico bipartito .
Nel caso di una ricerca di un campo che non si ripete necessariamente su se stesso, è stato dimostrato che esiste una soluzione per qualsiasi scacchiera rettangolare la cui lunghezza e larghezza siano maggiori o uguali a 5.
I trucchi dei cavalieri possono essere eseguiti su pedine di diverse dimensioni e su diverse forme (rettangolo, cubo, selciato, spirale infinita, ecc.), Ma il numero dei quadrati deve essere pari. Nel caso di una scacchiera rettangolare abbiamo il seguente risultato di esistenza:
Teorema di Schwenk - Per qualsiasi scacchiera m × n tale che m sia minore o uguale an , c'è il turno di un cavaliere, a meno che una o più delle seguenti condizioni non siano vere:
La condizione 1 impedisce l'esistenza di una svolta chiusa, per semplici motivi di parità e colorazione. Su una scacchiera standard in bianco e nero, un cavaliere si sposta dal bianco al nero o viceversa. Quindi una svolta chiusa deve visitare lo stesso numero di quadrati bianchi e neri e il numero di quadrati visitati deve essere pari. Ora se m e n sono dispari, il numero di quadrati è dispari, quindi non esistono giri chiusi. Tuttavia, potrebbero esserci torri aperte.
Condizione 2In base a questa condizione, non c'è svolta chiusa se il lato più piccolo è 1, 2 o 4.
Se m = 1 o 2, il cavaliere non può raggiungere tutte le caselle (tranne nel caso banale 1 × 1 ). Possiamo anche mostrare l'assenza di una svolta chiusa nel caso 4 × n con un argomento colorante.
Supponiamo che ci sia una torre chiusa su una scacchiera 4 × n . Chiamiamo l'insieme dei quadrati neri e l'insieme dei quadrati bianchi visitati dal turno, su una scacchiera standard bianca e nera. Diamo un'occhiata alla figura a destra. Chiamiamo l'insieme delle caselle verdi e l'insieme delle caselle rosse. Sono in numero uguale. Nota che il cavaliere deve andare da un quadrato di a un quadrato di . Poiché deve visitare ogni quadrato, deve anche andare da un quadrato di a un quadrato di (altrimenti dovrebbe percorrere due o più quadrati consecutivi dopo, cosa impossibile).
L'esame di questo ipotetico trucco dà una contraddizione:
Ne consegue che gli insiemi e sono confusi, proprio come gli insiemi e . Questo è assurdo, quindi nel caso 4 × n non esiste alcuna svolta , indipendentemente da n .
Condizione 3Possiamo provare la condizione 3 caso per caso. La ricerca di una svolta chiusa nei casi 3 × 4 , 3 × 6 , 3 × 8 fallisce rapidamente. Per i casi 3 × n , con n pari e maggiore di 8, costruiamo le spire chiuse per induzione, ripetendo i movimenti.
Altri casiAbbiamo dimostrato che una torre chiusa non esiste nelle tre condizioni menzionate. Dimostrare l'esistenza di un simile trucco in altri casi è più complicato.
Per avere successo in un percorso è sufficiente scegliere per ogni nuovo salto uno spazio libero tra quello che offre il minor numero di salti successivi possibili, anche se significa annullare le ultime mosse in caso di vicolo cieco: questo è un classico esercizio di programmazione.
Sebbene il problema generale di trovare un circuito Hamiltoniano in un grafico sia NP-completo , il caso particolare della virata del ciclista può essere risolto in tempo lineare .
Ci sono 26.534.728.821.064 circuiti chiusi diversi su una scacchiera quadrata di 64 caselle, e ce ne sono 9.862 su una scacchiera quadrata di 36 caselle.
Il numero di corsi aperti per una scacchiera quadrata è dato dalla A165134 della OEIS :
Dimensione scacchiera: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|
Numero di corsi aperti: | 1 | 0 | 0 | 0 | 1.728 | 6.637.920 | 165 575 218 320 | 19591828170979904 |