program sortowanie_plikow;
const w		 = 5;
   max		 = w*w; 
type plansza = array [1..w,1..w] of byte;
   ruch		 = record
				  w,k,nr : integer;
				  done	 : boolean
			   end;		 
   stos		 = ^elem;
   elem		 = record 
				  top  : ruch;
				  nast : stos
			   end;	   
var p	   : plansza;
   s	   : stos;
   r,rp	   : ruch;
   i,j	   : byte;
   wie,kol : array [1..8] of integer;
procedure gen_stos(var s: stos);
begin
   release(s);
   s := nil
end; { gen_stos }

function pusty(s : stos) : boolean;
begin
   pusty := s=nil
end; { pusty }

function pelny(s : stos) : boolean;
begin
   pelny := false
end; { pelny }

procedure zdejmij(var r: ruch; var s : stos);
var st : stos;
begin
   if pusty(s) then
	  writeln('stos pusty!!')
   else
   begin
	  r := s^.top ;
	  st := s^.nast;
	  release(s);
	  s :=st
   end
end; { zdejmij }

procedure dodaj(r: ruch; var s : stos);
var st :  stos;
   procedure druk(s: stos);
   var r : ruch;
   begin
	  if not pusty(s) then
	  begin
		 zdejmij(r,s);
		 writeln(r.w:4,r.k:4,r.nr:4);
		 druk(s)
	  end
	  else 
		 writeln('koniec stosu');
   end;
begin
{   druk(s); }
   new(st);
   if pelny(s) then
	  writeln('stos pelny!!')
   else
   begin
	  st^.nast := s;
	  st^.top := r;
	  s := st
   end
end; { dodaj }

procedure drukuj(pl: plansza);
(* drukuje plansze *)
var i, j : integer;
begin
   for i := 1 to w do
   begin
	  for j := 1 to w do
		 write(pl[i,j]:4);
	  writeln
   end;
   writeln
end; { drukuj }

procedure generuj(var pl : plansza);
(* generuje PUSTA plansze *)
var i, j : integer;
begin
   for i := 1 to w do
	  for j := 1 to w do
		 pl[i,j]:=0;
end; { generuj }

function mozliwy_skok(r	: ruch; pl:plansza) : boolean;
begin
   mozliwy_skok := (1<=r.w) and (r.w<=w) and (1<=r.k) and (r.k<=w) and (pl[r.w,r.k]=0);
end; { mozliwy_skok }

begin
   wie[1]:= 1;  kol[1]:= 2;
   wie[2]:= 1;  kol[2]:=-2;
   wie[3]:=-1;  kol[3]:= 2;
   wie[4]:=-1;  kol[4]:=-2;
   wie[5]:= 2;  kol[5]:= 1;
   wie[6]:= 2;  kol[6]:=-1;
   wie[7]:=-2;  kol[7]:= 1;
   wie[8]:=-2;  kol[8]:=-1;

   for i:= 1 to (w+1)div 2 do
	  for j := 1 to i do
	  begin
		 generuj(p); { czyscimy plansze }
		 r.w := i;
		 r.k := j;
		 r.done := false;
		 r.nr := 1; { kreujemy piersze miejsce skoczka na planszy }
		 gen_stos(s); { generujemy pusty stos }
		 dodaj(r,s);   { dodajemy pierwszy ruch do stosu }
		 repeat
			zdejmij(r,s);
			if r.done then
			   p[r.w,r.k] := 0  { zdejmujemy pionka z nowego miejsca }
			else if mozliwy_skok(r,p) then
			begin
			   p[r.w,r.k] := r.nr;  { stawiamy pionka na nowe miejsce }
{			   drukuj(p); }
			   r.done := true;
			   dodaj(r,s);
			   if r.nr = w*w then
				  drukuj(p)
			   else
				  for i:= 1 to 8 do
				  begin
					 rp.w := r.w + wie[i];
					 rp.k := r.k + kol[i];
					 rp.nr := r.nr+1;
					 rp.done := false;
					 dodaj(rp,s)
				  end
			end
		 until pusty(s) 
	  end;
   writeln('KONiEC')
end.