Declaratieve Talen/Oplossing N-queens

een oplossing

% beginmethode: Opl zal van de vorm [1,2,3,4,5,6,..] zijn

nqueens(N, Opl) :-
    nqueens(N, 1, [], Opl).

% C is current kolum, Accum van vorm [(1,x), (2,y), ..]

 nqueens(N, C, Accum, Opl) :-
    (
      check_row_constraint(Accum) -> 
        fail
    ;
      check_diagonal_constraint(N, Accum) ->
        fail
    ;
      C > N ->
        findall(B, member((_,B), Accum), Opl)
    ;
      get_next_choice(N, C, Choice),
      C1 is C + 1,
      nqueens(N, C1, [Choice|Accum], Opl)    
    ).

% constraintchecking    

check_row_constraint(Accum) :-
    member((A, B), Accum), 
    member((C, D), Accum), 
    A \== C, 
    B == D, !.

% diagonaal rechts naar boven check

check_diagonal_constraint(N, Accum) :-
    member((A, B), Accum),
    between(1, N, D),
    D \== 0,
    F is A + D,
    G is B + D,
    member((F, G), Accum).

% diagonaal links naar boven check

check_diagonal_constraint(N, Accum) :-
    member((A, B), Accum),
    between(1, N, D),
    D \== 0,
    F is A - D,
    G is B + D,
    member((F, G), Accum).

% volgende keuze            

get_next_choice(N, C, Choice) :-
    between(1, N, A), 
    Choice = (C, A).

een andere 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)

nog een andere oplossing

nqueens(N, Oplossing) :-
   findall(A,between(1,N,A),List),
   permutation(List, Oplossing),
   \+queen_hits_queen_on_diagonal(Oplossing).

queen_hits_queen_on_diagonal(Oplossing) :-
   member(Queen1,Oplossing),
   member(Queen2,Oplossing),
   Queen1 \== Queen2,
   nth1(Col1,Oplossing,Queen1),
   nth1(Col2,Oplossing,Queen2),
   ColDiff is abs(Col1 - Col2),
   RowDiff is abs(Queen1 - Queen2),
   ColDiff == RowDiff.

permutation? nth1?--Beau 18 jun 2006 17:55 (CEST)