The logic is explained in the first section of
Hui, Roger, "The N-Queens Problem", APL Quote-Quad,
Volume 11, Number 3, 1981-03.
...
In a solution, each possible row (column) index
must appear exactly once: an index occurring
more than once means that two queens are on the
same (column), and the absence of an index means
that some other index must occur more than once.
Hence, we can specify an arrangement as a
permutation of {iota}n, representing the column
indices, with the row indices understood to be
{iota}n. Knowing this, the number of possibilities
is reduced from n!n{times}n to !n. It remains to
eliminate arrangements having two queens on the
same diagonal.
If two queens occupy the same diagonal, the line
connecting them has slope 1 or {minus}1, and
conversely. Therefore, we seek to eliminate all
permutations in which any pair of queens has:
(|change in y) = (|change in x)
Let perm be a function of n producing a matrix
whose rows are all the permutations of {iota}n.
Let n comb m produce a matrix whose rows are all
the size-n combinations of {iota}m. We can now
solve the n-queens problem:
{del} z{is}kweens n;c;p
{comment} all sol'ns to the n-queens problem
p{is}perm n
c{is}2 comb n
z{is}((|-/p[;c]){and}.{not equal}|-/c){slash bar} p
{del}
(See Appendix for definitions of perm and comb.)
For each permutation, we compute the difference
in column indices (y) and the difference in row
indices (x) for each distinct pair of queens.
A permutation is a solution if and only if the
absolute values of these differences are unequal.
* * * *
The APL solution translates pretty directly
to the following J explicit verb and thence to
a tacit verb.
queens6e=: 3 : 0
p=. perm y
c=. comb2 y
p #~ (c{"1/p) */ .~:&(|@-/) c
)
perm =: ! A.&i. ]
comb2 =: |:@(</"1 # ])@(, #: [EMAIL PROTECTED])~
mask =: {"1/ */ .~:&(|@-/) [
queens6=: comb2 (] #~ mask) perm
queens6 f.
|:@(</"1 # ])@(, #: [EMAIL PROTECTED])~ (] #~ {"1/ */ .~:&(|@-/) [) ! A.&i. ]
----- Original Message -----
From: Raul Miller <[EMAIL PROTECTED]>
Date: Monday, April 7, 2008 6:13
Subject: Re: [Jgeneral] How readable is J?
To: General forum <[email protected]>
> On Sun, Apr 6, 2008 at 8:15 PM, Roger Hui <[EMAIL PROTECTED]> wrote:
> > If conciseness is a primary concern then the following
> > is worthy of consideration. ...
>
> I find concise approaches to be very interesting, because
> they tend to encapsulate ideas in interesting ways.
>
> Thank you!
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
