Declaratieve Talen/Oplossing N-queens

een oplossing

check_queens(List) :-
	check_doubles(List),
	check_queens(List,1).
	
check_queens(List,N) :-
	length(List,Length),
	N==Length;
	element_at(List,N,Position),
	check_queen(List,N,Position),
	NN is N+1,
	check_queens(List,NN).
	
check_doubles(List) :-
	list_to_set(List,Set),
	List == Set.

%kijkt de diagonalen na _boven_ de queen op rij N, Position is de plaats van de queen op rij N.
%indien de diagonalen naar onder een andere queen zouden kruisen faalt de test bij die queen.
%bijgevolg is dit een voldoende voorwaarde.
check_queen(_,1,_) :- !.
check_queen([L|Rest],N,Position) :-
	V1 is Position-N+1,
	V2 is Position+N-1,
	L \= V1,
	L \= V2,
	NN is N-1,
	check_queen(Rest,NN,Position).

element_at([L|Rest],N,Result) :-
	(N == 1 -> Result = L;
	NN is N-1,
	element_at(Rest,NN,Result)).

%uit de vb oef... 
queens(N,Qs) :- 
	range(1,N,Rs), 
	permu(Rs,Qs), 
	check_queens(Qs).


% range(A,B,L) :- L is the list of numbers A..B
range(A,A,[A]).
range(A,B,[A|L]) :- 
	A < B,
	A1 is A+1, 
	range(A1,B,L).
	
% permu(Xs,Zs) :- the list Zs is a permutation of the list Xs
permu([],[]).
permu(Qs,[Y|Ys]) :- 
	del(Y,Qs,Rs),
	permu(Rs,Ys).

del(X,[X|Xs],Xs).
del(X,[Y|Ys],[Y|Zs]) :- 
	del(X,Ys,Zs).

--Beau 17 jun 2006 21:40 (CEST)