jm@sics.se (Johan Montelius) (08/03/90)
This is yet another n-queens solver. It illustrates the concept of
using logical variables as communication channels. In this case they
are simple flags but the concept has general usage for any information
that need to be spread out immediately to different parts of a program.
Really there is nothing special about this, logical variables work
this way all the time ;-) but this example could maybe be of some
interest to novice prolog users.
There is no attempt to reduce the combinatorial work in the queens
problem, this is just a fast way to do the work.
A 4*4 board is created like:
[[p(C1, _,Y1),p(C2,X2,Y2),p(C3,X3,Y3),p(C4,X4, _)],
[p(C1,X2,Y4),p(C2,X3,Y1),p(C3,X4,Y2),p(C4,X5,Y3)],
[p(C1,X3,Y5),p(C2,X4,Y4),p(C3,X5,Y1),p(C4,X6,Y2)],
[p(C1,X4, _),p(C2,X5,Y5),p(C3,X6,Y4),p(C4, _,Y1)]]
All positions in the same column or diagonal share a variable.
When queen n is placed at a position the structure p(C,X,Y) is
instantiated to p(n,n,n). Queen n+1 can then not be placed at
any position on the same column or diagonal as queen n, since
p(n+1,n+1,n+1) will not unify with p(n,_,_), p(_,n,_) or p(_,_n).
Johan Montelius
jm@sics.se
Kent Boortz
boortz@sics.se
%%%% Yet another N-Queens program
%%%% By Johan Montelius and Kent Boortz
%%%%
%%%% :- queens(+Number of Queens, -The table).
%%%% :- timeall(queens(8, _)) => 0.2 s (SICStus with spark native code)
queens(N,All):- board(N,N,All),place(All,1).
board(1,_,[_]).
board(M,N,[Next,Last|Rest]):-
M =\= 1,
M1 is M - 1,
next(N,Last,Next),
board(M1,N,[Last|Rest]).
next(1,[_],[_]).
next(N,[p(A2,B2,_),p(A1,B1,C2)|Rest],[p(A2,_,C2),p(A1,B2,C3)|Next]):-
N =\= 1,
N1 is N - 1,
next(N1,[p(A1,B1,C2)|Rest],[p(A1,B2,C3)|Next]).
place([],_).
place([Row|Rest],N):-
row(Row,N),
N1 is N + 1,
place(Rest,N1).
row([p(N,N,N)|_],N).
row([_|Row],N) :- row(Row,N).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
display_queens(N) :- queens(N,All),displ(All).
displ([First|_]):- displr(First).
displr([]).
displr([p(C,_,_)|Rest]):- write(C),write(' '),displr(Rest).
time(Goal):-
statistics(runtime,_),
call(Goal),
statistics(runtime,[_,T]),
Sec is T / 1000,
nl,write(Sec),write(' sec.'),nl.
timeall(Goal):- time(all(Goal)).
all(Goal):- call(Goal),fail.
all(_).
--
Johan Montelius
SICS, PO Box 1263, S-164 28 Kista, Sweden.
Phone: +46 8 752 15 68 Telefax: +46 8 751 72 30 Internet: jm@sics.se