ВУЗ:
Составители:
Рубрика:
40
запись кандидата
if
решение неполное then
begin
Try0(i+1);
if not Success then
стирание кандидата (возврат)
end;
else Success:=True
end;
until Success or
кандидатов больше нет
end;
Отметим, что как только переменная Success получает значение True, мы
выходим из всех рекурсивных вызовов процедуры Try0, не совершая никаких
дополнительных действий.
Рассмотрим реализацию указанного выше алгоритма на примере задачи об-
хода конем шахматной доски размера
nn
×
. Составим вначале внутреннюю про-
цедуру Try0, для которой переменная Success (удача) и массив Solution
(решение) будут глобальными.
Всего из данной клетки конь может совершить максимум 8 ходов, которые
мы пронумеруем так, как показано на рисунке.
Для каждого из этих ходов необходимо проверить, находится ли клетка в
пределах шахматной доски, и не ходил ли конь в эту клетку раньше. Если клетка
– в пределах доски и конь в нее еще не ходил, то мы пробуем совершить в нее
ход, помечая клетку номером хода, после чего, если все
клетки обойдены, то мы
устанавливаем переменную Success в True (решение найдено), в противном
случае вызываем процедуру Try0 повторно с координатами новой клетки в каче-
стве параметра и проверяем, решена ли задача. Если задача не решена, то ход сле-
дует признать неудачным и стереть его из списка ходов (возврат).
Далее приводится
код решения.
program KnightWay;
const
n=8;
dx: array [1..8] of integer=(-1,1,2,2,1,-1,-2,-2);
dy: array [1..8] of integer=(2,2,1,-1,-2,-2,-1,1);
var Solution: array [1..n,1..n] of integer;
// массив ходов
