Re: Обход доски шахматным конем

From

Dmitriy K. ()

To

Roman Zhelnov

Date

2002-07-22T15:59:08Z

Area

RU.ALGORITHMS

From: "Dmitriy K." <krylov@mail.primorye.ru>

Привет.

"Roman Zhelnov" <Roman.Zhelnov@p29.f25.n5053.z2.fidonet.org>
сообщил/сообщила в новостях следующее:
news:1027250589@p29.f25.n5053.z2.FIDOnet.ftn...
>
>  [√] Привет, как жизнь, All ?
>
>   Интересует алгоритм обхода доски шахматным конем. На одну клетку можно
> вставать только один раз...

На - другую - тоже один раз, на третью - один раз и т.д. Рекурсия!

----8<----8<----8<----8<----8<----8<----8<----8<----8<----8<----8<----8<----

program MoveOfTheKnight;

const
  DeskSize = 8; { Размер доски }
type
  TCoords = 1..DeskSize; { возможные координаты доски }
  TDesk = array[TCoords, TCoords] of Boolean; { Доски. Клетка либо пройдена,
либо нет }
  TMove = record { ход }
    X: TCoords;
    Y: TCoords;
  end;

const
  NumOfKnightSteps = 8; { количество шагов конем из некоторого положения }

type
  TKnightSteps = 1..NumOfKnightSteps;

const
  KnightSteps: array[TKnightSteps] of record
    DeltaX, DeltaY: Shortint
  end = (
   (DeltaX: -1; DeltaY: -2),
   (DeltaX: 1;  DeltaY: -2),
   (DeltaX: 2;  DeltaY: -1),
   (DeltaX: 2;  DeltaY: 1),
   (DeltaX: -1; DeltaY: 2),
   (DeltaX: 1;  DeltaY: 2),
   (DeltaX: -2; DeltaY: -1),
   (DeltaX: -2; DeltaY: 1));

var
  Desk: TDesk; { Доска }
  MakedMoves: Integer; { Количество сделанных конем ходов }

const
  MaxMoves = DeskSize * DeskSize; { Максимальное количество ходов }

var
  Moves: array[1..MaxMoves] of TMove;

////////////////////////////////////////////////////////////////////////////

procedure PrintMoves; forward; { Вывод на экран результатов }

{ перемещение коня }
{ на входе: Pos - текущая позиция коня }
procedure Go(X, Y: TCoords);
var
  i: TKnightSteps;
  NewX, NewY: Shortint;
begin
  { Помечаем позицию, в которую пришли }
  {  Writeln(MakedMoves); }
  Desk[X, Y] := True;
  Inc(MakedMoves);
  Moves[MakedMoves].X := X;
  Moves[MakedMoves].Y := Y;
  if MakedMoves = MaxMoves then
    PrintMoves { Ну вот, обшагали всю доску, результаты - на экран }
  else
  begin
    { Пытаемся найти подходящий ход }
    for i := 1 to NumOfKnightSteps do
    begin
      { Вычисление очередных координат }
      NewX := X + KnightSteps[i].DeltaX;
      if (NewX < 1) or (NewX > DeskSize) then Continue; { Выход за границы
доски - пропускаем }
      NewY := Y + KnightSteps[i].DeltaY;
      if (NewY < 1) or (NewY > DeskSize) then Continue; { Выход за границы
доски - пропускаем }
      if not(Desk[NewX, NewY]) then Go(NewX, NewY); { Место не занято -
ходим туда }
    end; { for... }
  end; { if... }
  { Откат - помечаем позицию как непройденную }
  Desk[X, Y] := False;
  Dec(MakedMoves);
end;

procedure PrintMoves; { Вывод на экран результатов }
var
  i: Integer;
begin
  for i := 1 to MaxMoves do
    with Moves[i] do
      Write(X, ',', Y, '; ');
  Writeln;
  Writeln;
end;

begin
  { Обнулирование ;-) }
  FillChar(Desk, SizeOf(Desk), 0);
  MakedMoves := 0;
  Go(1, 1);
  WriteLn('Any Enter to continue...'); ReadLn;
end.

----8<----8<----8<----8<----8<----8<----8<----8<----8<----8<----8<----8<----

Для случая 3x3 и необходимости обойти все поля, кроме центрального,
программка работает на ура.

Естественно, можно оптимизировать. Например, конь сделает только 64 хода,
так что можно избежать рекурсии, а сделать итерацию; посмотреть, как он
обходит и т.д.

Еще можно использовать факт симметрии доски и ходов - например, за один шаг
рекурсии делать не один шаг конем а все восемь в доступных направлениях.

>
>  [√] Пока, All, счастливого тебе коннекта ! ...

Та же фигня.



-- 
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
 * Origin: Talk.Mail.Ru (2:5020/400)