Dear Lim Yew, Firstly, please accept my appologise for my tardiness in replying to this email, generally I try to apply to anything on the day of receipt, but I have been at a metting for the last few days without network access. The matrix of search variables is an array containing the search variables. If you have never come across arrays in ECLiPSe you may wish to have a look at section 5.3 in the user mannual, and consult dim/2 in the reference mannual. The second parameter in sbds_initalise/5 is the number of dimensons of this matrix. In sbds_initalise/4 this is defaulted to one, infact this is the difference between the two versions. If your search variables are in a list then you might find: Matrix =.. [[]|List] useful, for converting this list to a 1D matrix. I have attached two versions of the famous N-Queens problem, one is a boolen encoding on a 2D matrix representing the board, the other is a list of the more usual row variables. This should exemplify the difference between the two sbds_initalise predicates. Although, some of the constraints in the 2D version are not written in the simplest manner possible, and it is not as well documented as it should be. As you may know, the SBDS library is a fairly recent addition to ECLiPSe, so if you have any advice on how the documentation could be made clearer, than please do let me know and I will see what I can do. I am currently persuing a PhD in CSP symmetry breaking, so I am always intressted to talk to people with simillar intressts. If I can be of any other assistance than please do get intouch. I do warn you though, that unfortunatly I am going on holiday from Saturday for a week, so again there may be a delay in replies. Please accept my appologies for this in advance. Karen >From: Lim Yew Jin <limyewji@comp.nus.edu.sg> >To: eclipse-users <eclipse-users@icparc.ic.ac.uk> >Subject: [eclipse-users] +VarMatrix in sbds_initialise >Date: Wed, 9 Apr 2003 00:52:12 +0800 >MIME-Version: 1.0 >Content-Transfer-Encoding: 7bit >X-Priority: 3 (Normal) >X-MSMail-Priority: Normal >X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1106 >Importance: Normal > >Dear all, > > I am interested in using fd_sbds but I am confused by the variable >VarMatrix in sbds_initialize. The documentation says "VarMatrix is the >matrix of variables, which are searched over to allocate values to." > > What type of matrix is this? Is it a list of lists or a functor? > > Also, is there a working example that uses lib(fd_sbds) available? >The snippets of code sprinkled in the documentation do not really show >how to use lib(fd_sbds). > > Any help appreciated. Thanks. > > > % ECLiPSe SAMPLE CODE for SBDS % % AUTHOR: Karen Petrie, Huddersfield University % % The famous N-queens problem, using finite domains % :- lib(fd). :- lib(fd_global). :- lib(fd_sbds). %The main calling Predicate %Input: N the dimensons of an N by N board all_solutions(N) :- model(N, Board), constrain(N, Board), setval(solutions, 0), %list of symmetry functions Syms = [ r90(Board, N), r180(Board, N), r270(Board, N), x(Board, N), y(Board, N), d1(Board, N), d2(Board, N) ], %where sbds is initalised sbds_initialise(Board, 2, Syms, #=, []), statistics(times, [T0|_]), ( init_backtracks, symlabelingmatrix(Board), getval(solutions, S), Sol is (S + 1), printf("\nSolution %d \n", [Sol]), prettyprint_matrix(Board), incval(solutions), fail ; true ), get_backtracks(B), statistics(times, [T1|_]), T is T1-T0, getval(solutions, S), printf("\nFound %d solutions for %d queens in %w s with %d backtracks%n",[S,N,T,B]). %model is setup %Input: N Number of dimensons of an N by N board %Output: Board, a 2 dimensonal matrix where each variable %represents a square on the board model(N, Board):- dim(Board, [N, N]), Board[1..N, 1..N] :: 0..1. %constraints are setup %Input: N Number of dimensons of an N by N board %Input: Board, a 2 dimensonal matrix where each variable %represents a square on the board constrain(N, Board):- row(Board,N), column(Board,N), diagonal(Board,N), flatten_matrix(Board,BoardList), occurrences(1,BoardList,N). %sets up row constraints for an N by N 2D Board 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] + Board[M,J] #\= 2 ) ) ). %sets up column constraints for an N by N 2D Board 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] + Board[I,M] #\= 2 ) ) ). %sets up diagonal constraints for an N by N 2D Board 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, (((K>I);(L>J)),((IminusK=JminusL);(KminusI=JminusL)))-> (Board[I,J] + Board[K,L] #\= 2) ; true ) ) ) ) ). %symmetry predicates %Input: Matrix of Search variables %Input: N dimenson of board %Input: [X,Y] index in the Matrix of variable which the symmetry is being applied to %Input: Value of above variable %Output: SymVar is the variable symmetric to Var %Output: SymValue is the value symmetric to Value r90(Matrix, N, [X,Y], Value, SymVar, SymValue) :- SymX is Y, SymY is (N + 1 - X), SymVar is Matrix[SymX, SymY], SymValue is Value. r180(Matrix, N, [X,Y], Value, SymVar, SymValue) :- SymX is (N + 1 - X), SymY is (N + 1 - Y), SymVar is Matrix[SymX, SymY], SymValue is Value. r270(Matrix, N, [X,Y], Value, SymVar, SymValue):- SymX is (N + 1 - Y), SymY is X, SymVar is Matrix[SymX, SymY], SymValue is Value. x(Matrix, N, [X,Y], Value, SymVar, SymValue):- SymX is (N + 1 - X), SymY is Y, SymVar is Matrix[SymX, SymY], SymValue is Value. y(Matrix, N, [X,Y], Value, SymVar, SymValue):- SymX is X, SymY is(N + 1 - Y), SymVar is Matrix[SymX, SymY], SymValue is Value. d1(Matrix, _N, [X,Y], Value, SymVar, SymValue) :- SymX is Y, SymY is X, SymVar is Matrix[SymX, SymY], SymValue is Value. d2(Matrix, N, [X,Y], Value, SymVar, SymValue) :- SymX is (N + 1 - Y), SymY is (N+ 1 - X), SymVar is Matrix[SymX, SymY], SymValue is Value. %labelling predicate %Input: AllVars a 2D matrix of search variables symlabelingmatrix(AllVars) :- (foreacharg(VarsList, AllVars) do (foreacharg(Var, VarsList) do count_backtracks, sbds_indomain(Var) ) ). %indomain predicate %Input: Var is the variable to try to assign a variable to sbds_indomain(Var) :- nonvar(Var). sbds_indomain(Var) :- var(Var), mindomain(Var, LWB), sbds_try(Var, LWB), sbds_indomain(Var). %%%%%%%%Auxillary predicates%%%%%%%%% prettyprint_matrix(M) :- foreacharg(X, M) do writeln(X). :- 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. % 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). % ECLiPSe SAMPLE CODE for SBDS % % AUTHOR: Joachim Schimpf, IC-Parc, % Simplified and adapted for SBDS by Karen Petrie, Huddersfield University % % The famous N-queens problem, using finite domains % :- set_flag(gc_interval, 100000000). :- lib(fd). :- lib(fd_sbds). %----------------------------------- % Toplevel code % % all_queens/2 finds all solutions % first_queens/2 finds one solution % Strategy is a,b,c,d or e % N is the size of the board %----------------------------------- all_queens(N) :- % Find all solutions setval(solutions, 0), statistics(times, [T0|_]), ( queens(N, Board), init_backtracks, %symmetry labelling called sbds_labeling(Board), writeln(Board), incval(solutions), fail ; true ), get_backtracks(B), statistics(times, [T1|_]), T is T1-T0, getval(solutions, S), printf("\nFound %d solutions for %d queens in %w s with %d backtracks", [S,N,T,B]). one_queen(N) :- % Find one solutions statistics(times, [T0|_]), queens(N, Board), init_backtracks, sbds_labeling(Board), writeln(Board), get_backtracks(B), statistics(times, [T1|_]), T is T1-T0, printf("\nFound solution for %d queens in %w s with %d backtracks%n", [N,T,B]). %-------------------- % The model %-------------------- queens(N, Board) :- length(Board, N), Board :: 1..N, ( fromto(Board, [Q1|Cols], Cols, []) do ( foreach(Q2, Cols), param(Q1), count(Dist,1,_) do noattack(Q1, Q2, Dist) ) ), Matrix =.. [[] | Board], %list of symmetry functions Syms = [ r90(Matrix, N), r180(Matrix, N), r270(Matrix, N), rx(Matrix, N), ry(Matrix, N), rd1(Matrix, N), rd2(Matrix, N) ], %where sbds is initalised sbds_initialise(Matrix, Syms, #=, []). noattack(Q1,Q2,Dist) :- Q2 #\= Q1, Q2 - Q1 #\= Dist, Q1 - Q2 #\= Dist. % The symmetry predicates. %Input: Matrix of Search variables %Input: N dimenson of board %Input: [X,Y] index in the Matrix of variable which the symmetry is being applied to %Input: Value of above variable %Output: SymVar is the variable symmetric to Var %Output: SymValue is the value symmetric to Value r90(Matrix, N, Index, Value, SymVar, SymValue) :- SymVar is Matrix[Value], SymValue is N + 1 - Index. r180(Matrix, N, Index, Value, SymVar, SymValue) :- SymVar is Matrix[N + 1 - Index], SymValue is N + 1 - Value. r270(Matrix, N, Index, Value, SymVar, SymValue) :- SymVar is Matrix[N + 1 - Value], SymValue is Index. rx(Matrix, N, Index, Value, SymVar, SymValue) :- SymVar is Matrix[N + 1 - Index], SymValue is Value. ry(Matrix, N, Index, Value, SymVar, SymValue) :- SymVar is Matrix[Index], SymValue is N + 1 - Value. rd1(Matrix, _N, Index, Value, SymVar, SymValue) :- SymVar is Matrix[Value], SymValue is Index. rd2(Matrix, N, Index, Value, SymVar, SymValue) :- SymVar is Matrix[N + 1 - Value], SymValue is N + 1 - Index. %----------------------- % The search strategies %----------------------- sbds_labeling(AllVars) :- ( foreach(Var, AllVars) do count_backtracks, sbds_indomain(Var) % select value ). % Replacement for indomain/1 which takes SBDS into account. sbds_indomain(X) :- nonvar(X). sbds_indomain(X) :- var(X), mindomain(X, LWB), sbds_try(X, LWB), sbds_indomain(X). %-------------------- % Utilities %-------------------- search_space(Vars, Size) :- ( foreach(V,Vars), fromto(1,S0,S1,Size) do dvar_domain(V,D), S1 is S0*dom_size(D) ). :- 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.Received on Wed Apr 09 21:46:04 2003
This archive was generated by hypermail 2.1.8 : Wed 16 Nov 2005 06:07:22 PM GMT GMT