Megkerülve a tábla sakk lovag

Az eredeti szabály, amely egy lineáris idejű algoritmust szegélylécek, Varnsdorf (Warnsdorff) javasolták 1983-ban.

A szabály megfogalmazása nagyon egyszerű: a következő lépés a ló, hogy nem egy cellában, ahol a lehető legkevesebb mozog. Ha ugyanaz a sejtek száma a mozgást, akkor lehet választani.

A gyakorlatban ez nem valósul meg, például, a következők szerint. Mielőtt minden mozog a ló értékelték értékelés legközelebbi elérhető területeken - mely területeken a ló még nem volt, és tudja mozgatni egy körben. Értékelés mező határozza meg a rendelkezésre álló területek mellette. Minél alacsonyabb a minősítés, annál jobb. Aztán előrelépést tett a helyszínen a legalacsonyabb minősítés (a bármely olyan, ha egynél több), és így tovább, amíg van hová menjen.

A heurisztika mindig dolgoznak a táblák 5x5 legfeljebb 76x76 sejtek nagy tábla mérete ló megtorpant. Ezen túlmenően, a szabályon alapulnak az algoritmus nem ad az összes lehetséges megoldást (azaz ló sávok), akkor mehet a szabályok ellen, és még mindig kielégítő kerek feladat.

Van egy lineáris algoritmus táblák bármilyen méretű, amely elválasztja a tábla kisebb darabokra, de azért, mert a rengeteg különleges esetekben, ez elég bonyolult, és nem olyan érdekes, mint az elegáns heurisztikus.

Egy másik módja a probléma megoldásának, nyilván, a mellszobor visszavonulást. Az alábbi ábra adott megközelíteni a fedélzeten 8x8.

Használata kétdimenziós tömbben sorban [64] és a Col [64] tárolására a sorszámokról, illetve és oszlopok egymás ló áthalad a fedélzeten.

A ló, amely abban a helyzetben (i, j), akkor a következő lépés, hogy a sejtekben koordinátái (i-2, j + 1), (i-1, j + 2), (i + 1, j + 2), ( i + 2 j + 1), (i + 2 j-1), (i + 1, j-2), (i-1, j-2), (i-2, j-1). Vegye figyelembe, hogy ha a ló szélén a tábla, néhány lépést is okozhat a mozgás a ló túl, hogy természetesen elfogadhatatlan. Nyolc lehetséges elmozdulások ló lehet adni formájában két tömb ktmov1 [] és ktmov2 [], amint azt az alábbi program fragmens.

Ennek megfelelően, ló, pozícióban található (i, j) mozogni tud egy olyan helyzetbe, (i + ktmov [k], j + ktmov2 [k]), ahol k - bármilyen értéket a tartományban 0-7 kiválasztott feltételekkel hogy a ló maradjon a táblán. Így a program, amely megvalósítja a mozgás a ló összhangban a fenti feltételek a következők lesznek: