New J Challenge
Author Message
New J Challenge

J. Storrs Hall poses a challenge on the n queens problem on Tuesday, November 3.

I had previously worked on this puzzle (see "The N-Queens Problem", APL Quote-Quad,
Volume 11, Number 3, 1981 3).  The appended script are various solutions to the
problem in J.

The immediate challenge is to write a proposition on permutations that
discriminates a solution to the n-queens problem.  The answer is a composition
of the verbs test and inc below, viz., (inc y.) test"_ 1 y., easily written
on one line and/or written in tacit form if so desired.
____________________________________________________________

NB. various solutions to the n queens problem

q1  =: 3 : 'p #~ (inc y.) test"_ 1 p=.perm y.'

test=: 4 : '*/*/ ~:"1 |: y.+x.'

q2=: 3 : 0
n=. y.
s=. 2+n
k=. 0
z=. (n,*n)\$i.n
while. n>k=.1+k do.
m=. #z
b=. (m*s)\$1
i=. |:(k,m)\$s*i.m
b=. 0 (1+i+z)}b
b=. 0 (i+0>.z-"1 i.-k)}b
b=. 0 (i+(1+n)<.z+"1 ] 2+i.-k)}b
b=. (0,(n\$1),0)#"1 (m,s)\$b
z=. ((+/"1 b)#z),.(,b)#(*/\$b)\$i.n
end.
)

n=. x.
z=. y.
k=. {:\$z
b=. ((#z)*2+n)\$1
i=. (i.#z)*/k#2+n
b=. 0 (1+i+z)}b
b=. 0 (i+0    >.z-"1 i.-k    )}b
b=. 0 (i+(1+n)<.z+"1 ] 2+i.-k)}b
(-2+n) (0,(n\$1),0)&#\b
)

n   =: [
q3  =: n grow^:(0:>.n-1:) seed

q4  =: 3 : 0
n=. y.
z=. seed n
while. n>{:\$z do. z=. (n mask z) ext z end.
)

____________________________________________________________

q1 5
0 2 4 1 3
0 3 1 4 2
1 3 0 2 4
1 4 2 0 3
2 0 3 1 4
2 4 1 3 0
3 0 2 4 1
3 1 4 2 0
4 1 3 0 2
4 2 0 3 1

(q1 -: q2) 5
1
(q1 -: q3) 5
1
(q1 -: q4) 5
1

Wed, 25 Apr 2001 03:00:00 GMT

 Page 1 of 1 [ 1 post ]

Relevant Pages
 10. profile.js