Despre turul calului | Regula lui Warnsdorff, tururi deschise și închise

Un puzzle vechi

În Kavyalankara, scrisă de poetul indian Rudrata în secolul al IX-lea, un vers este așezat pe o jumătate de tablă de șah astfel încât să poată fi citit de-a lungul drumului unui cal. Leonhard Euler a scris primul studiu matematic al turului calului în 1759, cu metode de a construi tururi și de a le transforma în tururi închise.

Un drum printr-un graf

Gândește-te la fiecare câmp ca la un punct și la fiecare mutare de cal ca la o linie între două puncte. Un tur al calului este atunci un drum care vizitează fiecare punct exact o dată, ceea ce matematicienii numesc drum hamiltonian; un tur închis este un ciclu hamiltonian. În majoritatea rețelelor, un asemenea drum este foarte greu de găsit. Rețeaua calului este generoasă: are atât de multe tururi încât o regulă bună găsește unul repede.

Regula lui Warnsdorff

H. C. von Warnsdorff și-a descris regula în 1823: sari mereu pe câmpul care lasă cele mai puține mutări următoare. Câmpurile de pe margine au puțini vecini, așa că regula le vizitează devreme, în loc să le lase izolate. Când două câmpuri sunt la egalitate, trebuie făcută o alegere, iar o alegere nefericită poate totuși bloca calul. În aplicație, numerele aurii marchează câmpurile pe care le-ar alege regula.

Căutare cu backtracking

Rezolvă urmează ordinea lui Warnsdorff, dar nu are încredere oarbă în ea. Face o căutare în adâncime și, de îndată ce un câmp nevizitat nu mai poate fi atins, abandonează acea ramură și încearcă mutarea următoare. Pe table de până la 10×10 găsește de obicei un tur imediat. Când propriul tău drum a încolțit calul, mai întâi se întoarce câteva mutări.

Culori și tururi închise

Fiecare mutare de cal schimbă culoarea câmpului. Pe o tablă impară, cum e 5×5, există cu un câmp mai mult de culoarea colțurilor decât de cealaltă culoare, așa că un tur trebuie să înceapă și să se termine pe culoarea colțurilor. Acolo un tur închis este imposibil, pentru că o buclă care alternează culorile are tot atâtea câmpuri de fiecare culoare. Pe tablele pare, tururile închise există de la 6×6 în sus.

Încearcă în PictorX

Deschide Turul calului și dă clic pe un câmp ca să începi. Câmpurile evidențiate sunt săriturile permise, numărul auriu este alegerea lui Warnsdorff, iar tabla păstrează ordinea mutărilor tale. Dimensiune setează tabla de la 5×5 la 10×10, cu „Tur închis” Rezolvă caută o buclă, iar Anulează retrage orice mutare. Salvează drumul terminat ca PNG.

Întrebări frecvente

Cine a studiat primul turul calului?

Tururile erau cunoscute cu mult înainte ca cineva să le studieze matematic. Leonhard Euler a scris prima tratare matematică în 1759, iar Warnsdorff și-a prezentat regula în 1823.

Există un tur pe orice tablă?

Tablele pătrate de la 5×5 în sus au tururi deschise, iar cele pare de la 6×6 în sus au și tururi închise. Tablele de 2×2, 3×3 și 4×4 nu au niciun tur.

Câte tururi are o tablă de șah?

Există 26.534.728.821.064 de tururi închise, dacă un tur și același tur parcurs invers se numără separat. Numărul tururilor deschise este de aproximativ 19,6 biliarde.

PictorX încarcă ceva?

Nu. Tabla este desenată pe o pânză în browser. Salvează descarcă un PNG, iar Editează deschide imaginea în editorul PictorX.