Re: Counting backtracks

Hi Farouk,

You wrote:
>I would like to count the number of backtracks done between successive 
>solutions until the 'last'. I would also like to know the number of 
>backtracks done between finding the optimum value and proving optimality. 
>Is there anyway I can do this in ECLiPSe?
>

Yes, there is a way to do it fairly easily if you are using the FD 
minimize predicate, as it rases the event handler 280 every time it 
outputs the optimal found to date. So all you need to do is set this even 
handler to also include a backtrack count. In my case I have only ever had 
it print out the value, but it should be fairly easy to output it to a 
file, if that was required.

Firstly, you need to write your own backtracking methods (this one 
actually comes from an example which Joachim Schimpf wrote, so all the 
credit goes to him):

:- local variable(backtracks), variable(deep_fail).

init_backtracks :-
        setval(backtracks,0).

get_backtracks(B) :-
        getval(backtracks,B).
        
count_backtracks :-
        setval(deep_fail,false).
count_backtracks :-
        getval(deep_fail,false),        % may fail
        setval(deep_fail,true),
        incval(backtracks),
        fail.
        
Then a search predicate which updates this count:

mylabeling(AllVars) :-
        ( foreach(Var, AllVars) do
            count_backtracks,
            indomain(Var)                       % select value
        ).
        
Then you need to redefine the event handler:

write_info(_Error, Predicate):-
	arg(1, Predicate, Minimum),
	printf("Found a solution with cost %d \n", [Minimum]),
	get_backtracks(B),
	printf("Backtracks to this point = %d \n \n", [B]).

%set event handler	
:- set_event_handler(280, write_info/2).	

Then all you do is call minimize on your labelling:

minimize(mylabeling(SearchVars), OptimalNumber)

I have attached an full example using 'The Peaceably Coexisting Armies of 
Queens' problem. Feel free to use any of the code, but I would appreciate 
an acknowledgment, if you use it in any public way.

One question I have though, is that I can not find an equivalent of the 
minimize predicate in the IC library, is it possible to do this with IC?

Karen

%'Peaceably Coexisting Armies of Queens'
%What is the maximum number of Queens in two equal sized
%armies (black and white), that can be placed on an n by n chess 
%board so that no two queens from opposing armies can attack each other?
%Karen E. Petrie, University of Huddersfield, 30th April 2003

:- lib(fd).
:- lib(fd_global).

%board is of dimensons n*n
%this is represented by a matrix where rows are 
%indexed by i, and columns by j
%optimum(N) is the control predicate
%N is the dimenson of the board
optimium(N):-
	model(N, Board, NWhites, NBlacks),
	constrain(N, Board, NWhites, NBlacks),
	flatten_matrix(Board, FlattenedBoard),
	NegWhites #= -NWhites,
	init_backtracks,
	minimize(mylabeling(FlattenedBoard), NegWhites),
	get_backtracks(B),
	printf("Total Backtracks= %d \n", [B]),
	prettyprint_matrix(Board).
	
%set up the model	
model(N, Board, NWhites, NBlacks):-
	dim(Board, [N, N]),
	Board[1..N, 1..N] :: 0..2,
	flatten_matrix(Board, FlattenedBoard),
	occurrences(1, FlattenedBoard, NWhites),
	occurrences(2, FlattenedBoard, NBlacks).
	
%set up the row constraints	
constrain(N, Board, NWhites, NBlacks):-
	row(Board,N),
	column(Board,N),
	diagonal(Board,N),
	NWhites #= NBlacks.
	

%row constraints
row(Board, N):-
	(for(I, 1, N), 
	 param(N,Board) do
		(for(J, 1, N), 
		 param(I,N,Board) do
			(for(M, I+1, N),
		  	 param(I,J,N,Board) do
				(
				((Board[I,J] #= 1) #=> (Board[M,J] #\= 2)),
				((Board[I,J] #= 2) #=> (Board[M,J] #\= 1))
				)
			)
		)
	).

%column constraints
column(Board, N):-
	(for(J, 1, N), 
	 param(N,Board) do
		(for(I, 1, N), 
		 param(J,N,Board) do
			(for(M, J+1, N),
		  	 param(I,J,N,Board) do
				(
				((Board[I,J] #= 1) #=> (Board[I,M] #\= 2)),
				((Board[I,J] #= 2) #=> (Board[I,M] #\= 1))
				)
			)
		)
	).

%diagonal constraints	
diagonal(Board, N):-
	(for(I, 1, N), 
	 param(N,Board) do
		(for(J, 1, N), 
		 param(I,N,Board) do
			(for(K, 1, N),
		  	 param(I,J,N,Board) do
		  	 	(for(L, 1, N),
 		  	 	param(I,J,K,N,Board) do
					(
					 IminusK is I-K,
		  	 	 	 JminusL is J-L,
		  	 	 	 KminusI is K-I,
		  	 	 	 %printf("variables i-k= %d, j-l= %d, k-i= %d \n",[IminusK,JminusL,KminusI]),
		  	 	 	 (((K>I);(L>J)),((IminusK=JminusL);(KminusI=JminusL)))->
		  	 	 	  (((Board[I,J] #= 1) #=> (Board[K,L] #\= 2)),
					  ((Board[I,J] #= 2) #=> (Board[K,L] #\= 1)));
		  	 	 	true
					 )
				)
			)
		)
	).
		
% Flatten a matrix into a list of its elements.
flatten_matrix(M, List) :-
	flatten_matrix(M, List, []).

flatten_matrix(M, List, Tail) :-
	compound(M),
	!,
	M =.. [_ | Elems],
	(
	    foreach(Elem, Elems),
	    fromto(List, List1, Tail1, Tail)
	do
	    flatten_matrix(Elem, List1, Tail1)
	).
flatten_matrix(X, [X | Tail], Tail).

%mylabelling predicate (which counts backtracks
%Allvars is a list of search variables
mylabeling(AllVars) :-
        ( foreach(Var, AllVars) do
            count_backtracks,
            indomain(Var)                       % select value
        ).

%write a matrix as a set of args
prettyprint_matrix(M) :-
	foreacharg(X, M) do
		writeln(X).	
		

%count backtracks		
:- local variable(backtracks), variable(deep_fail).

init_backtracks :-
        setval(backtracks,0).

get_backtracks(B) :-
        getval(backtracks,B).
        
count_backtracks :-
        setval(deep_fail,false).
count_backtracks :-
        getval(deep_fail,false),        % may fail
        setval(deep_fail,true),
        incval(backtracks),
        fail.

%redefine error handler to give backtracks
write_info(_Error, Predicate):-
	arg(1, Predicate, Minimum),
	printf("Found a solution with cost %d \n", [Minimum]),
	get_backtracks(B),
	printf("Backtracks to this point = %d \n \n", [B]).

%set event handler	
:- set_event_handler(280, write_info/2).