Path: utzoo!attcan!uunet!lll-winken!lll-lcc!ames!mailrus!csd4.milw.wisc.edu!uxc!uxc.cso.uiuc.edu!m.cs.uiuc.edu!kale
From: kale@m.cs.uiuc.edu
Newsgroups: comp.lang.prolog
Subject: Queens Again
Message-ID: <5500009@m.cs.uiuc.edu>
Date: 3 Jan 89 23:14:00 GMT
Lines: 67
Nf-ID: #N:m.cs.uiuc.edu:5500009:000:2699
Nf-From: m.cs.uiuc.edu!kale    Jan  3 17:14:00 1989



Here is a simple program for solving the n non-attacking program.
Unlike the usual ones I have seen and written, this program uses an
array of logical variables to keep track of the status of each diagonal.

It does not exploit any symmetries except the reflection-symmetry.
It uses an ADT for a set of logical variables, which is defined
by the two predicates createSet and bind.
This ADT is implemented here simply using a flat term (so is valid upto
the maximum arity allowed on your system. It was 128 on SBProlog).

I ran this with sbprolog and quintus, and it runs much faster than the simple
programs which do not keep track of the diagonals.

No originality claimed here. I remember reading postings by Saraswat
and possibly by H. Stone that may have involved similar algorithms.

This program showed me once more the advantage of programming in Prolog.
It took me 30-40 minutes to write, debug, and execute this.
I wrote the program later in C, and it took me about 4-5 hours.
(Of course, I may be a bad C programmer, am certainly rusty).
It is just the routine details one gets caught up in, in the C program.

Some peculiarities in the program are for compatibility with our
parallel (pure) prolog interpreter.

safe(N, Queens) :-
/* Queens is a set of N co-ordinates for N non attacking queens on a
   NxN board */
	makeList(N,Cols),
	N2 is 2*N+1,
	createSet(N2, Diag1),	/* Creates an "array" of logical variables */
	createSet(N2, Diag2),
	delete(Col,Cols, RCols), Nhalf is (N+1)/2, Col =< Nhalf,
	diag1of(1,Col, N, D1),     bind(Diag1, D1, 1),
	diag2of(1,Col, N, D2),     bind(Diag2, D2, 1),
	ext(2,N,[q(1,Col)], Diag1, Diag2, RCols, Queens).

ext(Row, Max, Selected, Diag1, Diag2, Cols, Selected) :- Row > Max.

ext(Row, Max, Selected, Diag1, Diag2, Cols, Final) :-
	Row =< Max,
	delete(Col, Cols, RCols), 
	diag1of(Row,Col, Max, D1), bind(Diag1, D1, Row),
	diag2of(Row,Col, Max, D2), bind(Diag2, D2, Row),
	N1 is Row+1, 
	ext(N1, Max, [q(Row,Col)|Selected], Diag1, Diag2, RCols, Final).

diag1of(Row, Col, Max, M) :- M is Row+Col-1.
  /* diag1of returns the diagonal number of one passing thru (Row,Col) */
diag2of(Row, Col, Max, M) :- M is Row-Col+Max.
  /* diag2of returns the diagonal number of the counter-diagonal
	 passing thru (Row,Col) */

/* createSet and bind define an ADT for an array of logical variables */
/* This implementation works only for sets of size < 128. */
/* That is enough here. In general, would need a tree.    */

createSet(Size,T) :- Size < 128, functor(T,f,Size).
bind(T,Position,Value) :- arg(Position,T,Value). 

delete(X, [X|R] , R).
delete(X, [Y|R] , [Y|T]) :- delete(X,R,T).

makeList(0,[]).
makeList(N,[N|R]) :- N>0, N1 is N-1, makeList(N1,R).