From: Ma Long <qrma_at_yahoo.com>

Date: Fri 29 Apr 2005 06:06:01 AM GMT

Message-ID: <20050429060601.59594.qmail@web41002.mail.yahoo.com>

Date: Fri 29 Apr 2005 06:06:01 AM GMT

Message-ID: <20050429060601.59594.qmail@web41002.mail.yahoo.com>

Hi, I am working on the coexisting queens problem, the problem descriptions can be found in http://www.bigfoot.com/~velucchi/queens.zip. I do some testing with library sbds by fixed some position of queens for N=9, such as, Board[1,1] #= 1, Board[1,N] #= 1, Board[N,1] #= 1, Board[N,N] #= 1. Board[1,3] #= 1, Board[3,3] #= 1, Board[3,1] #= 1, Board[3,N] #= 1. Board[N,3] #= 1. it is a solution from velucchi, the program returns the answer is 18 no doubt, then I remove 1 line, Board[1,1] #= 1, Board[1,N] #= 1, Board[N,1] #= 1, Board[N,N] #= 1. Board[1,3] #= 1, Board[3,3] #= 1, Board[3,1] #= 1, %Board[3,N] #= 1. Board[N,3] #= 1. the program try 34 solutions and returns the answer is 14 ?! I try to print out each solution of the library sbds generated, it seems library sbds only search the non-fixed position and ignore all the fixed position. for the above example, there are 9 positions in 1 solution but 8 positions fixed, then sbds only try 1 position in 9*9 board and applied symmetry breaking for that 1 position only. such as Board[3,9] and Board[9,3] is symmetry position for single position, but it may not be symmetry in 9-positions list; so that library sbds missed some solutions in this case. May I conclude for library sbds usage, the variable matrix generated by symmetry breaking should be not prefixed by some constraints, otherwise some possible solutions will be missed in symmetry breaking search. the following is my program : :- lib(ic). :- lib(ic_global). :- lib(ic_sbds). :- lib(branch_and_bound). /* Main function */ fq(N,Timeout) :- model(N, Board), constraints(N, Board), find_queen_post(Board,N,Timeout). /* Main function with heuristic constraints */ fqh(N,Timeout) :- model(N, Board), constraints(N, Board), % apply heuristic constraints constraints_heuristic(N, Board), find_queen_post(Board,N,Timeout). /* Model of N*N board */ model(N, Board):- dim(Board, [N, N]), Board[1..N, 1..N] :: 0..1. /* Common constraints: N queens must be put on N*N board */ constraints(N, Board):- flatten_matrix(Board,BoardList), occurrences(1,BoardList,N). /* Heuristic constraints: */ constraints_heuristic(N,Board) :- Board[1,1] #= 1, Board[1,N] #= 1, Board[N,1] #= 1, Board[N,N] #= 1, Board[1,3] #= 1, Board[3,3] #= 1, Board[3,1] #= 1, %Board[3,N] #= 1, Board[N,3] #= 1. /* Search function with Symmetry Breaking function */ find_queen_post(Board,N,T) :- Upper is N*N, Syms = [ r90(Board, N), r180(Board, N), r270(Board, N), rx(Board, N), ry(Board, N), rd1(Board, N), rd2(Board, N) ], sbds_initialise(Board, 2, Syms, #=, []), Cost #= N*N - Ua, %setval(count,0), bb_min(( sbds_labeling(Board), %incval(count), %getval(count,S), %(mod(S,1000,0) -> writeln(S);true), count_unattack(Board,Board2,N,Ua) ), Cost, bb_options{from:N,to:Upper, timeout:T}), print_board(Board2,N), write("Number of unattacked cells: "),writeln(Ua). /* Count the unattack area of board */ count_unattack(B1,B2,N,Count) :- dim(B2,[N,N]), set_queen(B1,B2), set_attack(N,B1,B2), (for(I,1,N), fromto(0,I1,I2,C1), param(B2,N) do (for(J,1,N), fromto(0,J1,J2,C2), param(B2,I) do subscript(B2,[I,J],T), ((T == 1;T==2) -> J2=J1;J2 is J1+1,B2[I,J] #= 0) ), I2 is I1+C2 ), Count #= C1. /* Set queens on the board */ set_queen(B1,B2) :- (foreacharg(V1s, B1), foreacharg(V2s, B2) do (foreacharg(V1, V1s), foreacharg(V2, V2s) do (V1==1 -> V2 = 1;true) )). /* Set attack area of board for each queen */ set_attack(N,B1,B2) :- (for(I,1,N), param(N,B1,B2) do (for(J,1,N), param(N,B1,B2,I) do subscript(B1,[I,J],T), (T==1-> set_attack_row(B2,N,I), set_attack_col(B2,N,J), set_attack_nwse(B2,N,I,J), set_attack_nesw(B2,N,I,J); true) ) ). /* Set attack row of board */ set_attack_row(Board,N,Row) :- (for(I,1,N), param(Board,Row) do subscript(Board,[Row,I],T), (T==1-> true; Board[Row,I] #= 2)). /* Set attack column of board */ set_attack_col(Board,N,Col) :- (for(I,1,N), param(Board,Col) do subscript(Board,[I,Col],T), (T==1-> true; Board[I,Col] #= 2)). /* Set attack line from northwest to southeast */ set_attack_nwse(Board,N,Row,Col) :- D1 is Row-1, D2 is Col-1, D3 is N-Row, D4 is N-Col, (D1 =< D2 -> A1=1, B1 is Col-D1; A1 is Row-D2, B1=1), (D3 =< D4 -> A2=N, B2 is Col+D3; A2 is Row+D4, B2=N), (for(I,A1,A2), for(J,B1,B2), param(Board) do subscript(Board,[I,J],T), (T==1-> true; Board[I,J] #= 2)). /* Set attack line from northeast to southwest */ set_attack_nesw(Board,N,Row,Col) :- D1 is Row-1, D2 is N-Col, (D1 =< D2 -> A1=1, B1 is Col+D1; A1 is Row-D2, B1=N), A2=B1,B2=A1, (for(I,A1,A2), for(J,B1,B2,-1), param(Board) do subscript(Board,[I,J],T), (T==1-> true; Board[I,J] #= 2)). /* Print out the board nicely */ print_board(Board,N) :- (for(I,1,N), param(Board,N) do (for(J,1,N), param(Board,I) do subscript(Board,[I,J],A), (A==1 -> printf("q ",[]); (A==2 -> printf("a ",[]); printf("v ",[]))) ),printf("%n",[]) ). % The sample code from ECLiPSe documents % http://www.comp.nus.edu.sg/~cs5216/eclipse/doc/bips/lib/ic_sbds/sbds_initialise-5.html 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. rx(Matrix, N, [X,Y], Value, SymVar, SymValue):- SymX is (N + 1 - X), SymY is Y, SymVar is Matrix[SymX, SymY], SymValue is Value. ry(Matrix, N, [X,Y], Value, SymVar, SymValue):- SymX is X, SymY is(N + 1 - Y), SymVar is Matrix[SymX, SymY], SymValue is Value. rd1(Matrix, _, [X,Y], Value, SymVar, SymValue) :- SymX is Y, SymY is X, SymVar is Matrix[SymX, SymY], SymValue is Value. rd2(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. % The sample code from ECLiPSe documents % http://www.comp.nus.edu.sg/~cs5216/eclipse/doc/bips/lib/ic_sbds/sbds_try-2.html sbds_indomain(X) :- nonvar(X). sbds_indomain(X) :- var(X), %mindomain(X, LWB), % lib(fd) get_min(X, LWB), % lib(ic) sbds_try(X, LWB), sbds_indomain(X). sbds_labeling(AllVars) :- (foreacharg(VarsList, AllVars) do (foreacharg(Var, VarsList) do sbds_indomain(Var) )). % 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). __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.comReceived on Fri Apr 29 07:36:05 2005

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