Declaratieve Talen/Oplossing N-queens: verschil tussen versies

Ga naar: navigatie, zoeken
(een andere oplossing)
(Oplossing 5 toegevoegd.)
 
Regel 1: Regel 1:
=== een oplossing ===
+
=== Oplossing 1 ===
  
 
  % beginmethode: Opl zal van de vorm [1,2,3,4,5,6,..] zijn
 
  % beginmethode: Opl zal van de vorm [1,2,3,4,5,6,..] zijn
Regel 58: Regel 58:
 
     Choice = (C, A).
 
     Choice = (C, A).
  
=== een andere oplossing ===
+
=== Oplossing 2 ===
  
 
  check_queens(List) :-
 
  check_queens(List) :-
Regel 120: Regel 120:
 
--[[Gebruiker:Beau|Beau]] 17 jun 2006 21:40 (CEST)
 
--[[Gebruiker:Beau|Beau]] 17 jun 2006 21:40 (CEST)
  
=== nog een andere oplossing ===
+
=== Oplossing 3 ===
  
 
  nqueens(N, Oplossing) :-
 
  nqueens(N, Oplossing) :-
Regel 137: Regel 137:
 
     ColDiff == RowDiff.
 
     ColDiff == RowDiff.
  
=== en weer een andere oplossing ===
+
=== Oplossing 4 ===
 
   
 
   
 
  %list(0,[]):-!.
 
  %list(0,[]):-!.
Regel 175: Regel 175:
 
     Nnext is N-1,
 
     Nnext is N-1,
 
     list2(Nnext,Lnext).
 
     list2(Nnext,Lnext).
 +
 +
=== Oplossing 5 ===
 +
 +
queens(N,S) :-
 +
numlist(1,N,X),
 +
permutation(X,S),
 +
safe(S).
 +
 +
safe([]).
 +
safe([X|Y]) :-
 +
noattack(X,Y,1),
 +
safe(Y).
 +
 +
noattack(_X,[],_D).
 +
noattack(X,[H|T],D) :-
 +
H =\= X + D,
 +
H =\= X - D,
 +
New is D + 1,
 +
noattack(X,T,New).

Huidige versie van 17 aug 2009 om 10:09

Oplossing 1

% 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).

Oplossing 2

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)

Oplossing 3

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.

Oplossing 4

%list(0,[]):-!.
%list(N,[N|R]) :-
%   Nnew is N-1,
%   list(Nnew,R).

nqueens(N,Sol) :-
   %maak een lijst met elke queen op een verschillende rij.
   %positie in lijst geeft kolom weer.
   list2(N,List),!,  %Cut omdat we niet naar list willen  backtracken.
   permutation(List,Perm),
   correct(Perm),
   Sol = Perm.

%ze zitten allemaal in een verschillende kolom en een  verschillende rij.
%controleren op diagonaal.

%elke kolom tov de volgende controleren.
correct([]).
correct([P|Pr]) :-
   correct2(P,Pr,1),
   correct(Pr).

%Kol is de afstand van de te controleren kolom (K) Tov P
%P en K geven weer op welke rij de queen staat.
correct2(_,[],_).
correct2(P,[K|Kr],Kol) :-
   K =\= P - Kol,
   K =\= P + Kol,
   Kol2 is Kol + 1,
   correct2(P,Kr,Kol2).

list2(0,[]).
list2(N,L) :-
   L = [N|Lnext],
   Nnext is N-1,
   list2(Nnext,Lnext).

Oplossing 5

queens(N,S) :-
	numlist(1,N,X),
	permutation(X,S),
	safe(S).

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

noattack(_X,[],_D).
noattack(X,[H|T],D) :-
	H =\= X + D,
	H =\= X - D,
	New is D + 1,
	noattack(X,T,New).