Om springerturen | Warnsdorffs regel, åbne og lukkede ture

En gammel gåde

I Kavyalankara, skrevet af den indiske digter Rudrata i det 9. århundrede, er et vers stillet op på et halvt skakbræt, så det kan læses langs en springers vej. Leonhard Euler skrev den første matematiske undersøgelse af springerturen i 1759, med metoder til at bygge ture og gøre dem lukkede.

En vej gennem en graf

Tænk på hvert felt som et punkt og hvert springertræk som en linje mellem to punkter. En springertur er så en vej, der besøger hvert punkt præcis én gang, det matematikere kalder en hamiltonsk vej; en lukket tur er en hamiltonsk kreds. I de fleste netværk er sådan en vej meget svær at finde. Springerens netværk er gavmildt: det har så mange ture, at en god regel hurtigt finder en.

Warnsdorffs regel

H. C. von Warnsdorff beskrev sin regel i 1823: hop altid til det felt, der giver færrest træk videre. Felter langs kanten har få naboer, så reglen besøger dem tidligt i stedet for at efterlade dem isolerede. Når to felter står lige, skal der vælges, og et uheldigt valg kan stadig få springeren til at sidde fast. I appen markerer de gyldne tal de felter, reglen ville vælge.

Søgning med backtracking

Løs følger Warnsdorffs rækkefølge, men stoler ikke blindt på den. Den søger i dybden først, og så snart et ubesøgt felt ikke længere kan nås, opgiver den den gren og prøver det næste træk. På brætter op til 10×10 finder den som regel en tur med det samme. Når din egen rute har spærret springeren inde, går den først nogle træk tilbage.

Farver og lukkede ture

Hvert springertræk skifter feltets farve. På et bræt af ulige størrelse som 5×5 er der ét felt mere i hjørnernes farve end i den anden farve, så en tur skal starte og slutte på hjørnernes farve. En lukket tur er umulig der, fordi en løkke, der skifter farve hver gang, har lige mange felter af hver farve. På brætter af lige størrelse findes lukkede ture fra 6×6 og op.

Prøv det i PictorX

Åbn Springertur, og klik på et felt for at starte. De fremhævede felter er de lovlige hop, det gyldne tal er Warnsdorffs valg, og brættet husker rækkefølgen af dine træk. Størrelse sætter brættet fra 5×5 til 10×10, »Lukket tur« beder Løs om en løkke, og Fortryd tager ethvert træk tilbage. Gem den færdige rute som PNG.

Ofte stillede spørgsmål

Hvem studerede springerturen først?

Ture var kendt længe før nogen studerede dem matematisk. Leonhard Euler skrev den første matematiske behandling i 1759, og Warnsdorff gav sin regel i 1823.

Findes der en tur på alle brætter?

Kvadratiske brætter fra 5×5 og op har åbne ture, og dem af lige størrelse fra 6×6 og op har også lukkede ture. Brætter på 2×2, 3×3 og 4×4 har slet ingen tur.

Hvor mange ture har et skakbræt?

Der er 26.534.728.821.064 lukkede ture, hvis en tur og den samme tur gennemløbet baglæns tælles hver for sig. Antallet af åbne ture er omkring 19,6 billiarder.

Uploader PictorX noget?

Nej. Brættet tegnes på et lærred i din browser. Gem henter et PNG, og Rediger åbner billedet i PictorX-editoren.