Заобикаляйки борда шах рицар
Оригиналният правилото, а дават линейно време алгоритъм первази, Varnsdorf (Warnsdorff) бе предложена през 1983 година.
Правилото е формулирана много просто: Следващият ход на коня, за да се направи една клетка, където има възможно най-малко ходове. Ако един и същ брой клетки се движат повече, можете да изберете някоя.
На практика това се реализира, например, както следва. Преди всяко преместване на кон оценява Оценката близкия възможен начин - области, в които конят все още не е бил, и той може да се движи в един ред. поле рейтинг се определя от броя на наличните полета до него. Колкото по-нисък рейтинг, толкова по-добре. Тогава той отбеляза напредък в областта с най-ниската оценка (на който и да е от тези, ако са повече от един), и така нататък, докато не се къде да отида.
Евристики винаги работят по дъските от 5x5 до 76x76 клетки за голяма дъска кон размер може да спре. В допълнение, основана на върховенството на алгоритъма не дава всички възможни решения (т.е. конски песни), можете да отидете в разрез с правилата и все още се получи задоволителен кръг задача.
Съществува линейна алгоритъм за дъски от всякакъв размер, който разделя на борда на малки парчета, но, поради изобилието на специални случаи, това е доста сложно и не толкова интересно, колкото този елегантен евристични методи.
Друг начин за решаване на проблема е, очевидно, в бюста с отстъпление. Следващата илюстрация е даден, за да се обърне към дъска 8х8.
Използване на двуизмерен ред масив [64] и колона [64] за съхраняване на номерата на редовете, съответно, и колони, които последователно преминава кон дъската.
Конят, който е в положение (I, J), може следващия ход да бъде в клетки с координати (I-2, J + 1), (I-1, J + 2), (I + 1, J + 2), ( I + 2. к + 1), (I + 2. к-1), (I + 1, J-2), (I-1, J-2), (I-2, J-1). Имайте предвид, че ако конят е близо до ръба на борда, някои движения могат да причинят на движението на коня отвъд това, разбира се, е неприемливо. Осем възможно кон премествания може да се прилага под формата на два масива ktmov1 [] и ktmov2 [], както е показано в следната програма фрагмент.
Съответно, кон, разположен в позиция (I, J) може да се премести в положение (I + ktmov [к], J + ktmov2 [к]), където к - всяка стойност в диапазона 0 - 7, избран от условията че конят трябва да остане на борда. По този начин, програмата, която изпълнява движение на коня, в съответствие с посочените по-горе условия, ще бъде както следва: