Problemet med ridderens træk

Problemet med ridderens træk  er problemet med at finde ruten for en skakridder , der passerer gennem alle felterne på brættet én gang.

Dette problem har været kendt i det mindste siden det 18. århundrede . Leonhard Euler dedikerede hende et stort værk "Løsningen af ​​et mærkværdigt spørgsmål, som ikke synes at være genstand for nogen forskning," dateret 1759 [1] . I et brev til Goldbach [2] rapporterede han:

... Erindringen om et problem, der engang blev foreslået mig, tjente som anledning for mig for nylig til nogle subtile undersøgelser, hvor almindelig analyse, det ser ud til, ikke har nogen nytte ... Jeg fandt endelig en klar måde at finde så mange løsninger som jeg kan lide (deres antal er dog ikke uendeligt), uden at lave forsøg.

Problemformulering

Med hensyn til grafteori svarer hver ridders rute gennem alle felterne på skakbrættet til en Hamiltonsk sti (eller en cyklus, hvis ruten er lukket) i en graf, hvis hjørner er brættets firkanter, og to felter er forbundet med en kant, hvis man kan komme fra den ene til den anden i den ene hests træk.

For et 8 × 8 bræt er antallet af alle lukkede ridderruter (Hamiltonske cykler) uden hensyntagen til omfartsvejens retning 13 267 364 410 532 [3] . Antallet af alle åbne ruter (under hensyntagen til omfartsretningen) er 19.591.828.170.979.904.

Løsningsmetoder

Euler metode

Eulers metode er, at ridderen først bevæger sig ad en vilkårlig rute, indtil den udtømmer alle mulige træk. Derefter tilføjes de resterende celler, der ikke er blevet passeret, til den lavede rute, efter en speciel permutation af dens elementer.

Overvej følgende rute som et eksempel:

55 58 29 40 27 44 19 22
60 39 56 43 tredive 21 26 45
57 54 59 28 41 atten 23 tyve
38 51 42 31 otte 25 46 17
53 32 37 -en 47 16 9 24
halvtreds 3 52 33 36 7 12 femten
en 34 5 48 b fjorten c ti
fire 49 2 35 6 elleve d 13

Lad os først prøve at lave en lukket rute fra en åben rute. For at gøre dette skal du overveje, hvor du kan gå fra felt 1 og 60. Fra felt 1 kan du gå til felt 2, 32 og 52, og fra 60 til 29, 51 og 59. I disse to sæt er der felter, der adskiller sig med én , nemlig - 51 og 52. Takket være dette kan du lukke ruten ved at vende en del af den. For at gøre dette skal du omnummerere felterne fra 52 til 60 i omvendt rækkefølge. Derefter får vi en lukket rute:

57 54 29 40 27 44 19 22
52 39 56 43 tredive 21 26 45
55 58 53 28 41 atten 23 tyve
38 51 42 31 otte 25 46 17
59 32 37 -en 47 16 9 24
halvtreds 3 60 33 36 7 12 femten
en 34 5 48 b fjorten c ti
fire 49 2 35 6 elleve d 13

Nu kan du inkludere nogle af de ikke-traverserede celler i ruten. Da vores rute er lukket, kan den brydes et vilkårligt sted, og en passende kæde af ikke-traverserede celler kan fastgøres til en af ​​enderne. Hvis vi for eksempel bryder kæden i celle 51 (ved at omnummerere celler og få den til at sidste, og 52 først), kan vi forlænge vores kæde med celler a , b og d , som bliver til celler 61, 62 og 63.

Vandermonde metode

Vandermonde forsøgte at reducere problemet til aritmetik. For at gøre dette betegnede han ridderens rute langs brættet som en sekvens af brøker x / y , hvor x og y  er koordinaterne for feltet på brættet. I rækken af ​​brøker, der svarer til ridderens træk, kan forskellen mellem tællere i to nabobrøker naturligvis kun være 1 eller 2, på trods af at forskellen mellem deres nævnere er henholdsvis 2 eller 1. Derudover kan brøkerne være 1 eller 2. tælleren og nævneren må ikke være mindre end 1 og større end 8 .

Hans metode til at finde en passende sekvens ligner Eulers metode, men tillader kun at finde ridderens stier for lige dimensionelle brædder.


Warnsdorfs regel

Warnsdorfs regel , som er en slags grådig algoritme til at finde ridderens rute, er formuleret som følger:

Når man går rundt på brættet, følger ridderen det felt, hvorfra det er muligt at gå til det mindste antal felter, der endnu ikke er passeret. Hvis der er flere sådanne felter, kan du gå til et hvilket som helst af dem.

I lang tid troede man, at Warnsdorff-reglen fungerer upåklageligt. Senere, ved hjælp af computere, blev der etableret en unøjagtighed i den anden del af den: hvis der er flere egnede felter, så er ikke alle af dem lige, og et vilkårligt valg af et felt kan føre hesten til en blindgyde. Men i praksis er sandsynligheden for at komme i en blindgyde lille selv med den frie brug af anden del af Warnsdorff-reglen. [fire]

