Problema cavaler (sau chiar COMPOZITE sau algoritmul de cavaler sau călărețul lui Euler) este o problemă de matematică-logică bazată pe mișcările de cavaler al jocului de șah (o partajare a pătrat o latură comună , apoi un pătrat diagonală în aceeași direcție) . Un cavaler așezat pe orice pătrat al unei table de șah trebuie să-și viziteze toate pătratele fără a trece de două ori pe același.
În timp ce scopul este, în general, să acopere toate pătratele de pe tablă cu un cavaler, o variantă a fost studiată în Orientul Mijlociu medieval unde piesa alternează între mișcarea unui cavaler și o mișcare diagonală ( vezi mai jos ).
Problema se referea inițial la cursul unei table de șah pătrate de 64 de pătrate sau pe o jumătate de șah de 32 de pătrate; dar a fost ulterior studiat pentru alte dimensiuni și, de asemenea, pentru forme non-dreptunghiulare, inclusiv cruci.
Există diferite moduri de a traversa tabla de șah: traseul poate fi deschis sau închis pe sine, caz în care vorbim de rândul călărețului . Putem căuta, de asemenea, soluții cu simetrii particulare sau chiar și cele mai lungi soluții fără trecere.
Circuitul jumperului pe o tablă de șah de dimensiunea 24 × 24 obținută de o rețea neuronală .
Curs deschis pe o tablă de șah de dimensiuni 130 x 130 obținută prin utilizarea euristicii Warnsdorf.
Deschideți cursul pe o tablă de șah de dimensiuni 5 x 5.
Turnul călărețului pe o scândură în formă de cruce.
Circuit închis fără trecere maximă pe o placă de dimensiunea 49; lungimea sa este de 24 de salturi.
Traseu deschis fără traversare maximă pe o tablă de șah de dimensiunea 64; lungimea sa este de 35 de salturi.
Prima apariție se găsește într-un tratat despre ornamentul poetic indian, Kavyalankara de poetul Rudrata.
O soluție la problema cursului unei întregi pe jumătate tablă de șah de 32 de pătrate a fost găsit într - un manuscris de la începutul X - lea secol ; această soluție poate fi ușor adaptată pentru a obține prin juxtapunere parcursul complet al unei table de șah de 64 de pătrate. Această soluție nu este un circuit, deoarece nu vă permite să reveniți la punctul de plecare.
O enciclopedie datând indian din XVII - lea secol exemplifică închis calea pe o tablă de 64 de pătrate. Charles Monneron raportează din India o altă soluție a problemei, care va fi tipărită ulterior în Enciclopedie .
|
|
|
Raja Krishnaraja Wadiyar III (in) a fost interesat de subiect , în prima jumătate a XIX - lea secol , noi îl datorăm primul dintr - un călăreț curs cunoscut al cărui numere de bloc formează un pătrat magică.
Călăreț Euler a fost cunoscut pentru o lungă perioadă de timp. În jurul anului 840 , șahistul și teoreticianul arab al-Adli ar-Rumi au dat deja o soluție.
Preparate mnemonice pentru susținerea unei soluții la circuitul de legătură sunt documentate într - un manuscris copiat în 1141 , care conține textele din adăugarea la X - lea secol ; acestea sunt poezii de 64 de rânduri , fiecare dintre ele fiind asociat cu coordonatele unui pătrat de pe tabla de șah. Sunt cunoscute patru astfel de poezii, ceea ce duce la concluzia că problema circuitului călărețului era populară în lumea arabo-musulmană și că nu se cunoaște nicio metodă generală de construire a unui astfel de curs.
Alte reguli ale cursuluiSavanții arabi au studiat, de asemenea, o problemă conexă în care piesa care urmează să fie mutată adoptă alternativ mișcarea călărețului și cea a unei alte piese, consilier sau elefant, a chatrang-ului (versiunea șahului practicată în lumea arabă medievală). Consilierul (strămoșul doamnei ) și elefantul (strămoșul nebunului ) deplasându-se respectiv un pătrat în diagonală și două pătrate în diagonală. Poezii au fost, de asemenea, compuse pentru a memora soluții.
|
|
Se găsește într-un manuscris anglo-normand din secolul al XIV- lea un fairway care are ca scop aducerea călărețului dintr-un colț în altul. Câteva alte manuscrise ulterioare oferă, de asemenea, cursuri deschise pe tablă de șah sau demipensiuni.
Soluție datată din secolul al XIV- lea. | |||||||
---|---|---|---|---|---|---|---|
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 a studiat această problemă și oferă o soluție citată de Martin Grandin . Acesta din urmă folosește și alte două soluții obținute de Abraham de Moivre și de de Mairan .
|
|
|
Matematicianul Leonhard Euler a reluat studiul științific în 1759 . „Soluția unei întrebări curioase care nu pare supusă niciunei analize” nu a fost publicată decât în 1766 . Côme Alexandre Collini a publicat unul în Jurnalul Enciclopedic în 1773.
Euler arată acolo soluția mai multor probleme:
O soluție publicată de Euler.
O soluție propusă de Euler. Aceasta este simetrică în raport cu centrul tablei de șah și trece mai întâi prin jumătatea inferioară a acesteia, apoi partea superioară.
Soluția trucului pe o tablă de șah 10x10, propusă de Euler.
De asemenea, Euler a făcut erori, afirmând astfel că nu este posibilă o cale închisă pe o tablă de șah cu lățimea 3; un contraexemplu a fost dat în 1917 pe o tablă de șah de dimensiuni 3 × 10.
Curs închis pe o tablă de șah de dimensiuni 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 |
De-a lungul secolelor, matematicienii au studiat această temă variind:
S-a propus studierea curselor călărețului în care suma numărului de trecere al unei cutii este constantă în funcție de rânduri și coloane. În 1888, 83 de astfel de cursuri (inclusiv 27 închise) au fost depuse la Conservatorul Național de Arte și Meserii ; niciunul dintre aceste cursuri nu dă un pătrat magic deoarece suma nu este aceeași urmând diagonalele. O a 84- a rută a fost descoperită în anii 1970 Cercetări extinse înființate în 2003 ca tablă de șah există un total de 108 cursuri diferite care formează pătrate magice, niciuna dintre ele nu are o diagonală egală
Curs închis, care este și un pătrat magic. (Cu excepția diagonalelor) | |||||||
---|---|---|---|---|---|---|---|
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 |
Trebuie remarcat faptul că unele lucrări se face pe tema golf rider XXI - lea secol .
Căutarea rândului unui călăreț este un caz special al graficelor hamiltoniene în teoria graficelor . Mai mult, întrucât un cavaler trece întotdeauna de la o cutie neagră la o cutie albă și invers , rezultă că graficul mișcărilor cavalerului este un grafic bipartit .
În cazul căutării unui traseu care nu este neapărat o buclă pe sine, s-a dovedit că există o soluție pentru orice tablă de șah dreptunghiulară a cărei lungime și lățime sunt mai mari sau egale cu 5.
Trucurile cavalerilor se pot face pe dame de diferite dimensiuni și pe diferite forme (dreptunghi, cub, pavaj, spirală infinită etc.), dar numărul de pătrate trebuie să fie egal. În cazul unei table de șah dreptunghiulare, avem următorul rezultat al existenței:
Teorema lui Schwenk - Pentru orice tablă de șah m × n astfel încât m este mai mică sau egală cu n , există rândul cavalerului, cu excepția cazului în care una sau mai multe dintre următoarele condiții sunt adevărate:
Condiția 1 împiedică existența unui viraj închis, din simple motive de paritate și colorare. Pe o tablă de șah alb-negru standard, un cavaler trece de la alb la negru sau invers. Deci, o tura închisă trebuie să viziteze același număr de pătrate alb-negru, iar numărul de pătrate vizitate trebuie să fie par. Acum, dacă m și n sunt impare, numărul de pătrate este impar, deci nu există o rotație închisă. Cu toate acestea, pot exista turnuri deschise.
Starea 2Conform acestei condiții, nu există nicio viraj închis dacă partea cea mai mică este 1, 2 sau 4.
Dacă m = 1 sau 2, cavalerul nu poate atinge toate pătratele (cu excepția cazului banal 1 × 1 ). De asemenea, putem arăta absența unui viraj închis în cazul 4 × n printr-un argument de colorare.
Să presupunem că există un turn închis pe o tablă de șah 4 × n . Să numim setul de pătrate negre și setul de pătrate albe vizitate de turn, pe o tablă de șah alb-negru standard. Să ne uităm la figura din dreapta. Să numim setul de cutii verzi și setul de cutii roșii. Sunt în număr egal. Rețineți că cavalerul trebuie să treacă de la un pătrat de la un pătrat de . Deoarece trebuie să viziteze fiecare pătrat, trebuie să treacă și de la un pătrat de la un pătrat de (altfel ar trebui să călătorească două sau mai multe pătrate consecutive după aceea, ceea ce este imposibil).
Examinarea acestui truc ipotetic dă o contradicție:
Rezultă că mulțimile și sunt confuze, la fel ca mulțimile și . Acest lucru este absurd, deci nu există nicio rotație în cazul 4 × n , indiferent de n .
Starea 3Putem dovedi condiția 3 de la caz la caz. Căutarea unei ture închise în cazurile 3 × 4 , 3 × 6 , 3 × 8 eșuează rapid. Pentru cazurile 3 × n , cu n par și mai mare de 8, construim ture închise prin inducție, repetând mișcările.
Alte cazuriAm demonstrat că un turn închis nu există în cele trei condiții menționate. Dovedirea existenței unui astfel de truc în alte cazuri este mai complicată.
Pentru a reuși într-un curs, este suficient să alegeți pentru fiecare salt nou un spațiu liber dintre cel care oferă cele mai puține sărituri ulterioare posibile, chiar dacă aceasta înseamnă anularea ultimelor mișcări în cazul unui impas: acesta este un exercițiu clasic de programare.
Deși problema generală a găsirii unui circuit hamiltonian într-un grafic este NP-completă , cazul particular al turei călărețului poate fi rezolvat în timp liniar .
Există 26.534.728.821.064 circuite închise diferite pe o tablă de șah pătrată de 64 de pătrate și există 9.862 dintre ele pe o tablă de șah pătrată de 36 de pătrate.
Numărul cursurilor deschise pentru o tablă de șah pătrată este dat de A165134 al OEIS :
Dimensiunea tabloului de șah: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|
Numărul de cursuri deschise: | 1 | 0 | 0 | 0 | 1.728 | 6.637.920 | 165 575 218 320 | 19 591 828 170 979 904 |