Question

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?

Was it helpful?

Solution

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.
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top