position 8 queens on a board without attack

From: Gregor Rot (zara4tustra_at_yahoo.com)
Date: 04/09/04 

Date: Fri, 09 Apr 2004 15:53:53 +0200

Hi everybody,

i have this program that possitions 8 queens (chess game) on the board
in a way that there is no attacking involved.

All the possible combinations are: 8^8 (8 possible Y possitions for the
first queen, 8 for the second, ...).

I would like to figure out, how many combinations Prolog tryes out actually.

Here is the program:
------------------

:- dynamic iter/1
% set the template, each queen on it's own X coordinate, 1,2,3,...8
template([1/Y1,2/Y2,3/Y3,4/Y4,5/Y5,6/Y6,7/Y7,8/Y8]).
% iter facts serve as counter
iter(1).

solution([]).

solution([X/Y|Others]):-
   solution(Others),
   member(Y,[1,2,3,4,5,6,7,8]),
   noattack(X/Y,Others).

noattack(X/Y,[]).
noattack(X/Y,[X1/Y1|Others]):-
   Y=\=Y1,
   X-X1=\=Y-Y1,
   X-X1=\=Y1-Y,
   noattack(X/Y,Others).

conc([],L,L).
conc([X|Rest],L2,[X|L3]):-
   conc(Rest,L2,L3).

member(X,L):-
   iteration,
   conc(L1,[X|L2],L).

iteration:-
   iter(Last),
   retract(iter(Last)),
   Next is Last+1,
   asserta(iter(Last)).

--------
There are 92 solutions for this problem, and by:

?- template(Pos),solution(Pos).

Prolog starts returning them in variable Pos.

Now, the iteration predicate should add a iter(value) fact each time
member is computed = each time a combination is tryed out.

Now, if you stop the program after the first response for Pos, that is:

Pos = [1/4,2/2,3/7,4/3,5/6,6/8,7/5,8/1] ? ENTER

and then you ask:

iter(A).

you get:

A=114

But now, if you change the code and the place of the predicate iteration
and put it in the solution predicate (and remove it from the member
predicate of course), thus the code now looking like:

solution([X/Y|Others]):-
   solution(Others),
   member(Y,[1,2,3,4,5,6,7,8]),
   iteration,
   noattack(X/Y,Others).

member(X,L):-
   conc(L1,[X|L2],L).

and after this modifications you repeat the measurement (first deleting
all facts about iter), you get that:
?-iter(A).

A=877

//////

The results mean that predicate member was "computed" 114 times to get
the first solution to the problem, and at the same time solution was
kind of? computed 877 times, Prolog returning to get other possibilities
for member etc...., i sort of get the idea of the difference, i just
want to know witch answer is right? (to the question of how many
different combinations for the placement of the queens Prolog tryed out
before returning the first solution).

Can somebody see the point here and write it out shortly?

Thanks a lot,
Greg

Relevant Pages

  • Re: How to improve this 8 queens?
    ... of 8 queens, and I wanted to do more of it. ... generate the test/8 predicate, if possible, with a short 1 or 2 line ... headaches in Prolog. ... his if I had easy access to an array type, but no tutorial or FAQ I've ...
    (comp.lang.prolog)
  • Re: Where is JerryD
    ... >posting from Queens University Kingston (that was listed as the ... Member - Liberal International ... God Queen and country! ...
    (rec.arts.drwho)