%:- use_module(library(lists), [nth/4]).



% takeone (+N, +Lista, -Lista1): 
% Lista N. elem pozitiv, es Lista1 minden eleme megegyezik Lista megfelelo elemevel, de az N. pozicion 1-el kisebbet
%	tartalmaz.
% Lista N. elem negativ, es Lista1 megegyezik Listaval.

takeone(1, A, B) :-
	!, 
	A = [Fej|Farok],
	B = [Fej1|Farok],
	( 
	Fej > 0, !,
	Fej1 is Fej - 1
	;
	Fej < 0, !,
	Fej = Fej1
	).
takeone(N, A, B) :-
	N > 1,
	A = [Fej|Farok],
	B = [Fej|Farok1],
	N1 is N - 1,
	takeone(N1, Farok, Farok1).


% satrak(+Leiro, -SatorHelyek): A Leiro által meghatározott sátor-feladvány 
% megoldása a SatorHelyek égtájlista.
satrak(satrak(Sorosszegek, Oszloposszegek, Fak), Lehetoseg) :-
	length(Sorosszegek, SorokSzama),
	length(Oszloposszegek, OszlopokSzama),
	mat_create(SorokSzama, OszlopokSzama, Terulet),
	helyek(SorokSzama, OszlopokSzama, Sorosszegek, Oszloposszegek, Fak, Lehetoseg, Terulet).
	

%helyek(+SorokSzama, +OszlopokSzama, +Sorosszegek, +Oszloposszegek, +Fak, -Megoldas, +Terulet):
% A megadott felteteleknek megfelelo megoldas Megoldasban kaphato vissza.
helyek(_, _, Sorosszegek, Oszloposszegek, [], [], _) :- 
	!,
	kisebb(Sorosszegek),
	kisebb(Oszloposszegek).


helyek(SorokSzama, OszlopokSzama, Sorosszegek, Oszloposszegek, [FaS-FaO|Fak], [Egtaj|Megoldas], Terulet) :-
	szomszed(Egtaj, Sorkulonbseg, Oszlopkulonbseg),
	SatorS is FaS + Sorkulonbseg,
	SatorO is FaO + Oszlopkulonbseg,
	1 =< SatorS, SatorS =< SorokSzama,
	1 =< SatorO, SatorO =< OszlopokSzama,


	szabad_placc1(SatorS, SatorO, Terulet, Terulet1),
	takeone(SatorS, Sorosszegek, Sorosszegek1),
	takeone(SatorO, Oszloposszegek, Oszloposszegek1),
	helyek(SorokSzama, OszlopokSzama, Sorosszegek1, Oszloposszegek1, Fak, Megoldas, Terulet1).

% szomszed(Egtaj, Sorkulonbseg, Oszlopkulonbseg): Az Egtajnak megfelelő
% szomszéd sorszáma Sorkulonbseg-gel, oszlopszáma Oszlopkulonbseg-gel nagyobb
% mint az eredeti mező sor- ill. oszlopszáma.
szomszed(s, 1, 0).
szomszed(e, 0, 1).
szomszed(n, -1, 0).
szomszed(w, 0, -1).



% mat_create(S, O, Lista) Lista egy S elemu lista, melynek minden eleme egy O elemu lista, melynek minden eleme egyes.
% Foglaltsagi matrix. Lista, amely listakat tartalmaz. Minden reszlista egy sornak felel meg.
mat_create(0, _, []) :- !.
mat_create(S, O, [Fej|Farok]) :- 
	/* S > 0, */
	mat_create(O, Fej),
	S1 is S - 1,
	mat_create(S1, O, Farok).


% mat_create(E, Lista) Lista egy E elemu, kizarolag 1-eseket tartalmazo lista.
mat_create(0, Lista) :- !, Lista = [].
mat_create(E, Lista) :-
	Lista = [1|Farok],
	/* E > 0, */
	E1 is E - 1,
	mat_create(E1, Farok).


