Задача про шахматного коня

program go;

{$mode objfpc}{$H+}

type
THod=record    // тип данных для описания относительного хода через два смещения
  ox:shortint; // смещение по горизонтали
  oy:shortint; // смещение по вертикали
  num:shortint; // номер относительного хода
  end;
TCoord=record // тип данных для описания координат коня
 x:shortint;
 y:shortint;
end;
TPath=array[1..64] of Thod;
const
   RelHohs:array[1..8]of Thod=(     // константа-массив со списком относительных ходов
                             (ox:1; oy:2;num:1),
                             (ox:2; oy:1;num:2),
                             (ox:2; oy:-1 ;num:3),
                             (ox:1; oy:-2 ;num:4),
                             (ox:-1;oy:-2 ;num:5),
                             (ox:-2;oy:-1 ;num:6),
                             (ox:-2;oy:1;num:7),
                             (ox:-1;oy:2;num:8)
                             );

function go( start:TCoord;dest:Tcoord; Nmax:integer;var pathindex:integer; var path:TPath ):boolean;
var
  i:integer;
  r:boolean;
  tmp:TCoord;
begin

   if Nmax<1  then
      begin
        Result:=false;
        exit;
      end;
   pathindex:=pathindex+1;
   for i:=1 to 8 do
   begin
     // сделать ход
     tmp:=start;
     tmp.x:=RelHohs[i].ox+tmp.x;
     tmp.y:=RelHohs[i].oy+tmp.y;
     if (tmp.x<1) or (tmp.y<1) or (tmp.x>8) or (tmp.y>8) then
        continue;
     path[pathindex]:=RelHohs[i];
     // проверить, попадает-ли ход в точку назначения
     if (tmp.x=dest.x) and (tmp.y=dest.y) then
        begin
          Result:=true;
          exit;
        end;
     r:=go(tmp,dest,Nmax-1,pathindex,path);
     if r then
        begin
          Result:=true;
          exit;
        end;
   end;
   Result:=false;
end;

var
  s,d:TCoord;
  p:TPath;
  pi:integer;
  i:integer;
  found:boolean;
begin
  s.x:=3; s.y:=2;
  d.x:=7; d.y:=3;
  for i:=1 to 8 do
  begin
    pi:=0;
    if go(s,d,i,pi,p) then
       begin
         found:=true;
         break;
       end;
  end;
  writeln(found);
  for i:=1 to pi do
    writeln(p[i].num);
  readln;
end.

nextposs (c,r) = filter inboard . map (\(x,y) -> (c+x, r+y)) $
    [(-2,-1),(-2,1),(-1,-2),(-1,2),(1,-2),(1,2),(2,-1),(2,1)]
        where inboard (c,r) = c>0 && c<9 && r>0 && r<9

task a b = map (reverse . map c2f) $ go [[f2c a]] where
    go l | null dest = go $ l >>= steps
         | otherwise = dest where
        dest = filter ((== f2c b) . head) l
        steps sc = map (:sc) . nextposs . head $ sc

c2f (c,r) = ['@'..] !! c : show r

f2c (c:r) = (fromEnum c - fromEnum 'A' + 1, read r :: Int)

main = print $ task "B2" "D4"

{
Модуль с помощью рекурсии ищущий все короткие пути коня из начальной точки в конечную
}
unit recur2;

interface

type
THod=record    // тип данных для описания относительного хода через два смещения
  ox:shortint; // смещение по горизонтали
  oy:shortint; // смещение по вертикали
  num:shortint; // номер относительного хода
  end;
TCoord=record // тип данных для описания координат коня
 x:shortint;
 y:shortint;
end;
TPath=array[1..64] of Thod;
TOnePath=record
   length:integer;
   path:TPath;
end;
TAllPaths=record
   length:integer;
   paths:array [1..500] of TOnePath;
end;
const
   RelHohs:array[1..8]of Thod=(     // константа-массив со списком относительных ходов
                             (ox:1; oy:2;num:1),
                             (ox:2; oy:1;num:2),
                             (ox:2; oy:-1 ;num:3),
                             (ox:1; oy:-2 ;num:4),
                             (ox:-1;oy:-2 ;num:5),
                             (ox:-2;oy:-1 ;num:6),
                             (ox:-2;oy:1;num:7),
                             (ox:-1;oy:2;num:8)
                             );


function horse_go(start:TCoord;dest:TCoord;var count:integer;var paths:TAllPaths):boolean;

implementation


procedure go( start:TCoord;dest:Tcoord; Nmax:integer;var pathindex:integer; var path:TPath;var paths:TAllPaths;var found:boolean );
var
  i,j,k,m:integer;
  tmp:TCoord;
  curr_paths_length:integer;
begin

   if Nmax<1  then
        exit;
   pathindex:=pathindex+1;
   for i:=1 to 8 do
   begin
     // сделать ход
     tmp:=start;
     tmp.x:=RelHohs[i].ox+tmp.x;
     tmp.y:=RelHohs[i].oy+tmp.y;
     if (tmp.x<1) or (tmp.y<1) or (tmp.x>8) or (tmp.y>8) then
        continue;
     path[pathindex]:=RelHohs[i];
     // проверить, попадает-ли ход в точку назначения
     if (tmp.x=dest.x) and (tmp.y=dest.y) then
        begin
          paths.length:= paths.length +1;
          paths.paths[paths.length].length:=pathindex;
          for j:=1 to pathindex do
              paths.paths[paths.length].path[j]:=path[j];
          found:=true;
          pathindex:=pathindex-1;
          exit;
        end;
     go(tmp,dest,Nmax-1,pathindex,path,paths,found);
   end;
   pathindex:=pathindex-1;
end;

function horse_go(start:TCoord;dest:TCoord;var count:integer;var paths:TAllPaths):boolean; // возвращает первый из кратчайших путей коня из точки start в точку dest
 var
   pi:integer;
   i:integer;
   found:boolean;
   path:TPath;
begin
   found:=false;
  for i:=1 to 16 do
  begin
    pi:=0;
    go(start,dest,i,pi,path,paths,found);
    if found then
         break;
  end;
  if found  then
     begin
       Result:=true;
       count:=pi;
     end;
end;


begin
end.