Om springarturen | Warnsdorffs regel, öppna och slutna turer

Ett gammalt pussel

I Kavyalankara, skriven av den indiske poeten Rudrata på 800-talet, är en vers utlagd på ett halvt schackbräde så att den kan läsas längs en springares väg. Leonhard Euler skrev den första matematiska studien av springarturen 1759, med sätt att bygga turer och göra om dem till slutna turer.

En väg genom en graf

Tänk på varje ruta som en punkt och varje springardrag som en linje mellan två punkter. En springartur är då en väg som besöker varje punkt exakt en gång, det som matematiker kallar en hamiltonsk väg; en sluten tur är en hamiltonsk cykel. I de flesta nätverk är en sådan väg mycket svår att hitta. Springarens nätverk är generöst: det har så många turer att en bra regel snabbt hittar en.

Warnsdorffs regel

H. C. von Warnsdorff beskrev sin regel 1823: hoppa alltid till den ruta som lämnar minst antal drag vidare. Rutor längs kanten har få grannar, så regeln besöker dem tidigt i stället för att lämna dem isolerade. När två rutor står lika måste man välja, och ett olyckligt val kan ändå få springaren att köra fast. I appen visar de guldfärgade talen vilka rutor regeln skulle välja.

Sökning med backtracking

Lös följer Warnsdorffs ordning men litar inte blint på den. Den gör en djupet-först-sökning, och så snart en obesökt ruta inte längre kan nås överger den den grenen och provar nästa drag. På bräden upp till 10×10 hittar den oftast en tur direkt. När din egen väg har stängt in springaren backar den först några drag.

Färger och slutna turer

Varje springardrag byter rutans färg. På ett udda bräde som 5×5 finns det en ruta mer i hörnens färg än i den andra färgen, så en tur måste börja och sluta på hörnens färg. En sluten tur är omöjlig där, eftersom en slinga som växlar färg har lika många rutor av varje färg. På jämna bräden finns slutna turer från 6×6 och uppåt.

Prova i PictorX

Öppna Springartur och klicka på en ruta för att börja. De markerade rutorna är de tillåtna hoppen, det guldfärgade talet är Warnsdorffs val, och brädet behåller ordningen på dina drag. Med storlek ställer du in brädet från 5×5 till 10×10, ”Sluten tur” ber Lös om en slinga, och Ångra tar tillbaka valfritt drag. Spara den färdiga vägen som PNG.

Ofta ställda frågor

Vem studerade springarturen först?

Turer var kända långt innan någon studerade dem matematiskt. Leonhard Euler skrev den första matematiska behandlingen 1759, och Warnsdorff gav sin regel 1823.

Finns det en tur på alla bräden?

Kvadratiska bräden från 5×5 och uppåt har öppna turer, och de jämna från 6×6 och uppåt har också slutna turer. Bräden på 2×2, 3×3 och 4×4 har ingen tur alls.

Hur många turer har ett schackbräde?

Det finns 26 534 728 821 064 slutna turer om en tur och samma tur baklänges räknas var för sig. Antalet öppna turer är omkring 19,6 biljarder.

Laddar PictorX upp något?

Nej. Brädet ritas på en canvas i webbläsaren. Spara laddar ner en PNG, och Redigera öppnar bilden i PictorX-redigeraren.