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.
)

mask=: 4 : 0
 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
)




grow=: mask ext ]
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  
 
 [ 1 post ] 

 Relevant Pages 

1. JS-EAI with *JS*-callback

2. js.exception 3279.js

3. New J challenge

4. SmallTalk vs C++ Challenge! 8/17/95 New York City

5. a new challenge

6. New Nudds Challenge: Write PASM

7. new challenge in prolog

8. NB. gray.js: a J verb that generates a grayscale postscript image from a 2d array

9. lapackTest.js

10. profile.js

11. J script file profile.js

12. JS valueOf() in RB ?

 

 
Powered by phpBB® Forum Software