Startsidan | in English | E-post | Springarproblemet | Warnsdorffs regel II


Warnsdorffs regel

I början av 1800-talet kom en praktisk lösningsmetod. Då presenterade H. C. Warnsdorff i "Des Rösselsprungs einfachste und allgemeinste Lösung" (Schmalkalden, 1823) sin metod, för att enkelt konstruera springarfärder.

Det gäller att undvika att skapa återvändsgränder - rutor från vilka springaren inte kan ta sig vidare utan att hamna på en redan besökt ruta. Därför undersöks inför varje drag de nya rutor, som springaren har att välja mellan. Man noterar hur många nya valmöjligheter, fria utgångar, de nya rutorna har, och väljer att gå till den ruta, som har minst med fria utgångar kvar. (Exempel: se [1]

Warnsdorffs regel är en tumregel. Den är inte teoretiskt oantastlig [2], men fungerar bra för ett normalt 8*8 rutors schackbräde

Java appletten på den här sidan demonstrerar Warnsdorffs regels effektivitet:
  1. Klicka på valfri startruta (vänster tangent) så visas antalet fria utgångar för de valbara rutorna. Välj rutan med lägsta siffran, och fortsätt så, tills brädets alla rutor besökts och turen är klar. I många fall presenteras likvärdiga alternativ, och det kan ev. också gå bra att spara någon ruta med få utgångar till senare (för att åstadkomma en sluten tur t.ex.). Rutor med en utgång bör dock besökas genast; de blir annars återvändsgränd. En sådan går bra, kan kanske bli slutruta, men två kan bli problem.
  2. Backa: höger-klicka på redan besökt ruta, så förkortas turen så att det det går att göra om vägvalet från den rutan.
Prova och upptäck hur lätt det är att lösa springarproblemet med hjälp av Warnsdorffs regel !


1. Exempel. Betrakta situationen vid en hörnruta. Från en hörnruta når springaren bara två andra rutor. Och hörnrutan kan bara nås från dess två rutor - hörnrutan har två "utgångar". Om springaren under sin tur hamnar på någon av dessa utgångar är det nästan tvunget att ta hörnrutan som nästa. Annars förvandlas hörnrutan till en återvändsgränd; det är fortfarande möjligt att nå den, men det finns inte längre någon oanvänd utgång därifrån.
Under en springartur reduceras successivt antalet fria utgångar för alla rutor. Warnsdorffs regel avser att styra springaren till rutorna med lägst antal fria utgångar kvar - innan dessa rutor har förvandlats till återvändsgränder.

2. Warnsdorffs regel ger lösningar, men inte samtliga lösningar. (Man kan göra vägval i strid med regeln och ändå uppnå en komplett springarfärd) Det finns ett drag av godtycklighet; vägvalen är ofta likvärdiga enligt regeln. Och på riktigt stora bräden uppstår problem. Warnsdorff hade knappast möjlighet att undersöka den saken, men Arnd Roth vid Max-Planck-institut für Medizinische Forschung presenterar en undersökning i "The Problem of the Knight"

3. Mer om Warsndorffs regels heuristiska natur och vad den egentligen kan prestera finns på Warnsdorffs regel II.


© 1999 Gunno Törnberg
Ändrad 00 03 08 Antal besök: