Is there a problem of library sbds ?

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>
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.com 
Received 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