Problema mișcării cavalerului

Problema mișcării cavalerului  este problema găsirii traseului unui cavaler de șah care trece o dată prin toate pătratele tablei .

Această problemă este cunoscută cel puțin din secolul al XVIII-lea . Leonhard Euler i-a dedicat o mare lucrare „Soluția unei întrebări curioase, care pare să nu facă obiectul niciunei cercetări”, din 1759 [1] . Într-o scrisoare către Goldbach [2] , el a raportat:

... Reamintirea unei probleme care mi s-a propus cândva mi-a servit recent ca prilej la niște cercetări subtile, în care analiza obișnuită, se pare, nu are rost... Am găsit în sfârșit o modalitate clară de a găsi cât mai multe soluții după cum îmi plac (numărul lor, însă, nu este infinit), fără a face încercări.

Declarația problemei

În ceea ce privește teoria grafurilor, fiecare traseu al cavalerului prin toate pătratele tablei de șah corespunde unui drum hamiltonian (sau unui ciclu dacă traseul este închis) într-un grafic ale cărui vârfuri sunt pătratele tablei, iar două pătrate sunt conectate printr-un marginea dacă se poate trece de la unul la altul într-o mișcare a unui cal.

Pentru o placă 8 × 8, numărul tuturor rutelor cavalerelor închise (cicluri hamiltoniene) fără a lua în considerare direcția ocolirii este de 13 267 364 410 532 [3] . Numărul tuturor rutelor deschise (ținând cont de direcția de ocolire) este 19.591.828.170.979.904.

Metode de rezolvare

Metoda Euler

Metoda lui Euler este ca mai întâi cavalerul să se deplaseze pe un traseu arbitrar până când epuizează toate mișcările posibile. Apoi celulele rămase care nu au fost trecute sunt adăugate la traseul realizat, după o permutare specială a elementelor acestuia.

Luați în considerare următorul traseu ca exemplu:

55 58 29 40 27 44 19 22
60 39 56 43 treizeci 21 26 45
57 54 59 28 41 optsprezece 23 douăzeci
38 51 42 31 opt 25 46 17
53 32 37 A 47 16 9 24
cincizeci 3 52 33 36 7 12 cincisprezece
unu 34 5 48 b paisprezece c zece
patru 49 2 35 6 unsprezece d 13

Mai întâi, să încercăm să facem un traseu închis dintr-un traseu deschis. Pentru a face acest lucru, luați în considerare unde puteți merge de la câmpurile 1 și 60. Din câmpul 1 puteți merge la câmpurile 2, 32 și 52 și de la 60 la 29, 51 și 59. În aceste două seturi există câmpuri care diferă cu unul. , și anume - 51 și 52. Datorită acestui lucru, puteți face traseul închis inversând o parte a acestuia. Pentru a face acest lucru, renumerotați câmpurile de la 52 la 60 în ordine inversă. După aceea, obținem un traseu închis:

57 54 29 40 27 44 19 22
52 39 56 43 treizeci 21 26 45
55 58 53 28 41 optsprezece 23 douăzeci
38 51 42 31 opt 25 46 17
59 32 37 A 47 16 9 24
cincizeci 3 60 33 36 7 12 cincisprezece
unu 34 5 48 b paisprezece c zece
patru 49 2 35 6 unsprezece d 13

Acum puteți include unele dintre celulele netraversate în traseu. Deoarece traseul nostru este închis, acesta poate fi rupt într-un loc arbitrar și un lanț adecvat de celule netraversate poate fi atașat la unul dintre capete. De exemplu, dacă rupem lanțul din celula 51 (prin renumerotarea celulelor și făcându-l să dureze, și mai întâi 52), ne putem extinde lanțul cu celulele a , b și d , care vor deveni celulele 61, 62 și 63.

metoda Vandermonde

Vandermonde a încercat să reducă problema la aritmetică. Pentru a face acest lucru, el a notat traseul cavalerului de-a lungul tablei ca o succesiune de fracții x / y , unde x și y  sunt coordonatele câmpului de pe tablă. Evident, în succesiunea fracțiilor corespunzătoare mișcărilor cavalerului, diferența dintre numărătorii a două fracții învecinate nu poate fi decât 1 sau 2, în ciuda faptului că diferența dintre numitorii lor este 2 sau, respectiv, 1. În plus, numărătorul și numitorul nu pot fi mai mici de 1 și mai mari de 8 .

Metoda lui de a găsi o secvență potrivită este similară cu metoda lui Euler, dar permite doar găsirea căilor cavalerului pentru plăci cu dimensiuni egale.


Regula lui Warnsdorf

Regula lui Warnsdorf , care este un fel de algoritm lacom pentru găsirea traseului cavalerului, este formulată după cum urmează:

Când ocolește tabla, cavalerul urmărește terenul din care se poate merge la numărul minim de câmpuri care nu au fost încă trecute. Dacă există mai multe astfel de câmpuri, atunci puteți merge la oricare dintre ele.

Multă vreme s-a crezut că regula Warnsdorff funcționează impecabil. Mai târziu, cu ajutorul computerelor, a fost stabilită o inexactitate în a doua parte a acesteia: dacă există mai multe câmpuri adecvate, atunci nu toate sunt egale, iar o alegere arbitrară a unui câmp poate duce calul într-o fundătură. Cu toate acestea, în practică, probabilitatea de a ajunge într-o fundătură este mică, chiar și cu utilizarea gratuită a celei de-a doua părți a regulii Warnsdorff. [patru]

Trasee notabile

traseul Janisch

cincizeci unsprezece 24 63 paisprezece 37 26 35
23 62 51 12 25 34 cincisprezece 38
zece 49 64 21 40 13 36 27
61 22 9 52 33 28 39 16
48 7 60 unu douăzeci 41 54 29
59 patru 45 opt 53 32 17 42
6 47 2 57 44 19 treizeci 55
3 58 5 46 31 56 43 optsprezece
traseul Janisch

Traseul calului, găsit de K. A. Yanish , formează un pătrat semi-magic , iar când placa este rotită cu 180 °, prima jumătate a traseului (numerele de la 1 la 32) trece în a doua (numerele de la 33 la 64). ). Traseul, care este un adevărat pătrat magic, nu există pentru tabla 8 × 8 [5] .

traseul turcului

Mașina de șah „Turc” a demonstrat traseul închis al cavalerului, prezentat în diagrama din dreapta.

Poezie mnemonică

Poți ocoli toate pătratele de șah cu cavalerul o dată, în plus, poți să o faci „orb”, începând sau terminând pe orice pătrat la cererea „spectatorului”, poți urma poezia: [6]

Înroșește toamna cu cadouri valoroase,
O altă zi dătătoare de viață.
Snururi galbene roșii de pâine,
Baldachin filozofic Crystal Waters.

Două Seri Clinging Buds
Artista a scris, Bezdonna Sineva.
Zgură rutieră Kiss Worms,
Încă acoperit cu iarbă Phlox.

Fumează ceai ciocolată eficientă,
Cești de porțelan primesc trei,
Fata blonda Dana Joy
Forshmak Divide cu o margine rece.

Soție împingând iubita fragilă
Vrea să filmeze în acest weekend
Apreciind viscolul arctic însuși,
Aruncă o minge de pepene verde la patru.

Călcâiul de Cicada, abia ventriloc,
Îi dă fereastra lui Sandman lui Ficus.
Deși însetați de ceai sunt mulțumiți,
Proprietarul Noisily Donates Wine.

Foxtrot Six Girls Captivated,
Varietatea dansurilor sunt mai fantastice decât tata,
A ieșit puiul cu abia călcat,
Și Dracul Rătăcitor a dispărut.

Corpul Aspenului de bronz devine roșu,
Reigns Shadows Ajurat Lungime.
Silențios decât anvelopele mașinii
Vântul de mlaștină dă semințe.

Lantern Opt himere strălucește,
Beetle sosește, batând din palme, acolo.
Toamnă de dorit, dacă se completează
Cel mai valoros rest de muncă veselă.

Primele litere stabilesc coordonatele mișcărilor:

Aleet Toamna = A1; Cadouri de valoare = C2; etc.

În fiecare strofă este introdus un indiciu pentru a nu încurca succesiunea de strofe: încă una, două seri, TREI înțelegi etc.

Generalizare la panouri arbitrare

Trasee închise

Numărul de trasee închise, ținând cont de direcția, este de două ori mai mare. Rute închise există pe panouri pentru toate parele (secvența A001230 în OEIS ).

Rute deschise

Pentru scândurile nepătrate, o plimbare de cavaler neînchisă există numai dacă sunt îndeplinite următoarele condiții: dacă o parte a tablei este 3, atunci cealaltă parte trebuie să fie fie 4, fie cel puțin 7; dacă ambele părți sunt mai mari de 3, atunci cavalerul poate fi ocolit pe toate scândurile, cu excepția 4 × 4. În special, rutele neînchise există pe scânduri pătrate pentru toate . [7] Numărul de căi deschise pe plăci formează secvența A165134 în OEIS .

Vezi și

Note

  1. ↑ Euler, Leonhard, Solution d'une question curieuse que ne paroit soumise à aucune analyze Arhivat la 30 septembrie 2017 la Wayback Machine , Mémoires de l'académie des sciences de Berlin, 15 (1759) 1766, p. 310-337.
  2. ↑ How Euler Did It Arhivat 8 august 2017 la Wayback Machine .
  3. ↑ Brendan McKay. Turneele cavalerilor pe o tablă de șah 8x8  (nedeterminată)  // Raport tehnic TR-CS-97-03. — Department of Computer Science, Australian National University, 1997. Arhivat din original pe 28 septembrie 2013.
  4. ↑ E. Geek. Capitolul 2. Cal cameleon // Şah şi Matematică . - M . : Nauka, 1983. - (Biblioteca „Quantum”).
  5. ↑ Eric W. Weisstein, There Are No Magic Knight's Tours on the Chessboard Arhivat 8 septembrie 2017 la Wayback Machine , MathWorld Headline News.
  6. ↑ V. Panov. Secretul unui truc  // Știință și viață . - 1969. - Nr 5 .
  7. ↑ A. Conrad, T. Hindrichs, H. Morsy, I. Wegener. Rezolvarea problemei căii hamiltoniene a cavalerului pe tablele de șah   // Discr . Aplic. Matematică. : jurnal. - 1994. - Vol. 50 . - P. 125-134 . - doi : 10.1016/0166-218X(92)00170-Q .

Link -uri