» Главная
eXcode.ru » Статьи » Задачи » С решениями
» Новости
» Опросы
» Файлы
» Журнал



Пользователей: 0
Гостей: 9





Шахматный конь




Вывести последовательность ходов шахматного коня, который
обходит доску, посещая каждую клетку по одному разу, если это
возможно.

Ставим коня в произвольную клетку на доске. Из любой клетки
конь имеет не более 8 вариантов для продолжения своего пути,
причем направления этих путей для любой клетки известны.
Поочередно переставляя коня на различные позиции, ищем такую,
которая удовлетворяет условию, что ранее конь на ней не был.
Есди таких вообще позиций нет, то возвращаемся на предыдущую
клетку и так далее.
Таким образом продолжаем движение, пока не будет пройдена вся доска.


{$APPTYPE CONSOLE}
const n=8;d=64;
way:array[1..8,1..2]of -2..2=
((-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1));
{Таким образом задается, куда может сделать следующий ход
конь с текущей позиции}

var i,j,m:1..n;
board:array[1..n,1..n]of boolean;
{Здесь отмечаем клетки, на которых конь уже был}
route:array[1..d,1..2]of char;
{Запоминание координат маршрута "жеребца"}

procedure print;
var i:1..d;
begin writeln(′The Chess Horse′);
for i:=1 to d do write(route[i,1],route[i,2],′ ′);
readln;halt;end;

procedure inspector(p1,p2:integer);
var y,j,i:byte;
begin if m=d then print;
{Если конь сделал 64 "успешных" хода значит вся доска пройдена}
for y:=1 to 8 do begin
i:=p1+way[y,1];j:=p2+way[y,2]; {Шагаем копытом на следующую клетку}
if(i in[1..n])and(j in [1..n])and not(board[i,j])then
begin inc(m);
route[m,1]:=chr(64+i);
route[m,2]:=chr(48+j);
board[i,j]:=true; {Перебор с возвратами}
inspector(i,j);
dec(m);
board[i,j]:=false;
end;
end;
end;

begin
for i:=1 to n do
for j:=1 to n do board[i,j]:=false;
i:=1;j:=1;//readln(i,j);
{Координаты можно и вводить, но далеко не факт, что
путь такой есть и "жеребец" не заблудится. В этом случае программу
нужно завершать извне, так как она зациклится. А можно написать
маленькую функцию проверки на зацикливание и вставить ее
в начало inspector. Но вданном примере целью было показать ход решения.}
m:=1;
route[m,1]:=chr(64+i);
route[m,2]:=chr(48+j);
board[i,j]:=true;
inspector(i,j);end.

К началу статьи





Добавил: EugeneДата публикации: 2006-01-20 19:18:17
Рейтинг статьи:5.00 [Голосов 4]Кол-во просмотров: 8631

Комментарии читателей

Всего комментариев: 1

2006-11-17 21:31:50
Женя
А без Halt слабо решить?
Ваше имя: *
Текст записи: *
Имя:

Пароль:



Регистрация

Какую музыку вы предпочитаете?
Techno
11% (29)
Rap
10% (26)
Rock
48% (126)
Trance
10% (27)
Pop
7% (17)
house
5% (13)
Классическую
7% (19)
Я не слушаю музыку
2% (4)

Проголосовало: 261
Из беседы юзеров: "Как включить Windows, не включая компьютер?"
Рейтинг: 3/10 (3)
Посмотреть все анекдоты