135 views

Skip to first unread message

Mar 8, 1991, 10:30:52 AM3/8/91

to

/*

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.

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-nqueens

Mar 11, 1991, 5:00:22 AM3/11/91

to

What do the figures in the program correspond to, for example:

% Production version with arithmetic increment 1.55 7.20 34.0 180.8

Thanks

Mike

br...@cs.tcd.ie

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu