edge(reg(s(0)),reg(s(s(0)))).
edge(reg(s(0)),reg(s(s(s(0))))).
edge(reg(s(s(0))),reg(s(s(s(0))))).

nat(0).
nat(s(N)) :- nat(N).

to_nat(0,0).
to_nat(I,s(N)) :- I1 is I - 1, to_nat(I1,N), !.

to_number(0,0).
to_number(s(N),I) :- to_number(N,I1), I is I1 + 1, !.

reg(X) :- nat(X).

%le(s(0),_)./errata/
le(0,_).
le(s(M),s(N)) :- le(M,N).

%aggiunto
range(X,I,S):-le(I,X),le(X,S).
%aggiunto
eq(0,0).
eq(s(X),s(Y)):-eq(X,Y).

%allRegions([put(_,_)], s(0)).
%allRegions([put(_,reg(R))|[put(_,reg(s(R)))|Ps]],s(N)) :-
%	allRegions([put(_,reg(s(R)))|Ps],N).

%caso base?
add(put(col(C),R1),[],N,K).
add(put(col(C),R1),[put(col(C),R2)|Ps],N,K) :- !,\+edge(R1,R2),add(put(col(C),R1),Ps,N,K).
add(put(col(C1),R1),[put(col(C2),_)|Ps],N,K) :- add(put(col(C1),R1),Ps,N,K).
%add(put(col(C1),R1),[put(col(C2),R2)|Ps],N,K) :- eq(C1,C2),\+edge(R1,R2),add(put(col(C1),R1),Ps,N,K).
%add(put(col(C1),R1),[put(col(C2),_)|Ps],N,K) :- \+eq(C1,C2),add(put(col(C1),R1),Ps,N,K).

%noConflict([put(col(C),_)],N,K) :- le(C,K).
%noConflict([put(col(C),R)|Ps],N,K) :- noConflict(Ps,N,K),add(put(col(C),R),Ps,N,K).
noConflict([put(col(C),_)],N,K) :- range(C,s(0),K).
noConflict([put(col(C),R)|Ps],N,K) :- noConflict(Ps,N,K),add(put(col(C),R),Ps,N,K).

%colored(P,N,K) :- allRegions(P,N),noConflict(P,N,K).
colored(P,N,K) :- allRegions(P,N,K),noConflict(P,N,K).

color(s(0),r).
color(s(s(0)),g).
color(s(s(s(0))),b).

%solution(P,NP).
solution([put(col(C),reg(R))],[put(col(X),reg(N))]) :- color(C,X),to_number(R,N).
solution([put(col(C),reg(R))|Ps],[put(col(X),reg(N))|NPs]) :- 
	solution(Ps,NPs),color(C,X),to_number(R,N).

%nuova allRegions.
%allRegions([put(_,reg(s(0)))|Ps],s(N)) :- addR(Ps,s(0),N).
allRegions([put(col(X),reg(s(0)))|Ps],s(N),K) :- range(X,s(0),K),addR(Ps,s(0),N,K).
addR([],M,0,K).
%addR([put(_,reg(s(K)))|Ps],K,s(N)) :- addR(Ps,s(K),N).
addR([put(col(X),reg(s(Y)))|Ps],Y,s(N),K) :- range(X,s(0),K),addR(Ps,s(Y),N,K).

%altra soluzione, peggiore, fa uso di reverse
%reverse([]).
%reverse([X|Xs]) :- append(Xs,[X]).	%append built-in di sistema
