Problemet med riddarens drag

Problemet med riddarens drag  är problemet med att hitta vägen för en schackriddare som passerar alla rutor på brädan en gång.

Detta problem har varit känt åtminstone sedan 1700-talet . Leonhard Euler tillägnade henne ett stort verk "Lösningen av en nyfiken fråga, som inte verkar vara föremål för någon forskning", daterat 1759 [1] . I ett brev till Goldbach [2] rapporterade han:

... Erinringen av ett problem som en gång föreslogs för mig tjänade som ett tillfälle för mig nyligen till någon subtil forskning, där vanlig analys, det verkar, inte har någon nytta ... Jag hittade äntligen ett tydligt sätt att hitta så många lösningar som jag gillar (deras antal är dock inte oändligt), utan att göra försök.

Problemformulering

När det gäller grafteorin motsvarar varje riddarväg genom schackbrädets alla rutor en Hamiltonsk väg (eller en cykel om rutten är stängd) i en graf vars hörn är brädans rutor, och två rutor är sammankopplade med en kant om man kan ta sig från den ena till den andra i ena hästens drag.

För en 8 × 8-bräda är antalet stängda riddarrutter (Hamilton-cykler) utan att ta hänsyn till bypassriktningen 13 267 364 410 532 [3] . Antalet öppna rutter (med hänsyn till förbifartsriktningen) är 19 591 828 170 979 904.

Lösningsmetoder

Euler-metoden

Eulers metod är att riddaren först rör sig längs en godtycklig rutt tills den förbrukar alla möjliga drag. Sedan läggs de återstående cellerna som inte har passerats till den gjorda rutten, efter en speciell permutation av dess element.

Betrakta följande väg som ett exempel:

55 58 29 40 27 44 19 22
60 39 56 43 trettio 21 26 45
57 54 59 28 41 arton 23 tjugo
38 51 42 31 åtta 25 46 17
53 32 37 a 47 16 9 24
femtio 3 52 33 36 7 12 femton
ett 34 5 48 b fjorton c tio
fyra 49 2 35 6 elva d 13

Låt oss först försöka göra en stängd rutt från en öppen rutt. För att göra detta, fundera över var du kan gå från fält 1 och 60. Från fält 1 kan du gå till fält 2, 32 och 52, och från 60 till 29, 51 och 59. I dessa två uppsättningar finns det fält som skiljer sig med ett , nämligen - 51 och 52. Tack vare detta kan du stänga rutten genom att vända en del av den. För att göra detta, numrera om fälten från 52 till 60 i omvänd ordning. Efter det får vi en stängd rutt:

57 54 29 40 27 44 19 22
52 39 56 43 trettio 21 26 45
55 58 53 28 41 arton 23 tjugo
38 51 42 31 åtta 25 46 17
59 32 37 a 47 16 9 24
femtio 3 60 33 36 7 12 femton
ett 34 5 48 b fjorton c tio
fyra 49 2 35 6 elva d 13

Nu kan du inkludera några av de icke-traverserade cellerna i rutten. Eftersom vår rutt är stängd kan den brytas på ett godtyckligt ställe och en lämplig kedja av icke-traverserade celler kan fästas i en av ändarna. Till exempel, om vi bryter kedjan i cell 51 (genom att numrera om cellerna och göra den sist, och 52 först), kan vi förlänga vår kedja med cellerna a , b och d , som blir cellerna 61, 62 och 63.

Vandermonde-metoden

Vandermonde försökte reducera problemet till aritmetik. För att göra detta betecknade han riddarens rutt längs brädet som en sekvens av bråk x / y , där x och y  är koordinaterna för fältet på brädet. Uppenbarligen, i sekvensen av bråk som motsvarar riddarens drag, kan skillnaden mellan täljarna för två angränsande bråk bara vara 1 eller 2, trots att skillnaden mellan deras nämnare är 2 respektive 1. Dessutom, täljaren och nämnaren får inte vara mindre än 1 och större än 8 .

Hans metod för att hitta en lämplig sekvens liknar Eulers metod, men tillåter bara att hitta riddarens vägar för brädor med jämna dimensioner.


Warnsdorfs regel

Warnsdorfs regel , som är en sorts girig algoritm för att hitta riddarens rutt, är formulerad enligt följande:

När han går runt brädet följer riddaren fältet från vilket det är möjligt att gå till det minsta antalet fält som ännu inte har passerats. Om det finns flera sådana fält kan du gå till vilket som helst av dem.

Länge trodde man att Warnsdorff-regeln fungerar felfritt. Senare, med hjälp av datorer, etablerades en felaktighet i den andra delen av den: om det finns flera lämpliga fält är inte alla lika, och ett godtyckligt val av ett fält kan leda hästen till en återvändsgränd. Men i praktiken är sannolikheten att hamna i en återvändsgränd liten även med den fria användningen av den andra delen av Warnsdorff-regeln. [fyra]

