Ход конем

[skorpi]

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

Program hod_konya;
Uses Crt;
const n=8; nsq=64;
type index=1..n;
var i,j:index;
    q:boolean;
    s:set of index;
    a,b:array[1..8] of integer;
    h:array[index,index] of integer;

procedure try (i:integer; x,y:index; var q:boolean);
    var k,u,v:integer; q1:boolean;
begin k:=0;
   repeat k:=k+1; q1:=false;
       u:=x+a[k]; v:=y+b[k];
       if (u in s) and (v in s) then
       if h[u,v]=0 then
       begin h[u,v]:=i;
          if i<nsq then
             begin try (i+1,u,v,q1);
                if not q1 then h[u,v]:=0;
             end else q1:=true
		end
    until q1 or (k=8);
    q:=q1;
end {try};
begin s:=[1,2,3,4,5,6,7,8];
   a[1]:=2;  b[1]:=1;
   a[2]:=1;  b[2]:=2;
   a[3]:=-1; b[3]:=2;
   a[4]:=-2; b[4]:=1;
   a[5]:=-2; b[5]:=-1;
   a[6]:=-1; b[6]:=-2;
   a[7]:=1; b[7]:=-2;
   a[8]:=2; b[8]:=-1;
   for i:=1 to n do
       for j:=1 to n do h[i,j]:=0;
	h[1,1]:=1; try (2,1,1,q); TextColor(10);
    if q then
        for i:=1 to n do
        begin for j:=1 to n do write(h[i,j]:4);
           writeln;
           writeln;
        end
    else writeln('NO SOLUTION');
         readln;
         clrscr;
end.

[TinMan]

Сообщение от skorpi

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

Алгоритм тут простой, я бы сказал - никакой )). Называется "полный перебор с помощью рекурсии". При этом совершенно не важно, сколько коней, моя прога годится как для одного коня, так и для десяти )).

Давай, разбирайся. Отвечу на любые вопросы.

const
  n= 3;  // board size
  m= 2;  // number of horses

type
  tPos= record
    x,y: integer;
  end;

var
  Board: array[1..n,1..n] of integer;

const
  Horse: array[1..m] of tPos= ((x:1;y:1),(x:1;y:2));  // initial positions

function HorseMove(MoveNum: integer; HorseNum: byte): boolean;
const
  z: array[1..2] of ShortInt= (-1,1);
var
  i,j,h,v,a,b: integer;
begin
  with Horse[HorseNum] do begin
    Board[x,y]:= MoveNum;
    if MoveNum=n*n then begin  // тут была ошибка, исправлено
      for i:=1 to n do begin
        for j:=1 to n do Write(Board[i,j]:3);
        WriteLn
      end;
      Halt
    end;
    for h:=1 to 2 do
      for v:=1 to 2 do
        for i:=1 to 2 do
          for j:=1 to 2 do
            if i<>j then begin
              a:= x+z[h]*i;
              b:= y+z[v]*j;
              if (0<a)and(0<b)and(a<=n)and(b<=n) and (Board[a,b]=0) then begin
                x:= a;
                y:= b;
                HorseMove(MoveNum+1,HorseNum mod m+1)
              end
            end;
    Board[x,y]:=0
  end
end;

begin
  FillChar(Board,SizeOf(Board),0);
  HorseMove(1,1);
  WriteLn('complete round of ',n,'x',n,' board with ',m,' horses from given positions is not possible')
end.

Тут рассматривается только одна начальная позиция. Если нужно рассмотреть все возможные (то есть сделать вывод о принципиальной возможности обхода из произвольной точки), то надо добавить перебор начальных позиций тоже (надо подумать, как).

[skorpi]

Спасибо большое за поддержку! Буду разбираться.

[TinMan]

[QUOTE=skorpi;873355]Спасибо большое за поддержку! Буду разбираться./QUOTE]Пожалуйста )). Только погоди - там в коде небольшая опечатка была (осталась от тестирования). Строчка
if MoveNum=n*n-1 then begin
- должна выглядеть так:
if MoveNum=n*n then begin
Я допишу этот мессадж и исправлю в том.

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

const
  n= 8;  // board size
  m= 2;  // number of horses

type
  tPos= record
    x,y: integer;
  end;

var
  Board: array[1..n,1..n] of integer;

const
  Horse: array[1..m] of tPos= ((x:1;y:1),(x:1;y:2));  // initial positions

function HorseMove(MoveNum: integer; HorseNum: byte): boolean;
const
  d: array[1..8] of tPos= ((x:2;y:1),(x:1;y:2),(x:-1;y:2),(x:-2;y:1),(x:-2;y:-1),(x:-1;y:-2),(x:1;y:-2),(x:2;y:-1));
var
  i,j,a,b: integer;
begin
  with Horse[HorseNum] do begin
    Board[x,y]:= MoveNum;
    if MoveNum=n*n then begin
      for i:=1 to n do begin
        for j:=1 to n do Write(Board[i,j]:3);
        WriteLn
      end;
      Halt
    end;
    for i:=1 to 8 do begin
      a:= x+d[i].x;
      b:= y+d[i].y;
      if (0<a)and(0<b)and(a<=n)and(b<=n) and (Board[a,b]=0) then begin
        x:= a;
        y:= b;
        HorseMove(MoveNum+1,HorseNum mod m+1)
      end
    end;
    Board[x,y]:=0
  end
end;

begin
  FillChar(Board,SizeOf(Board),0);
  HorseMove(1,1);
  WriteLn('complete round of ',n,'x',n,' board with ',m,' horses from given positions is not possible')
end.

Жду вопросов.