% A satras feladat.
% Meg nem vegleges valtozat.
% A megoldas otletet es megvalositasi tippeket az elozo evi NHF
% peldamegoldasabol, konkretan cikcakk9_utemezos -bol vettem.


%% nem volt kedven konkretan osszeszedni.
:- use_module(library(lists)).

:- use_module(kenyszerek).

%% TESZT
% :- use_module(backtrack_count).

%% A feladat altal definialt tipusleirasok:
% :- type fLeiro  ---> satrak(sSzS, sSzO, list(parc)).
% :- type sSzS    == list(int).
% :- type sSzO    == list(int).
% :- type parc    == int-int.
% :- type mezo    == parc.
% :- type irany   ---> n    % észak
%                 ;    e    % kelet
%                 ;    s    % dél
%                 ;    w.   % nyugat
% :- type sHelyek   == list(irany).


% satrak(Feladvany, Satrak) :- a Satrak egy megoldasa a Feladvany altal leirt
% feladvanynak.
%
% :- pred satrak(fLeiro::in, sHelyek::out).
satrak(Feladvany, Satrak) :-
	% clear_counter(btracks),
	kenyszerek(Feladvany, Kk, Satrak),
	% utso_kiir,
	megoldhato(valtozott, Kk).
	% visszalep_kiir.

/*
:- type klista == list(kenyszer).
:- type kenyszer ---> fa(irany, fakenyszer)
				% egy fahoz tartozo kenyszer
	         ;    vonal(int, list(mvaltozo)).
				% egy sorhoz vagy oszlophoz
				% tartozo kenyszer
		 ;    mezo(mvaltozo, list(fairany)).
:- type fakenyszer == list(fkelem).
:- type fkelem ---> fkelem(mvaltozo, irany).

:- type vkenyszer == list(mvaltozo).

:- type fairany ---> fairany(irany, irany).
:- type mvaltozo ---> m(foglalt, list(foglalt), irany).
:- type foglalt ---> 0 ; 1.
*/

% type hatas ---> valtozott ; valtozatlan.
% :- pred megldhato(hatas::in, klista::in).
megoldhato(valtozatlan, KL0) :- !,
	(   valasztas(KL0, KL1),
	    megoldhato(valtozott, KL1)
	;
	    nincs_lenyeges_kenyszer(KL0)
	).
megoldhato(_, KL0) :-
	kenyszerlista_szures(KL0, KL1, Hatas),
	megoldhato(Hatas, KL1).

% valasztas(KL) :- a KL kenyszerlistaban az elso fahoz tartozo kenyszerben
% az egyik mezovaltozot "lerogziti" az adott fahoz.
% :- pred valasztas(klista::in)
valasztas(KL0, KL1) :-
	select(fa(Irany,Fk), KL0, KL1), !,
	% choicepoint_made,  % ez nem kell
	member(fkelem(Mv,Irany), Fk),
	% choice_made,
	beallit(1, Mv, _Hatas),
	Mv = m(_,_,Irany).

%% nincs_lenyeges_kenyszer(KL) :- a KL kenyszerlistaban nincs lenyeges: fa ill vonal
%% kenyszer.
%% :- pred nincs_lenyeges_kenyszer(klista::in).
nincs_lenyeges_kenyszer(KL) :-
	\+ member(vonal(_,_), KL),
	\+ member(fa(_,_), KL).

% kenyszerlista_szures(KL0, KL, Hatas) :- a KL0 kenyszerlista KL
% kenyszerlistava egyszerusitheto. Ha tortenik kozben valtozobehelyettesites,
% akkor Hatas = valtozott.
% :- pred kenyszerlista_szures(klista::in, klista::out, hatas::out).
kenyszerlista_szures([], [], _).
kenyszerlista_szures([K|KL], KLe, Hatas) :-
	kenyszer_szures(K, KLe0, KLe, Hatas),
	kenyszerlista_szures(KL, KLe0, Hatas).

% kenyszer_szures(K, KLe0, KLe, Hatas) :- a K kenyszer KLe-KLe0
% kenyszerlistava egyszerusitheto. Hatas = valtozott, ha tortenik kozben
% valtozobehelyettesites.
% :- pred kenyszer_szures(kenyszer::in, klista::in, klista::out, hatas::out).
kenyszer_szures(fa(Ir, Fkk0),KLe0, KLe, Hatas) :-
	(   var(Ir)
	->
	    Fkk1 = [Fk|Fkv],
	    fa_kenyszer_szures(Fkk0, Fkk1),
	    (   Fkv = [] ->
		Fk = fkelem(Mv, Ir),
		beallit(1, Mv, Hatas),
		irany_beallit(Ir, Mv, Hatas),
		KLe = KLe0
	    ;
		KLe = [fa(Ir, Fkk1)|KLe0]
	    )
	;
	    member(fkelem(Mv, Ir), Fkk0),
	    beallit(1, Mv, Hatas),
	    irany_beallit(Ir, Mv, Hatas),
	    KLe = KLe0
	).