Anmärkningsvärda rutter

Janisch rutt

femtio elva 24 63 fjorton 37 26 35
23 62 51 12 25 34 femton 38
tio 49 64 21 40 13 36 27
61 22 9 52 33 28 39 16
48 7 60 ett tjugo 41 54 29
59 fyra 45 åtta 53 32 17 42
6 47 2 57 44 19 trettio 55
3 58 5 46 31 56 43 arton
Janisch väg

Hästens rutt, som hittats av K. A. Yanish , bildar en semi-magisk fyrkant , och när brädet roteras 180 ° går den första halvan av rutten (nummer från 1 till 32) över i den andra (nummer från 33 till 64) ). Rutten, som är en riktig magisk ruta, finns inte för brädet 8 × 8 [5] .

Turks väg

Schackmaskinen "Turk" demonstrerade riddarens stängda rutt, som visas i diagrammet till höger.

Mnemonisk dikt

Du kan gå runt alla schackrutorna med riddaren en gång, dessutom kan du göra det "blindt", börja eller sluta på valfri ruta på begäran av "åskådaren", du kan följa dikten: [6]

Redner hösten med värdefulla gåvor,
Ännu en livgivande dag.
Bröd Röda Gula Snören,
Crystal Waters filosofiska baldakin.

Två kvällar Klängande knoppar
Konstnären skrev, Bezdonna Sineva.
Road Slag Kiss Worms,
Fortfarande täckt med floxgräs.

Röker te effektiv choklad,
Porslinsmuggar får tre,
Blond tjej Dana Joy
Forshmak Divide med en kall kant.

Fru som trycker skröplig flickvän
Vill fota i helgen
Att uppskatta själva arktiska snöstormen,
Kastar en vattenmelonboll till fyra.

Cicada Heel, Barely Ventriloquist,
Ger Sandman Window till Ficus.
Även om törstiga efter te är nöjda,
Ägaren Noisily donerar vin.

Foxtrot Six Girls Captivated,
Variationsdanser är mer fantastiska än pappa,
Knappt stegande kyckling kom ut,
Och den vandrande Draken är borta.

Bronsaspens kropp blir röd,
Reigns Shadows genombruten längd.
Tyst än bildäck
Träskvinden ger frön.

Lantern Åtta chimärer lyser,
Beetle anländer, klappar, där.
Önskvärd höst, om den är klar
Den mest värdefulla resten av glad arbetskraft.

De första bokstäverna anger koordinaterna för rörelserna:

Aleet Höst = A1; Värdefulla gåvor = C2; etc.

En ledtråd infogas i varje strof för att hjälpa till att inte blanda ihop strofernas sekvens: EN till, TVÅ kvällar, TRE fattar, etc.

Generalisering till godtyckliga styrelser

Stängda rutter

Antalet stängda rutter, med hänsyn till riktningen, är dubbelt så stort. Stängda rutter finns på brädorna för alla jämna (sekvens A001230 i OEIS ).

Öppna rutter

För icke-fyrkantiga brädor existerar en icke-stängd riddarvandring endast om följande villkor är uppfyllda: om ena sidan av brädan är 3, måste den andra sidan vara antingen 4 eller minst 7; om båda sidor är större än 3, kan riddaren förbigås på alla brädor utom 4 × 4. I synnerhet finns icke-stängda rutter på fyrkantiga brädor för alla . [7] Antalet öppna banor på brädorna bildar sekvensen A165134 i OEIS .

Se även

Anteckningar

  1. ↑ Euler, Leonhard, Solution d'une question curieuse que ne paroit soumise à aucune analys Arkiverad 30 september 2017 på Wayback Machine , Mémoires de l'académie des sciences de Berlin, 15 (1759) 1766, sid. 310-337.
  2. ↑ Hur Euler gjorde det arkiverades 8 augusti 2017 på Wayback Machine .
  3. ↑ Brendan McKay. Riddarturer på ett 8x8 schackbräde  (obestämd tid)  // Teknisk rapport TR-CS-97-03. — Institutionen för datavetenskap, Australian National University, 1997. Arkiverad från originalet den 28 september 2013.
  4. ↑ E. Geek. Kapitel 2. Kameleonthäst // Schack och matematik . - M . : Nauka, 1983. - (Bibliotek "Quantum").
  5. ↑ Eric W. Weisstein, There Are No Magic Knight's Tours on the Chessboard Arkiverad 8 september 2017 på Wayback Machine , MathWorld Headline News.
  6. ↑ V. Panov. Hemligheten med ett trick  // Science and Life . - 1969. - Nr 5 .
  7. ↑ A. Conrad, T. Hindrichs, H. Morsy, I. Wegener. Lösning av riddarens Hamiltonska vägproblem på schackbräden   // Discr . Appl. Matematik. : journal. - 1994. - Vol. 50 . - S. 125-134 . - doi : 10.1016/0166-218X(92)00170-Q .

Länkar