%-----------------------------------------------------------------------------



%szabad_placc1(S, O, Lista, Lista1) A Lista1 S. soranak O. elemeben es annak 8 kozvetlen szomszedjaban 0 van,
% masol Lista megfelelo eleme. Lista S. soranak O. elemeben 1 szerepel.
szabad_placc1(2, O, L1, L2) :- !,
	L1 = [Fej1|Farok1],
	L2 = [Fej2|Farok2],
	szabadsor1(O, _, Fej1, Fej2),
	szabad_placc2(Farok1, 1, O, Farok2).

szabad_placc1(1, O, L1, L2) :- !,
	L1 = [Fej1|Farok1],
	L2 = [Fej2|Farok2],
	szabadsor1(O, 1, Fej1, Fej2),
	szabad_placc3(Farok1, O, Farok2).

szabad_placc1(S, O, L1, L2) :- !, 
/* S>2, */
S1 is S - 1,
	L1 = [F|Lista1],
	L2 = [F|Lista2],
	szabad_placc2(Lista1, S1, O, Lista2).


% L2 elso eleme 0, a tobbi L1 megfelelo elemevel egyezik meg, vagy mindket lista ures.
szabad_placc3([], _, L2) :- !,
	L2 = [].
szabad_placc3([Fej1|Farok], O, L2) :- !,
	L2 = [Fej2|Farok],
	szabadsor1(O, _, Fej1, Fej2).

	


% A szabadsor1 es szabadsor2 egymast hivjak jobbrekurzivan, ezt a Prolog az utolso hivas optimalizalasa szerint gyorsitja.
% mindket eljaras a prolog szamara felismerhetoen determinisztikus.
% szabad_placc2(Lista, S, O, Lista2) :- Vagy Lista es Lista1 ures listak, vagy szabad_placc1(S, O, Lista, Lista2).
szabad_placc2([], _, _, Lista2) :-
	Lista2 = [].
szabad_placc2([A|B], S, O, Lista2) :-
	szabad_placc1(S, O, [A|B], Lista2).


%-----------------------------------------------------------------------------



% szabadsor1(O, Cel, Lista, Lista1) :- Cel a Lista O. eleme. Ha letezik Listaban O-1. es/vagy O+1. elem, azok
% Lista1-ben nullak.
szabadsor1(2, S, L1, L2) :- !,
	L1 = [_|Farok1],
	L2 = [0|Farok2],
	szabadsor2(Farok1, 1, S, Farok2).

szabadsor1(1, S, L1, L2) :- !,
	L1 = [S|Farok1],
	L2 = [0|Farok2],
	szabadsor3(Farok1, Farok2).

szabadsor1(N, S, L1, L2) :- !, 
	/* N>2, */
	N1 is N - 1,
	L1 = [F|Lista1],
	L2 = [F|Lista2],
	szabadsor2(Lista1, N1, S, Lista2).


% L2 elso eleme 0, a tobbi L1 megfelelo elemevel egyezik meg, vagy mindket lista ures.
szabadsor3([], L2) :- !,
	L2 = [].
szabadsor3([_|Farok], L2) :- !,
	L2 = [0|Farok].

	


% A szabadsor1 es szabadsor2 egymast hivjak jobbrekurzivan, ezt a prolog az utolso hivas optimalizalasa szerint gyorsitja. mindket eljaras a prolog szamara felismerhetoen determinisztikus.
% szabadsor2(Lista1, N, S, Lista2) Lista1 es Lista2 uresek, vagy szabadsor1(N, S, Lista1, Lista2).
szabadsor2([], _, _, Lista2) :- !, 
	Lista2 = [].
szabadsor2([A|B], N, S, Lista2) :-
	szabadsor1(N, S, [A|B], Lista2).


% kisebb(Lista) Lista minden eleme szigoruan kisebb, mint 1.
kisebb([]).
kisebb([F|Farka]) :-
	F<1,
	kisebb(Farka).