Startsida | epost | Springarproblemet | Warnsdorff resultat

Warnsdorffs regel II

Inledning: Warnsdorffs regel är heuristik - en tumregel. Den garanterar inte en komplett springartur. Tvärtom, när regeln implementeras med fast prioriteringsordning kan risken för att en springartur slutar i en återvändsgränd inte negligeras.
Det har föreslagits en tilläggsregel, som ger avsevärt bättre resultat.
En underökning av resultaten för regeln och regeln med tillägg på 5x5 - 15x15 rutors bräden redovisas på sidan Warnsdorff resultat, som också närmare förklarar vad som här menas med "fast prioriteringsordning".

På den här sidan finns en Java Applet, som demonstrerar problemen, och som kan användas för att undersöka verkan av fast prioriteringsordning resp. den föreslagna tilläggsregeln.
Som allmänt råd gäller att om Warnsdorffs regel implementeras med fast prioritering, så bör också backtracking tillämpas.

Den här sidan fokuserar på de problem med Warnsdorffs regel, som dyker upp när den skall implementeras för dator.
Arnd Roth pekar i sin "The Problem of the Knight" på den inneboende tvetydigheten i Warnsdorffs regel. Den resulterar ofta i val mellan två eller fler lika "goda" rutor.
Kapil Hari Paranjape observerade in sin underhållande A Knight's Tour on OCaml (when a Python fails to digest it) vikten av i vilken ordning möjliga "nästa-rutor" testas, och vilken betydelse turens startruta har.

Allt detta samverkar. Datorer är inte byggda för att hantera tvetydighet, och ett vanligt sätt att möta problemet är att inte låtsas om det. Varför komplicera saker och ting - varför inte bara använda nästa värde, som min fina algoritm levererar ? (Här talar jag givetvis bara för mig själv.) Men Arnd Roth föreslog ett tillägg till Warnsdorffs regel för att lösa upp tvetydigheten. Om två eller flera "nästarutor" är lika bra, så ska man välja den som är längst bort från brädets centum. På så vis tenderar turen att gå nära brädets ytterkanter, och man motverkar den uppenbara risken att brädet blir delat i två eller flera separata otäckta områden.

Appletten ovan undersöker de här frågorna.
Den hanterar 5x5 - 400x400 rutors bräden, och man kan välja ruta att starta från.
Man kan också välja om man vill använda den av Arnd Roth föreslagna tilläggsregeln, eller om man vill testa möjliga "nästa-rutor enligt en fast prioriteringsordning. I det senare fallet kan man själv ange önskad ordning; man klickar bara på "prio." och därefter på de markerade rutorna i den ordning, som de ska testas. Kom bara ihåg att appletten måste vara stoppad innan inställningarna kan ändras.

Applettens hastighet däremot, kan ändras närhelst så önskas.
För bräden upp t.o.m. 15x15 rutor ges möjlighet att stega igenom springar-turerna drag för drag. Därvid visas antalet fria "utgångar" (röda siffror) samt prioriteringsordning för de möjliga nästa-rutorna. Klicka på nästa-knappen för att se nästa drag.

Första gången en springartur är komplett, och första gången en sådan tvärstoppar i en ruta utan utgångar, så blir det automatiskt paus, och hastigheten skiftas till sakta. Klicka på "forts." och iaktta hur bactracking fungerar. Eller ändra hastigheten - "Fort" är tillräckligt snabbt för att hitta alla "Warndorff turer" på ett 8x8 rutors bräde inom någon minut.

Det finns två inbyggda exempel.
"ex.1" ger ett 50x50 rutors bräde och en prioritering som får springarturen att dela brädet i två separata otäckta delar.
"ex.2" ger ett 8x8 bräde med en prioritering som innebär att en komplett tur uppnås först efter att turen slutat i tvärstopp 35 gånger.

Övning: På ett bräde med udda antal rutor, måste man starta från en mörk ruta för att kunna uppnå en komplett springartur. Förklara varför !

Visitors: