:- lib(ic).

%%%%%%%%%%%%%%%%%%%%%%% Ex 1.3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% StrategyName may be bf for brute force, otherwise the constraint strategy applies
nqueens(N,StrategyName) :-
	(StrategyName == bf ->
		Strategy = nqueensBruteForce(N,Sol)
	;
		Strategy = nqueensConstraints(N,Sol)
	),
	% puts all solutions to our problem in List
	findall(Sol,call(Strategy),List),
	% some output
	showSolutions(List),
	length(List,Length),
	printf("found solutions: %w%n",[Length]).


nqueensConstraints(N,Sol) :-
	init(N,Sol),
	% constrains the variables
	constraints(Sol),
	% finds a valid instantiation
	labeling(Sol).


nqueensBruteForce(N,Sol) :-
	init(N,Sol),
	% tries a possible variable instantiation
	labeling(Sol),
	% dismisses the instantiation if it does not fulfil the constraints
	constraints(Sol).


init(N,Sol) :-
	% instantiates Sol to a list of N variable elements
	length(Sol,N),
	% each element of list Sol can range from 1 to N
	Sol #:: [1..N].


% given a list of variables [X1,...Xn], this predicate puts the N-Queens constraints:
% Xi \= Xj, Xi-Xj \= i-j, Xi-Xj \= j-i (for all Xi and Xj with j >= i)
constraints([]).
constraints([H|T]) :-
	different(H,T,1),
	constraints(T).


% puts constraints Xi \= Xj, Xi-Xj \= i-j, Xi-Xj \= j-i (for fixed X_i and all Xj with j >= i)
different(_,[],_).
different(Xi,[Xj|T],Diff) :-
	Xi #\= Xj,
	Xi-Xj #\= Diff,
	Xi-Xj #\= -Diff,
	Diff1 is Diff+1,
	different(Xi,T,Diff1).


showSolutions([]).
showSolutions([H|T]) :-
	writeln(H),
	showSolutions(T).