:-use_module(library(clpfd)).

% simple enumeration
enum([]).
enum([H|T]):-
	indomain(H), % enumerate domain
	enum(T).

% step labeling
step([]).
step([H|Rest]):-
	fd_min(H,Value),
	(H#=Value ; H#\=Value),
	(var(H) ->
		step([H|Rest])
	;	step(Rest)).

% bisection labeling
bisection([]).
bisection([H|Rest]):-
	fd_min(H,Min), fd_max(H,Max),
	Middle is integer((Min+Max)/2),
	(H#=<Middle ; H#>Middle),
	(var(H) ->
		bisection([H|Rest])
	;	bisection(Rest)).

% generic search procedure
label([]).
label(Variables):-
	select_variable(Variables,V,Rest),!,
	choice_point(V),
	(var(V) ->
		label([V|Rest])
	;	label(Rest)).

% simple enumeration for a generic search procedure
select_variable([H|T],H,T).
choice_point(V):-indomain(V).

% simple minimization algorithm
minimizeSimple(Vars,X):-
	fd_min(X,X),
	label(Vars),!.
minimizeSimple(Vars,X):-
	fd_min(X,Min),
	X#>Min,
	minimizeSimple(Vars,X).

% minimization using Branch&Bound
minimizeBB(Vars,X,InitialBound):-
	bb_put(bound,InitialBound),	% save upper bound
	minBB(Vars,Vars,X).
minimizeBB(Vars,_,_):-
	bb_get(best,Vars).	% restore best solution

minBB([],AllVars,X):-		% all variables known
	bb_put(bound,X),	% save new upper bound
	bb_put(best,AllVars),	% save best solution
	fail.			% explore alternatives
minBB([H|Rest],AllVars,X):-
	indomain(H),		% assign a value
	bb_get(bound,Bound),
	fd_min(X,MinX),
	MinX<Bound,		% check bound
	minBB(Rest,AllVars,X).

% minimization with interval splitting
minimizeBBsplit(Vars,X):-
	(var(X) ->
	    fd_min(X,MinX),fd_max(X,MaxX),
	    Middle is integer((MinX+MaxX)/2),
	    ((X#=<Middle, \+ \+ label(Vars)) ->	
		true
	    ;
		X#>Middle
	    ),!,
	    minimizeBBsplit(Vars,X)
	;
	    label(Vars)
	).

% Bounded Backtrack Search
bbs_search(Variables,Limit):-
	bb_put(limit,Limit),
	bb_put(stage,fw),
	bbs(Variables).
bbs([]).
bbs([X|RestVariables]):-
	(bbs_assign_value(X) ; bb_put(stage,bw),fail),
	bbs(RestVariables).

bbs_assign_value(X):-
	assign_value(X),
	bb_update(stage,Stage,fw),
	(Stage=fw -> true
	;	bb_get(limit,L), NL is L-1, bb_put(limit,NL),
		(NL>0 -> true ; !,fail)
	).

% Depth Bounded Search
dbs_search([],_).
dbs_search([X|RestVariables],Depth):-
	(Depth>0 ->
		NewDepth is Depth-1,
		assign_value(X)
	;
		NewDepth = 0,
		once(assign_value(X))
	),
	dbs_search(RestVariables,NewDepth).

% Iterative Broadening
ib_search(Variables,Width):-
	bb_put(width,Width),
	ib(Variables,Width).
	
ib([],_).
ib([X|RestVariables],Width):-
	bb_update(width,TW,Width),
	(ib_assign_value(X) ; bb_put(width,TW),!,fail),
	ib(RestVariables,Width).

ib_assign_value(X):-
	assign_value(X),
	bb_get(width,RestWidth),
	(RestWidth=0 -> !,fail
	;	NewW is RestWidth-1, bb_put(width,NewW)
	).

assign_value(X):-
	indomain(X).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% FOR EVALUATING
queens(N,Queens):-
	length(Queens,N),
	domain(Queens,1,N),
	all_different(Queens),
	constraint_all(Queens),
%	enum(Queens).
%	step(Queens).
%	bisection(Queens).
	label(Queens).
%	bbs_search(Queens,100000).
%	dbs_search(Queens,3).
%	ib_search(Queens,3).
%	Queens=[Q1,Q2|_],Pos #= Q1+Q2, minimizeSimple(Queens,Pos).
%	Queens=[Q1,Q2|_],Pos #= Q1+Q2, minimizeBB(Queens,Pos,100).
%	Queens=[Q1,Q2|_],Pos #= Q1+Q2, minimizeBBsplit(Queens,Pos).

constraint_all([]).
constraint_all([Q|Qs]):-
	constraint_queens(Qs,Q,1),
	constraint_all(Qs).

constraint_queens([],_,_).
constraint_queens([Q2|Qs],Q1,I):-
	Q1#\=Q2+I, Q1#\=Q2-I,
	I1 is I+1,
	constraint_queens(Qs,Q1,I1).
