From: Karen Petrie <scomkep_at_zeus.hud.ac.uk>

Date: Wed 30 Apr 2003 06:51:16 PM GMT

Message-Id: <200304301851.h3UIpGF02674@dvorak.hud.ac.uk>

Date: Wed 30 Apr 2003 06:51:16 PM GMT

Message-Id: <200304301851.h3UIpGF02674@dvorak.hud.ac.uk>

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).Received on Wed Apr 30 20:02:24 2003

*
This archive was generated by hypermail 2.1.8
: Wed 16 Nov 2005 06:07:23 PM GMT GMT
*