Bemærkelsesværdige ruter

Janisch rute

halvtreds elleve 24 63 fjorten 37 26 35
23 62 51 12 25 34 femten 38
ti 49 64 21 40 13 36 27
61 22 9 52 33 28 39 16
48 7 60 en tyve 41 54 29
59 fire 45 otte 53 32 17 42
6 47 2 57 44 19 tredive 55
3 58 5 46 31 56 43 atten
Janisch rute

Hestens rute, fundet af K. A. Yanish , danner en semi-magisk firkant , og når brættet drejes 180°, går den første halvdel af ruten (tal fra 1 til 32) over i den anden (tal fra 33 til 64) ). Ruten, som er en rigtig magisk firkant, eksisterer ikke for brættet 8 × 8 [5] .

Turks rute

Skakmaskinen "Turk" demonstrerede ridderens lukkede rute, vist i diagrammet til højre.

Mnemonisk digt

Du kan gå rundt om alle skakfelterne med ridderen én gang, desuden kan du gøre det "blindt", begyndende eller slutte på et hvilket som helst felt efter anmodning fra "tilskueren", du kan følge digtet: [6]

Redner Autumn med værdifulde gaver,
Endnu en livgivende dag.
Brød røde gule snore,
Crystal Waters filosofiske baldakin.

To aftener klæbende knopper
Kunstner skrev, Bezdonna Sineva.
Road Slag Kiss Worms,
Stadig dækket med Phlox-græs.

Ryger Te Effektiv Chokolade,
Porcelænskopper får tre,
Blonde pige Dana Joy
Forshmak Divide med en kold kant.

Kone skubber skrøbelig kæreste
Ønsker at skyde denne weekend
At værdsætte selve den arktiske snestorm,
Kaster en vandmelonbold til fire.

Cicada Heel, Barely Ventriloquist,
Giver Sandman vindue til Ficus.
Selvom Tørstig efter Te er tilfreds,
Ejeren donerer Noisily vin.

Foxtrot Six Girls Captivated,
Variety danse er mere fantastiske end far,
Den knap trædende kylling kom ud,
Og den omvandrende Drake er væk.

Bronzeaspens krop bliver rød,
Reigns Shadows gennembrudt længde.
Lydløs end bildæk
Sumpvind giver frø.

Lanterne otte kimærer skinner,
Beetle ankommer, klapper, der.
Ønskeligt efterår, hvis det bliver gennemført
Den mest værdifulde resten af ​​muntert arbejde.

De første bogstaver sætter koordinaterne for bevægelserne:

Aleet Efterår = A1; Værdifulde gaver = C2; etc.

Et hint er indsat i hver strofe for at hjælpe med ikke at forvirre rækkefølgen af ​​strofer: EN mere, TO aftener, TRE få det osv.

Generalisering til vilkårlige bestyrelser

Lukkede ruter

Antallet af lukkede ruter, taget retningen i betragtning, er dobbelt så stort. Der findes lukkede ruter på tavler for alle lige (sekvens A001230 i OEIS ).

Åbne ruter

For ikke-firkantede brædder eksisterer en ikke-lukket riddervandring kun, hvis følgende betingelser er opfyldt: hvis den ene side af brættet er 3, så skal den anden side være enten 4 eller mindst 7; hvis begge sider er større end 3, så kan ridderen omgås på alle brædder undtagen 4 × 4. Især findes ikke-lukkede ruter på firkantede brædder for alle . [7] Antallet af åbne stier på tavlerne danner sekvensen A165134 i OEIS .

Se også

Noter

  1. ↑ Euler, Leonhard, Solution d'une question curieuse que ne paroit soumise à aucune analyse Arkiveret 30. september 2017 på Wayback Machine , Mémoires de l'académie des sciences de Berlin, 15 (1759) 1766, s. 310-337.
  2. ↑ Hvordan Euler gjorde det arkiveret 8. august 2017 på Wayback Machine .
  3. ↑ Brendan McKay. Knight's Tours på et 8x8 skakbræt  (ubestemt)  // Teknisk rapport TR-CS-97-03. — Department of Computer Science, Australian National University, 1997. Arkiveret fra originalen den 28. september 2013.
  4. ↑ E. Nørd. Kapitel 2. Kamæleonhest // Skak og matematik . - M . : Nauka, 1983. - (Bibliotek "Quantum").
  5. ↑ Eric W. Weisstein, There Are No Magic Knight's Tours on the Chessboard Arkived September 8, 2017 at the Wayback Machine , MathWorld Headline News.
  6. ↑ V. Panov. Hemmeligheden bag et trick  // Videnskab og liv . - 1969. - Nr. 5 .
  7. ↑ A. Conrad, T. Hindrichs, H. Morsy, I. Wegener. Løsning af Knight's Hamiltonian Path Problem på skakbrætter   // Discr . Appl. Matematik. : journal. - 1994. - Bd. 50 . - S. 125-134 . - doi : 10.1016/0166-218X(92)00170-Q .

Links