kenyszer_szures(vonal(N0, Vkk0), KLe0, KLe, Hatas) :-
	vonal_kenyszer_szures(Vkk0, N0, Vkk, N),
	length(Vkk, H),
	(   N < 0 ->
	    fail
	;	    
	    N =:= 0 ->
	    mind_beallit(Vkk, 0, Hatas),
	    KLe = KLe0
	;
	    N =:= H  ->
	    mind_beallit(Vkk, 1, Hatas),
	    % ( N>0 -> Hatas = valtozott ; true ),
	    KLe = KLe0
	;
	    N < H ->
	    KLe = [vonal(N,Vkk)|KLe0]
	).
kenyszer_szures(Mezo_k, KLe0, KLe, Hatas) :-
	Mezo_k = mezo(Mv, Fak),
	Mv = m(F, _Sz, Ir),
	(   var(F)
	->
	    KLe = [Mezo_k|KLe0]
	;
	    F = 1
	->
	    (   var(Ir)
	    ->
		Fak1 = [FaIr|Famarad],
		eldontetlen_fak(Fak, Fak1),
		(   Famarad = []
		->
		    FaIr = fairany(Fa, Irany),
		    Fa = Irany,
		    Ir = Irany,
		    Hatas = valtozott,
		    KLe = KLe0
		;
		    KLe = [mezo(Mv, Fak1)|KLe0]
		)
	    ;   % F=1, nonvar(Ir).
		KLe = KLe0
	    )
	;   % F = 0
	    KLe = KLe0
	).


%% eldontetlen_fak(Fak0, Fak1) :- Fak1 a Fak0 lista azon tagjai, amiben a
%% fairany(_,_) elso argumentuma (azaz, az olyan iranybol levo fa) meg behelyettesitetlen
%% :- pred eldontetlen_fak(+list(fairany), -list(fairany)).
eldontetlen_fak([], []).
eldontetlen_fak([FaIr|Fak0], Fak) :-
	FaIr = fairany(Fa, _),
	(   nonvar(Fa)
	->
	    Fak = Fak1
	;
	    Fak = [FaIr|Fak1]
	),
	eldontetlen_fak(Fak0, Fak1).

% fa_kenyszer_szures(Fakenyszk, FakenyszkE) :- a Fakenyszk lista FakenyszkE
% listava egyszerusitheto.
% :- pred fa_kenyszer_szures(fakenyszer::in, fakenyszer::out).
fa_kenyszer_szures([], []).
fa_kenyszer_szures([Fk|Fkk], FkkE) :-
	Fk = fkelem(m(Foglalt,_,Ir), Irany),
	(   Foglalt == 0 -> FkkE1 = FkkE
	;
	    % Itt eleg a nonvar(Ir) feltetelnek?
	    Ir \= Irany -> FkkE1 = FkkE
	;
	    FkkE = [Fk|FkkE1]
	),
	fa_kenyszer_szures(Fkk, FkkE1).

% vonal_kenyszer_szures(Vk, N, VkE, NE) :- a Vk,N vonalkenyszer,
% VkE,NE vonalkenyszerre egyszerusitheto.
% :- pred vonal_kenyszer_szures(vkenyszer::in, int::in, vkenyszer::out,
%                               int::out).
vonal_kenyszer_szures([], N, [], N).
vonal_kenyszer_szures([Mv|Mvk], N, MvkE, NE) :-
	Mv = m(Foglalt,_,_),
	(   Foglalt == 1 -> MvkE = MvkE1, N1 is N-1
	;
	    Foglalt == 0 -> MvkE = MvkE1, N1 = N
	;
	    MvkE = [Mv|MvkE1], N1 = N
	),
	vonal_kenyszer_szures(Mvk, N1, MvkE1, NE).

% beallit(Foglalt, Mezo, Hatas) :- a Mezo-t "beallitja" Foglaltra, es ha ez
% tenyeg foglalt, azaz 1, akkor a szomszedait ures-re allitja. Ha helyettsit
% be valtozot, akkor Hatas=valtozot.
% :- pred beallit(foglalt::in, mvaltozo::in, hatas::out).
beallit(1, m(F,Szomsz,_Ir), Hatas) :-
	(   var(F) -> mindures(Szomsz), Hatas=valtozott
	;   true ),
	F = 1.
beallit(0, m(F, _, _), Hatas) :-
	(   var(F) -> Hatas = valtozott
	;   true),
	F = 0.

% irany_beallit(Irany, Mezo, Hatas) :- a Mezo-nek az irany komponenset
% "beallitja" Iranyra. Ha vegez valtozo behelyettesitest, akkor
% Hatas = valtozott.
% :- pred irany_beallit(irany::in, mvaltozo::in, hatas::out).
irany_beallit(Irany, m(_,_,Ir), Hatas) :-
	(   var(Ir) -> Hatas = valtozott
	;   true ),
	Ir = Irany.

%% mind_beallit(Mezok, Foglalt, Hatas) :- az osszes mezot beallitja
%% Foglaltra.
%% Ha helyettesit be, akkor Hatas = valtozott.
%% :- pred mind_beallit1(list(mvaltozo)::in, hatas::out).
mind_beallit([], _, _).
mind_beallit([M|Mk], F, H) :-
	beallit(F, M, H),
	mind_beallit(Mk, F, H).

% mindures(Mk) :- checklist(=(0), Mk).
% Tenyleg, miert nincs checklist a sicstusban?
% :- pred mindures(list(foglalt)::in).
mindures([]).
mindures([0|Mk]) :-
	mindures(Mk).