Reputation: 42977
I am studying Prolog on Ivan Bratko book: Programming for Artificial Intelligence and on the book I have found this version of 8 Queens problem that use a space state "graph" to solve the problem:
s(Queens, [Queen|Queens]) :- member(Queen, [1,2,3,4,5,6,7,8]),
noattack(Queen, Queens).
goal([_,_,_,_,_,_,_,_]).
noattack(_,[],_).
noattack(Y,[Y1|Ylist],Xdist) :-
Y1-Y =\= Xdist,
Y-Y1 =\= Xdist,
Dist1 is Xdist + 1,
noattack(Y,Ylist,Dist1).
solve(N,[N]) :- goal(N).
solve(N, [N|Sol1]) :- s(N,N1),
solve(N1,Sol1).
It combines the 8 Queens problem solution based on permutation (use its noattack/3 relation) and the s/2 predicate that I think that build the possible successor states state (the nodes of my graph). So I have something like:
s(ActualState, SuccessorState)
The goal/1 predicate I think that only specify that I have to place exactly 8 queens.
On the book say me that executing this query: solve([],Solution) it will produce a list of board positions with increasing number of queens and that this list will end with a safe configuration of the eight queens.
But if I try to execute this query don't work and I will obtain this output:
?- solve([],Solution).
ERROR: s/2: Undefined procedure: noattack/2
ERROR: However, there are definitions for:
ERROR: noattack/3
Because,rightly, the noattack predicate called in the line 2 take only 2 parameters but the noattack predicate must have 3 parameters...bue on the book is given in this wrong way and I don't know how solve this problem...
Why? What am I missing?
Upvotes: 2
Views: 1686
Reputation: 71099
few bugs:
s(Queens, [Queen|Queens]) :- member(Queen, [1,2,3,4,5,6,7,8]),
noattack(Queen, Queens, 1).
noattack(_,[],_) :- !.
noattack(Y,[Y1|Ylist],Xdist) :- Y =\= Y1,
Y1-Y =\= Xdist,
Y-Y1 =\= Xdist,
Dist1 is Xdist + 1,
noattack(Y,Ylist,Dist1).
Then,
18 ?- solve([],_X), last(_X,S).
S = [4, 2, 7, 3, 6, 8, 5, 1] ;
S = [5, 2, 4, 7, 3, 8, 6, 1] ;
S = [3, 5, 2, 8, 6, 4, 7, 1] ;
S = [3, 6, 4, 2, 8, 5, 7, 1] ;
S = [5, 7, 1, 3, 8, 6, 4, 2] ;
S = [4, 6, 8, 3, 1, 7, 5, 2]
and,
25 ?- findall( X, solve([],X), _S), length(_S,N).
N = 92.
Upvotes: 3