%%%%%%%%%%%%%%%%%%%%%% Ass 3.1 2009 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
:- set_flag(output_options, [depth(full)]).
:- lib(fd).
%%%%%%%%% parameters %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
size(5,5).
start(1,1).
%%%%%%%%% a) flux related axioms %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
poss(move(Xp,Yp),Z) :- holds(at(X,Y),Z), adjacent(X,Y,Xp,Yp).
state_update(Z,move(Xp,Yp),Zp) :- holds(at(X,Y),Z),
update(Z,[at(Xp,Yp)],[at(X,Y),notVis(Xp,Yp)],Zp).
adjacent(X,Y,Xp,Yp) :-
size(M,N),
Xp::[1..M], Yp::[1..N],
(Xp is X+1, Yp is Y+2;
Xp is X+2, Yp is Y+1;
Xp is X+2, Yp is Y-1;
Xp is X+1, Yp is Y-2;
Xp is X-1, Yp is Y-2;
Xp is X-2, Yp is Y-1;
Xp is X-2, Yp is Y+1;
Xp is X-1, Yp is Y+2
).
%%%%%%%%% b) initialization %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
init(Z) :- allNotVis(NotVis), start(X,Y),
minus_(NotVis,[notVis(X,Y)],NotVis1),
Z = [at(X,Y)|NotVis1].
allNotVis(NotVis) :- size(M,N), allNotVis(1,M,1,N,NotVis).
allNotVis(M,M,N,N,[notVis(M,N)]) :- !.
allNotVis(X,M,Y,N,NotVis) :-
(X =:= M ->
(X1 is 1, Y1 is Y+1)
;
(X1 is X+1, Y1 is Y)
),
allNotVis(X1,M,Y1,N,NotVis1),
NotVis = [notVis(X,Y) | NotVis1].
%%%%%%%%% c) brute force strategy %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
strat1 :- ?(not notVis(_,_)),!.
strat1 :- ?(at(X,Y)),
adjacent_and_not_visited(X,Y,Xp,Yp),
do(move(Xp,Yp)), strat1.
adjacent_and_not_visited(X,Y,Xp,Yp) :-
adjacent(X,Y,Xp,Yp),
?(notVis(Xp,Yp)).
%%%%%%%%% d) strategy with heuristics %%%%%%%%%%%%%%%%%%%%%%%%%%%%
strat2 :- ?(not notVis(_,_)),!.
strat2 :- ?(at(X,Y)), chooseNext(X,Y,Xp,Yp),
do(move(Xp,Yp)), strat2.
chooseNext(X,Y,Xp,Yp) :-
adjacents_without_visited(X,Y,Adj),
pickBest(Adj,(Xp,Yp),_).
pickBest([(X,Y)],(X,Y),N) :-
number_of_succ_positions(X,Y,N),
!.
pickBest([(X,Y)|Rest],(Xb,Yb),Nb) :-
pickBest(Rest,(Xp,Yp),Np),
number_of_succ_positions(X,Y,N),
(N < Np ->
(Xb,Yb) = (X,Y),
Nb is N
;
(Xb,Yb) = (Xp,Yp),
Nb is Np
).
number_of_succ_positions(X,Y,N) :-
adjacents_without_visited(X,Y,Adj),
length(Adj,N).
adjacents_without_visited(X,Y,Adj) :-
findall((Xp,Yp),adjacent_and_not_visited(X,Y,Xp,Yp),Adj).
%%%%%%%%% flux interpreter for ALP %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
:- op(700, fy, not).
:- op(800, xfy, and).
:- op(900, xfy, or).
:- local reference(state).
run(P) :- init(Z), setval(state, Z-s0), call(P),
getval(state, _-S), write_canonical(S), nl.
?(F1 and F2) :- ?(F1), ?(F2), !.
?(F1 or F2) :- ?(F1); ?(F2), !.
?(not not F) :- ?(F), !.
?(not (F1 and F2)) :- ?(not F1 or not F2), !.
?(not (F1 or F2)) :- ?(not F1 and not F2), !.
?(not F) :- getval(state,Z-_), \+ holds(F,Z), !.
?(F) :- getval(state,Z-_), holds(F,Z), !.
do(A) :- getval(state,Z-S), poss(A,Z), state_update(Z,A,Z1),
setval(state,Z1-do(A,S)).
%%%%%%%%% special flux %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
holds(F, [F|_]).
holds(F, Z) :- Z=[F1|Z1], F\==F1, holds(F, Z1).
holds(F, [F|Z], Z).
holds(F, Z, [F1|Zp]) :- Z=[F1|Z1], F\==F1, holds(F, Z1, Zp).
minus_(Z, [], Z).
minus_(Z, [F|Fs], Zp) :-
(\+ holds(F, Z) -> Z1=Z ; holds(F, Z, Z1)),
minus_(Z1, Fs, Zp).
plus_(Z, [], Z).
plus_(Z, [F|Fs], Zp) :-
(\+ holds(F, Z) -> Z1=[F|Z] ; holds(F, Z), Z1=Z),
plus_(Z1, Fs, Zp).
update(Z1, ThetaP, ThetaN, Z2) :-
minus_(Z1, ThetaN, Z), plus_(Z, ThetaP, Z2).