% satrak(a::in,b::out) - a a feladatleíró, b egy megoldás listája
satrak(satrak(Sor, Oszlop, Falista), B) :-
	satrak(5,Falista, [0,0|Sor], Oszlop, [], B).

% satrak(falista::in, sor::in, oszlop::in, satorlista::in, satorhelylista::out)
satrak(_, [], Sor, Oszlop, _, []) :- !, empty(Oszlop), emptySor(Sor).

satrak(0, [Fy-Fx|Falista], SorRégi, Oszlop, SatorlistaRegi, [Direction|Satorhelylista]) :-
			!,		
			sorFrissit(SorRégi,Fy,Sor),
			satorFrissit(SatorlistaRegi,Fy,Satorlista),
			(
			  ( 
			    % első két eset, maradunk az oszlopban:
			    uj(Fx,Oszlop,UjO),
			    ((
			      % első eset, északi irány
			      Direction = n,
			      UjFy is Fy - 1,
			      ujSor(UjFy,Sor,UjSM1),
			      nosatorlistautkozes(Satorlista,UjFy-Fx), % nem ütközik sátorral
			      % nem kell falista ellenőrzés mivel a fák sor szerint növekvően vannak letárolva
			      satrak(10,Falista, UjSM1, UjO, [UjFy-Fx|Satorlista], Satorhelylista)
			    )
			  ;
			    (
			      % második eset a déli irány
			      Direction = s,
			      UjFy is Fy + 1,
			      ujSor(UjFy,Sor,UjSP1),
			      nosatorlistautkozes(Satorlista,UjFy-Fx), % nem ütközik sátorral
			      nofalistautkozes(Falista,UjFy-Fx), % nem ütközik fával
			      satrak(10,Falista, UjSP1, UjO, [UjFy-Fx|Satorlista], Satorhelylista)
			    ))
			  )
			;
			  (
			    % második esetben az azonos sorban maradunk feltételt vesszük elő
			    ujSor(Fy,Sor,UjS),
			    ((
			      % harmadik eset hogy nyugatra megyünk
			      Direction = w,
			      UjFx is Fx - 1,
			      uj(UjFx,Oszlop,UjMO1),
			      nosatorlistautkozes(Satorlista,Fy-UjFx), % nem ütközik sátorral
			      % nem kell falista ellenőrzés mivel a fák soron belül nyugatról keletre vannak felsorolva.
			      satrak(10,Falista, UjS, UjMO1, [Fy-UjFx|Satorlista], Satorhelylista)
			    )
			  ;
			    (
			      % negyedik eset, keleti irány
			      Direction = e,
			      UjFx is Fx + 1,
			      uj(UjFx,Oszlop,UjPO1),
			      ((Falista=[Fa|_])-> ((Fy-UjFx) \== Fa) ; true),
			      %nofalistautkozes(Falista,Fy-UjFx), % nem ütközik fával
			      nosatorlistautkozes(Satorlista,Fy-UjFx), % nem ütközik sátorral
			      satrak(10,Falista, UjS, UjPO1, [Fy-UjFx|Satorlista], Satorhelylista)
			    ))
			  )
			).

