Springarens färd

Problemet kan begränsas genom att kravet att turen skall vara sluten; att slutrutan skall vara på springarstegs avstånd från startrutan .

I dagens läge med datorer kan man möjligen tycka att problemet borde vara löst. Ett sätt är ju att helt enkelt låta datorn pröva alla möjliga vägar, som springaren kan välja på. De flesta slutar i en återvändsgränd - springaren kommer till en ruta varifrån den inte kan ta sig utan att hamna på en ruta, som redan besökts. Då backar man ett steg och provar ett annat vägval. Och har man redan provat alla val där, får man backa ett steg till. Osv. Backtracking kallas strategin, och är ofta användbar.

På ett normalt 8 * 8 rutors schackbräde visar sig problemet vara oväntat stort. Faktiskt så stort, att direkt räkning av springarfärder, ligger utom räckhåll också med dagens snabba datorer. Det behövs andra angreppssätt.

Martin Löbbing och Ingo Wegener skrev 1995 en artikel med den slående rubriken: "The Number of Knight's Tours equals 33,439,123,484,294 -- Counting with Binary Decision Diagrams". De nådde sitt resultat genom att köra 20 Sun-stationer i fyra månader (spilltid, effektiv CPU-tid var mindre).
Brendan McKay kom med en kommentar 18 feb 1997. Han hade använt en annan metod (delat brädet i två hälfter) och fått resultatet 13,267,364,410,532.   [4]

För att få en uppfattning om dessa tals storlek, betrakta en dator, som söker och hittar en miljon turer i minuten (266 MHz PC). Kan förefalla hyggligt snabbt, men datorn behöver icke desto mindre mer än 9,213 dygn - dvs. mer än 25 år - för att nå Brendan McKays antal turer.

• Java-appletten på den här sidan utnyttjar sökning med backtracking förstärkt med ett par algoritmer, som tidigt avbryter utsiktslösa sökvägar. (Annars behöver en renodlad backtracking-strategi 3 430 271 572 drag innan den hittar den första hela turen - vilket nog bleve tradigt. Nu räcker 94 drag) Klicka på brädet med vänster mustangent för att följa sökningen drag för drag. Använd höger mustangent för att få hela kompletta turer på en gång

Egentligen behöver man inte använda backtracking för att åstadkomma en springartur. Det finns en gammal effektiv metod som går rakt på målet. Den beskrivs och demonstreras på nästa sida om Warnsdorffs regel

2. Mark R. Keen berätttar mer om om problemets historia och grafteori i en vacker uppsats: "THE KNIGHT'S TOUR"

3. George Peter Jelliss ger en inträngande historia/bibliografi över problemet i sin Knight's Tour Notes. (Startar 2200 f.Kr. !)

4. De omnämnda artiklarna finns i the Electronic Journal of Combinatorics, Volume 3,(no 1)
Båda i postscript-format; direkt läsbart finns där en sammanfattning ("Abstract") och kommentarer ("Comments").
(Martin Löbbing och Ingo Wegener har senare gjort om sin körning, som var behäftad med fel - se "Comments" ovan - och bekräftat Brendan McKays resultat. Den gemensamma uppsatsen om detta är ännu inte skriven. [privat korrespondens med Brendan McKay]).

5. I Japan görs det med hjälp av neurala nätverk ! Här en Java applett:
Takayuki Saito har gjort Neural Network Demonstration for Knight's Tour Problems
Ytterst fascinerande, fast den har en tendens att alstra flera oberoende turer på samma bräde, i st.f. en sammanhängande. Möjligen en konsekvens av den använda tekniken.