thom@ecrc.de (Thom Fruehwirth) (03/08/91)
/*
This introduces an n-queens program that is simpler, smaller and an order
of magnitude faster (for n>=8) than optimized standard version as described
in the book Art of Prolog.
The idea for the algorithm and so its complexity is the same.
However instead of encoding the problem of finding attacking queens
with arithmetic operations, the power of unification and the logical
variable is exploited. This shows once more that "elegance is not optional"
(as Richard O'Keefe likes to put it).
Oberving that no two queens can be positioned on the same row, column
or diagonals, we place only one queen on each row. Hence we can identify
the queen by its row-number. Now imagine that the chess-board is divided
into three layers, one that deals with attacks on columns and two for the
diagonals going up and down respectively. We indicate that a field is
attacked by a queen by putting the number of the queen there.
Now we solve the problem by looking at one row at a time, placing one queen
on the column and the two diagonal-layers. For the next row/queen we use
the same column layer, to get the new up-diagonals we have to move the
layer one field up, for the down-diagonals we move the layer one field down.
There are four versions of the n-queens problem.
- The pure version uses natural numbers, so it is pure Prolog. Hence
it can also run backwards or without any input at all! And it is still
much faster than the standard version.
- The production version uses integers instead, so arithmetic is needed
to compute the successor. Its faster than the pure version, because the
storage requirements are less. However, you cannot run it backwards.
- The fun version is a more constraint variant of the original problem.
It assumes that the queens can move (and attack) by beeing reflected
on the top and bottom edges of the chess-board like a pin-ball.
This behaviour is accomplished by just a slight code change.
Optimizing the program: It significantly improved the speed of the program
*not* to use tail-end recursion in the predicate place_queens/4. It is a
common misconception that tail-end recursion always improves efficiency.
It only helps if the predicate is deterministic.
Adding cuts instead of the tests N>0 and I>0 showed less than 1/10 %
improvement, the same with restricting the board size to be greater than
zero and/or doing some unfolding. Joining the generation of the list with
the placing predicate made the program slower by about the same percentage.
*/
/* n-queens problem Thom Fruehwirth 1988 modified 910308 */
% -------- Meaning of Variables ------
% N, M ... Size of the board
% I, J ... Number of the row current queen is on
% Qs, L ... List of length N used to represent the solution
% Cs ... Column as a list of fields of length N
% Us ... Up-Diagonal as an open list of fields
% Ds ... Down-Diagonal as an open list of fields
% place_queen(Queen,Column,Updiagonal,Downdiagonal) places a single queen
% Its the same for all versions
place_queen(I,[I|_],[I|_],[I|_]).
place_queen(I,[_|Cs],[_|Us],[_|Ds]):-
place_queen(I,Cs,Us,Ds).
% Pure version with successor function 1.92
queensp(N,Qs):- gen_listp(N,Qs), place_queensp(N,Qs,_,_).
gen_listp(0,[]).
gen_listp(s(N),[_|L]):-
gen_listp(N,L).
place_queensp(0,_,_,_).
place_queensp(s(I),Cs,Us,[_|Ds]):-
place_queensp(I,Cs,[_|Us],Ds),
place_queen(s(I),Cs,Us,Ds).
% Production version with arithmetic increment 1.55 7.20 34.0 180.8
queens(N,Qs):- gen_list(N,Qs), place_queens(N,Qs,_,_).
gen_list(0,[]).
gen_list(N,[_|L]):-
N>0, M is N-1,
gen_list(M,L).
place_queens(0,_,_,_).
place_queens(I,Cs,Us,[_|Ds]):-
I>0, J is I-1,
place_queens(J,Cs,[_|Us],Ds),
place_queen(I,Cs,Us,Ds).
% Fun version with reflecting diagonals
queensf(N,Qs):- gen_list(N,Qs), place_queensf(N,Qs,_,_).
% uses gen_list/2 from production version
place_queensf(0,_,_,_).
place_queensf(I,Cs,Us,[D|Ds]):-
I>0, J is I-1,
place_queensf(J,Cs,[D|Us],Ds), % here's the difference
place_queen(I,Cs,Us,Ds).
% Art-of-Prolog version 17.13 84.75 426.6 2375.7
queensa(N,Qs) :- range(1,N,Ns), queens(Ns,[],Qs).
queens(UnplacedQs,SafeQs,Qs) :-
select(Q,UnplacedQs,UnplacedQs1),
not attack(Q,SafeQs),
queens(UnplacedQs1,[Q|SafeQs],Qs).
queens([],Qs,Qs).
select(X,[X|L],L).
select(Y,[X|L1],[X|L2]) :-
select(Y,L1,L2).
attack(Q,Qs):- attack(Q,1,Qs).
attack(X,N,[Y|Ys]):- X is Y+N ; X is Y-N.
attack(X,N,[Y|Ys]):- N1 is N+1, attack(X,N1,Ys).
range(M,N,[M|Ns]) :- M<N, M1 is M+1, range(M1,N,Ns).
range(N,N,[N]).
% end-of-nqueensbrady@swift.cs.tcd.ie (03/11/91)
What do the figures in the program correspond to, for example: % Production version with arithmetic increment 1.55 7.20 34.0 180.8 Are they benchmarks? Of what on what? Thanks Mike brady@cs.tcd.ie