/*-------------------------------------------------------------------------*/
/* Benchmark (Finite Domain)                                               */
/*                                                                         */
/* Name           : queens.pl                                              */
/* Title          : N-queens problem                                       */
/* Original Source: P. Van Hentenryck's book                               */
/* Adapted by     : Daniel Diaz for GNU Prolog                             */
/* 		    Guillaume Arnaud for SBDS                              */
/* Date           : June 2003                                              */
/*                                                                         */
/* Put N queens on an NxN chessboard so that there is no couple of queens  */
/* threatening each other.                                                 */
/*                                                                         */
/* Solution:                                                               */
/* N=4  [2,4,1,3]                                                          */
/* N=8  [1,5,8,6,3,7,2,4]                                                  */
/* N=16 [1,3,5,2,13,9,14,12,15,6,16,7,4,11,8,10]                           */
/*-------------------------------------------------------------------------*/

queen(L,N):-
	fd_set_vector_max(N),
	length(L,N),
	fd_domain(L,1,N),
	safe(L),
	lab(normal,L).

queen_sbds(L,N):-
	fd_set_vector_max(N),
	length(L,N),
	fd_domain(L,1,N),
	safe(L),
	create_sym1(S,N),
	fd_labeling_sbds(L,S,[variable_method(middle),value_method(middle)]).

%%%%%%%%%%%%%%%%%%%
% Main predicates %
%%%%%%%%%%%%%%%%%%%

safe([]).
safe([X|L]):-
	noattack(L,X,1),
	safe(L).

noattack([],_,_).
/*
% faster than the original PVH's version 

noattack([Y|L],X,I):-
	I1 is I+1,
	noattack(L,X,I1),
	diff(X,Y,I).
*/
noattack([Y|L],X,I):-
	diff(X,Y,I),
	I1 is I+1,
	noattack(L,X,I1).


/*
diff(X,Y,I):-
	fd_tell(diff(X,Y,I)).
*/

diff(X,Y,I):-
	X#\=Y,
	X#\=Y+I,
	X+I#\=Y.


lab(normal,L):-  
	fd_labeling(L).

lab(ff,L):-
	fd_labelingff(L).

%%%%%%%%%%%%%%%%%%%%%%%%
% Symmetry definitions %
%%%%%%%%%%%%%%%%%%%%%%%%


% Representation: 	point (couple of variable/value)
%			point= (ivar-1)*(N+1)+value
% Group 	:	none.
create_sym1(S,N):- 
	Np1 is N+1,NNp1 is N*Np1,	
	length(LHor,NNp1),
	length(LVert,NNp1),
	length(LDiag1,NNp1),
	length(LDiag2,NNp1),
	length(LRot180,NNp1),
	length(LRot90,NNp1),
	length(LRot270,NNp1),
	
	diag1(Np1,N,LDiag1,1,NNp1),
	diag2(Np1,N,LDiag2,1,NNp1),
	rot180(Np1,N,LRot180,1,NNp1),
	rot90(Np1,N,LRot90,1,NNp1),
	rot270(Np1,N,LRot270,1,NNp1),
	hor(Np1,N,LHor,1,NNp1),
	vert(Np1,N,LVert,1,NNp1),
	
	S=[sym(point,LHor),sym(point,LVert),sym(point,LDiag1),sym(point,LDiag2),sym(point,LRot180),sym(point,LRot90),sym(point,LRot270)].

% Representation: 	point (couple of variable/value)
%			point= (ivar-1)*(N+1)+value
% Group 	: 	two generators (horizontal and 90° rotation symmetries)
%			generates all symmetries of the problem (7 without identity).
create_sym2(S,N):- 
	Np1 is N+1,NNp1 is N*Np1,
	
	length(LHor,NNp1),
	length(LRot90,NNp1),
	rot90(Np1,N,LRot90,1,NNp1),
	hor(Np1,N,LHor,1,NNp1),
	S=[group([sym(point,LHor),sym(point,LRot90)])].
	
% Representation: 	varval (sym/3)
% Group 	: 	two generators (horizontal and vertical symmetries)
%			generates three symmetries of the problem (the two generators
%			plus 180° rotation).
create_sym3(S,N):- 
	liste_num(IVar,1,N),
	liste_num(Val,1,N),
	reverse(Val,ValSym),
	reverse(IVar,IVarSym),
	S=[group([sym(varval,IVar,[0|ValSym]),sym(varval,IVarSym,[0|Val])])].

	list_display(s[6],perm_size);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Building of permutation lists for point representation
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

hor(_,_,_,X,End):-X>End,!.
hor(M,N,L,X,End) :-
	I is (X-1)//M+1,
	J is (X-1) mod M,
	(J=0->
		nth(X,L,X)
		;
		ISym is N+1-I,
		XSym is (ISym-1)*M+J+1,
		nth(X,L,XSym)),
	Xp1 is X+1,
	hor(M,N,L,Xp1,End).

vert(_,_,_,X,End):-X>End,!.
vert(M,N,L,X,End) :- 
	I is (X-1)//M+1,
	J is (X-1) mod M,
	(J=0->
		nth(X,L,X)
		;
		JSym is N+1-J,
		XSym is (I-1)*M+JSym+1,
		nth(X,L,XSym)),
	Xp1 is X+1,
	vert(M,N,L,Xp1,End).

diag1(_,_,_,X,End):-X>End,!.
diag1(M,N,L,X,End) :- 
	I is (X-1)//M+1,
	J is (X-1) mod M,
	(J=0->
		nth(X,L,X)
		;
		XSym is (J-1)*M+I+1,
		nth(X,L,XSym)),
	Xp1 is X+1,
	diag1(M,N,L,Xp1,End).

diag2(_,_,_,X,End):-X>End,!.
diag2(M,N,L,X,End) :- 
	I is (X-1)//M+1,
	J is (X-1) mod M,
	(J=0->
		nth(X,L,X)
		;
		ISym is N+1-J,
		JSym is N+1-I,
		XSym is (ISym-1)*M+JSym+1,
		nth(X,L,XSym)),
	Xp1 is X+1,
	diag2(M,N,L,Xp1,End).
	
rot180(_,_,_,X,End):-X>End,!.
rot180(M,N,L,X,End) :- 
	I is (X-1)//M+1,
	J is (X-1) mod M,
	(J=0->
		nth(X,L,X)
		;
		ISym is N+1-I,
		JSym is N+1-J,
		XSym is (ISym-1)*M+JSym+1,
		nth(X,L,XSym)),
	Xp1 is X+1,
	rot180(M,N,L,Xp1,End).

rot90(_,_,_,X,End):-X>End,!.
rot90(M,N,L,X,End) :- 
	I is (X-1)//M+1,
	J is (X-1) mod M,
	(J=0->
		nth(X,L,X)
		;
		ISym is J,
		JSym is N+1-I,
		XSym is (ISym-1)*M+JSym+1,
		nth(X,L,XSym)),
	Xp1 is X+1,
	rot90(M,N,L,Xp1,End).
	
rot270(_,_,_,X,End):-X>End,!.
rot270(M,N,L,X,End) :- 
	I is (X-1)//M+1,
	J is (X-1) mod M,
	(J=0->
		nth(X,L,X)
		;
		ISym is N+1-J,
		JSym is I,
		XSym is (ISym-1)*M+JSym+1,
		nth(X,L,XSym)),
	Xp1 is X+1,
	rot270(M,N,L,Xp1,End).


