program sortowanie_plikow;
const w		 = 4;
   max		 = w*w; { max = w*w }
type plansza = array [1..w,1..w] of byte;
   ruch		 = record
				  w,k,nr : integer;
				  done	 : boolean
			   end;		 
   stos		 = record 
				  t	  : array[1..7*max] of ruch;
				  top : integer
			   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
   s.top := 0
end; { gen_stos }

function pusty(s : stos) : boolean;
begin
   pusty := s.top=0
end; { pusty }

function pelny(s : stos) : boolean;
begin
   pelny := s.top=max
end; { pelny }

procedure zdejmij(var r: ruch; var s : stos);
begin
   if pusty(s) then
	  writeln('stos pusty!!')
   else
   begin
	  r := s.t[s.top] ;
	  s.top:= s.top-1
   end
end; { zdejmij }

procedure dodaj(r: ruch; var s : 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);
   if pelny(s) then
	  writeln('stos pelny!!')
   else
   begin
	  s.top:= s.top+1;
	  s.t[s.top] := r
   end
end; { dodaj }

procedure drukuj(pl: plansza);
(* drukuje plansze *)
var i, j : integer;
begin
   writeln('kolejna plansza');
   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;
					 if mozliwy_skok(rp,p) then
						dodaj(rp,s)
				  end
			end
		 until pusty(s) 
	  end;
   writeln('KONiEC')
end.