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



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





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




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

Ставим коня в произвольную клетку на доске. Из любой клетки
конь имеет не более 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]Кол-во просмотров: 8825

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

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

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

Пароль:



Регистрация

Какую БД предпочитаете?
MSSQL
20% (38)
BDE
1% (1)
MySQL
35% (68)
Access
6% (11)
InterBase
11% (21)
Paradox
3% (5)
Oracle
10% (19)
PostgreSQL
0% (0)
Другой
3% (6)
Не использую БД!
12% (23)

Проголосовало: 192
Сын спрашивает у отца:
- Папа, а что такое Windows-98?
- Это сынок как обрезание - во-первых, это красиво...
- А во-вторых?
- Когда пытаешься его лечить, может стать еще хуже!
Рейтинг: 4/10 (1)
Посмотреть все анекдоты