
% File: cities.pl
% Author: Peter Clark
% Date: 1992
% Purpose: Formulation of the 10 constraints for the `cities' CSP 
% 	   (one) soln is [a,p,l,o,p,o,p]

/*
To run this demo with LPE, do
		% prolog
		| ?- compile(cspdemo).
 		| ?- compile(cities).
 		| ?- demo.

For more information, see the csp_demos/README file.
*/

:- ensure_loaded('../utils').

:- no_style_check(multiple).
:- dynamic 				% declare non-operational goals
	fails/3,
	consec_visits/3,
	not_visit_n_times/5,
	not_visited/4,
	visit_more_than_once/4,
	visit_after/5,
	not_right_after/5,
	visit_on/5,
	not_visit_on/5,
	visit_together/5,
	same_day_visit/5,

	dmember/4,
	not_member/3,
	dremove/5,
	dnmember/3,
	dnmember/4,
	dsub1/2,
	valeq/3,
	dadd1/2,
	vs/1.

% ======================================================================

all_vals(_, [a,b,l,o,p]).
no_of_generators(7).
ordered_generators([1,2,3,4,5,6,7]).
vs([1,2,3,4,5,6,7]).

% The 10 constraints
fails(Hypo, VsInv, 1) :- vs(Vs), consec_visits(Hypo, Vs, VsInv).
fails(Hypo, VsInv, 2) :- vs(Vs), not_visit_n_times(3, p, Hypo, Vs, VsInv).
fails(Hypo, VsInv, 3) :- vs(Vs), not_visited(a, Hypo, Vs, VsInv).
fails(Hypo, VsInv, 4) :- vs(Vs), visit_more_than_once(b, Hypo, Vs, VsInv).
fails(Hypo, VsInv, 5) :- vs(Vs), visit_after(a, p, Hypo, Vs, VsInv).
fails(Hypo, VsInv, 6) :- vs(Vs), not_right_after(o, l, Hypo, Vs, VsInv).
fails(Hypo, VsInv, 7) :- vs(Vs), visit_on(o, 2, Hypo, Vs, VsInv).
fails(Hypo, VsInv, 8) :- vs(Vs), not_visit_on(p, 7, Hypo, Vs, VsInv).
fails(Hypo, VsInv, 9) :- vs(Vs), visit_together(o, b, Hypo, Vs, VsInv).
fails(Hypo, VsInv,10) :- vs(Vs), same_day_visit(1, 6, Hypo, Vs, VsInv).

text(1, 'Can''t visit the same city on two consecutive days').
text(2, 'Must visit paris exactly three times').
text(3, 'Must visit athens at lest once').
text(4, 'Mustn''t visit berlin more than once').
text(5, 'Mustn''t visit athens after any visits to paris').
text(6, 'Must visit oslo directly after any trip to london').
text(7, 'Mustn''t visit oslo on day 2').
text(8, 'Must visit paris on the last day').
text(9, 'If oslo is visited, then berlin mustn''t be visited.').
text(10, 'The city visited first mustn''t also be visited on day 6').

% -------------------- Constraint 1 --------------------

consec_visits(Hypo, [V1,V2|_], [V1,V2]) :- valeq(V1, Hypo, C), valeq(V2, Hypo, C).
consec_visits(Hypo, [_|Vs], VsInv) :- consec_visits(Hypo, Vs, VsInv).

% -------------------- Constraint 2 -------------------- 

not_visit_n_times(0, C, Hypo, Vs, [V]) :-
	dmember(C, Hypo, Vs, V).
not_visit_n_times(N, C, Hypo, Vs, Vs) :-
	N > 0,
	not_member(C, Hypo, Vs).
not_visit_n_times(N, C, Hypo, Vs, [V|VsInv]) :-
	dremove(C, Hypo, Vs, V, RestVs),
	dsub1(N, NewN),
	not_visit_n_times(NewN, C, Hypo, RestVs, VsInv).

dmember(X, Hypo, [V| _], V) :- valeq(V, Hypo, X).
dmember(X, Hypo, [_|Vs], V) :- dmember(X, Hypo, Vs, V).

not_member(_, _, []).
not_member(X, Hypo, [V|Vs]) :- 
	valeq(V, Hypo, Val), 
	X \= Val, 
	not_member(X, Hypo, Vs).

dremove(X, Hypo, [V|Vs], V, Vs) :- valeq(V, Hypo, X).
dremove(X, Hypo, [V|Vs], V2, [V|RestVs]) :- dremove(X, Hypo, Vs, V2, RestVs).

% -------------------- Constraint 3 -------------------- 

not_visited(C, Hypo, Vs, Vs) :- not_member(C, Hypo, Vs).

% -------------------- Constraint 4 -------------------- 

visit_more_than_once(C, Hypo, Vs, [V1,V2]) :-
 	dremove(C, Hypo, Vs, V1, RestVs),
	dmember(C, Hypo, RestVs, V2).

% An alternative:
% visit_more_than_once(C, Hypo, Vs, [V1,V2]) :-
%	dmember(C, Hypo, Vs, V1),
%	dmember(C, Hypo, Vs, V2),
%	V1 \= V2.

% -------------------- Constraint 5 -------------------- 

visit_after(A, P, Hypo, [V|Vs], [V,V2]) :- valeq(V, Hypo, P), dmember(A, Hypo, Vs, V2).
visit_after(A, P, Hypo, [_|Vs], IVs) :- visit_after(A, P, Hypo, Vs, IVs).

% -------------------- Constraint 6 -------------------- 

not_right_after(C2, C1, Hypo, [V1,V2|_], [V1,V2]) :- 
	valeq(V1, Hypo, C1), 
	valeq(V2, Hypo, ActC2),
	ActC2 \= C2.
not_right_after(C2, C1, Hypo, [_|Vs], VsInv) :-
	not_right_after(C2, C1, Hypo, Vs, VsInv).

% -------------------- Constraint 7 -------------------- 

visit_on(C, N, Hypo, Vs, [V]) :- dnmember(V, Vs, N), valeq(V, Hypo, C).

% -------------------- Constraint 8 -------------------- 

not_visit_on(C, N, Hypo, Vs, [V]) :- dnmember(V, Vs, N), valeq(V, Hypo, C2), C2 \= C.

% -------------------- Constraint 9 -------------------- 

visit_together(C1, C2, Hypo, Vs, [V1,V2]) :-
	dremove(C1, Hypo, Vs, V1, RestVs),
	dmember(C2, Hypo, RestVs, V2).

% -------------------- Constraint 10 -------------------- 

same_day_visit(N1, N2, Hypo, Vs, [V1,V2]) :-
	dnmember(V1, Vs, N1), valeq(V1, Hypo, C),
	dnmember(V2, Vs, N2), valeq(V2, Hypo, C).

% ============================================================

% valeq/3: Access the value of constraint variable number VNo
% valeq(+VNo, +ConstraintVariables, -ValOfVarVNo)
valeq(VNo, Vars, Val) :- dnmember(Val, Vars, VNo).

dnmember(Elem, List, N) :-
	dnmember(Elem, List, 1, N).

dnmember(Elem, [Elem|_], N, N).
dnmember(Elem, [_|List], NSoFar, N) :-
	dadd1(NSoFar, NewN),
	dnmember(Elem, List, NewN, N).

dsub1(A, B) :- dadd1(B, A).

dadd1(0,1).
dadd1(1,2).
dadd1(2,3).
dadd1(3,4).
dadd1(4,5).
dadd1(5,6).
dadd1(6,7).

:- style_check(multiple).