satrak(A, [Fy-Fx|Falista], SorRégi, Oszlop, Satorlista, [Direction|Satorhelylista]) :-
			MZX is A - 1,
			sorFrissit(SorRégi,Fy,Sor),
			(
			  ( 
			    % első két eset, maradunk az oszlopban:
			    uj(Fx,Oszlop,UjO),
			    ((
			      % első eset, északi irány
			      Direction = n,
			      UjFy is Fy - 1,
			      ujSor(UjFy,Sor,UjSM1),
			      nosatorlistautkozes(Satorlista,UjFy-Fx), % nem ütközik sátorral
			      % nem kell falista ellenőrzés mivel a fák sor szerint növekvően vannak letárolva
			      satrak(MZX,Falista, UjSM1, UjO, [UjFy-Fx|Satorlista], Satorhelylista)
			    )
			  ;
			    (
			      % második eset a déli irány
			      Direction = s,
			      UjFy is Fy + 1,
			      ujSor(UjFy,Sor,UjSP1),
			      nosatorlistautkozes(Satorlista,UjFy-Fx), % nem ütközik sátorral
			      nofalistautkozes(Falista,UjFy-Fx), % nem ütközik fával
			      satrak(MZX,Falista, UjSP1, UjO, [UjFy-Fx|Satorlista], Satorhelylista)
			    ))
			  )
			;
			  (
			    % második esetben az azonos sorban maradunk feltételt vesszük elő
			    ujSor(Fy,Sor,UjS),
			    ((
			      % harmadik eset hogy nyugatra megyünk
			      Direction = w,
			      UjFx is Fx - 1,
			      uj(UjFx,Oszlop,UjMO1),
			      nosatorlistautkozes(Satorlista,Fy-UjFx), % nem ütközik sátorral
			      % nem kell falista ellenőrzés mivel a fák soron belül nyugatról keletre vannak felsorolva.
			      satrak(MZX,Falista, UjS, UjMO1, [Fy-UjFx|Satorlista], Satorhelylista)
			    )
			  ;
			    (
			      % negyedik eset, keleti irány
			      Direction = e,
			      UjFx is Fx + 1,
			      uj(UjFx,Oszlop,UjPO1),
			      ((Falista=[Fa|_])-> ((Fy-UjFx) \== Fa) ; true),
			      %nofalistautkozes(Falista,Fy-UjFx), % nem ütközik fával
			      nosatorlistautkozes(Satorlista,Fy-UjFx), % nem ütközik sátorral
			      satrak(MZX,Falista, UjS, UjPO1, [Fy-UjFx|Satorlista], Satorhelylista)
			    ))
			  )
			).

nofalistautkozes([], _).
nofalistautkozes([A|Lista], B) :- A \== B, nofalistautkozes(Lista,B).

nosatorutkozes(B-A, Y-X) :-	(Dx is A - X,
				Dy is B - Y,
				Dx < 2,
				Dx > -2,
				Dy < 2,
				Dy > -2), !, fail.
nosatorutkozes(_,_).
nosatorlistautkozes([], _-_).
nosatorlistautkozes([A|Lista], X) :- nosatorutkozes(A,X), nosatorlistautkozes(Lista,X).

% uj(Szam::in, Lista::in, UjLista::out) - a Lista Számadik elemét egyel csökkenti.
uj( 1, [A|Lista], [B|Lista]) :-  !, A \== 0, B is A-1.
uj( M, [A|Lista], [A|Lista2]) :- N is M-1, uj(N,Lista,Lista2).

ujSor(M, [A|Lista], [A|Lista2]) :- 
%A >= 1,
	M1 is M + 1 - A,
	uj(M1,Lista,Lista2).

elhagyNulla(A,Lista,Lista) :-
	A=<0,!.
elhagyNulla(A,[Elem|Lista],ListaKi) :-
%	A>0,
	Elem =< 0,
	A1 is A - 1,
	elhagyNulla(A1,Lista,ListaKi).

% sorFrissit(SorRégi::in,Fy::in,Sor::out)
sorFrissit([A|SorRégi],Fy,[Új|Sor]) :-
	Új is Fy - 1,
	Mennyi is Új - A,
	elhagyNulla(Mennyi,SorRégi,Sor).

%empty(Lista::in)
empty([]).
empty([A|Lista]) :- A =< 0, empty(Lista).

%emptySor(Lista::in)
emptySor([_|Lista]) :- empty(Lista).

% satorFrissit(Satorlista::in,Fy::in,UjSatorlista::out)
satorFrissit([S|Satorlista],Fy,[S|UjSatorlista]) :-
	S = Y-_X,
	Y > (Fy - 5),
%	(Fy-3 =< Y),
	!,
	satorFrissit(Satorlista,Fy,UjSatorlista).
satorFrissit(_,_,[]).