Current issue

Vol.26 No.4

Vol.26 No.4

Volumes

© 1984-2017
British APL Association
All rights reserved.

Archive articles posted online on request: ask the archivist.

archive/10/3

Volume 10, No.3

The N-Queens Problem in One Line

by R.G. Selfridge

The July 1993 edition of Vector has an article discussing putting Queens on a chessboard so that no two can attack each other (Backtracking, Queens and Permutations, pp34-38). Given the old myth (?) that any program can be written as a single APL statement, I naturally ask if this is possible for the Queens problem. Here is the ‘yes’ answer to that question:

     ∇ z←x q b
[1]    →⍎(((0=⍴x)/'0,(⍴p←z←'''')q(b,b)⍴0×d←
         ((n-k)⊖d)∨d∨⌽d←n∘.=n←⍳¯1+2×k←b')),
         (z←0≠⍴x)/'⍎(((k=⍴x)∨~i)/''0''),
         ((i^k≠⍴x)/''(x,0)q b∨(⍴b)↑((⍴b)-x[⍴x],⍴x)↓d''),
         ((i^k=⍴x)/'',⍴p←x,p''),(((1=⍴x)^~i)/'',p''),
         ((i^(⎕pw<(2×k+1)×1+(⍴p)÷k)^k=⍴x)∨
         (1=⍴x)^~i←k≥x[⍴x]←x[⍴x]+(x[⍴x]↓,b[;⍴x])⍳0)/
         ''←0⍴⎕←''''| _Q''''[(2+p[1;]>2),[1]
         p←1+((2×1↓⍴p)⍴0 1)\1+p←(((1+k)×(1↓⍴p)÷k)⍴(k⍴1),0)\
         1+p←(⍳k)∘.=p]'''
     ∇
     '' q 4
 _ _ _ _   _ _ _ _
|_|Q|_|_| |_|_|Q|_|
|_|_|_|Q| |Q|_|_|_|
|Q|_|_|_| |_|_|_|Q|
|_|_|Q|_| |_|Q|_|_|

Let me add that no claim is made that this is ‘good’ APL, only that it was a challenge to see if it could be done. Timing against a ‘proper’ program actually shows that this function is only twice as slow. The function will take any board size, greater than 3, and will print out as many boards across the screen as permitted by ⎕PW (sanity suggests that board sizes greater than 9 or 10 not be tried, since there will be quite a wait for the output to complete).

(36 minutes for ’’ q 11 on a DX2/50 with Dyalog APL/W ... and I think Richard Smith deserves the next Outstanding Achievement Award for typing this in from the listing and getting it to run first shot! Production Ed.)


(webpage generated: 18 February 2006, 02:17)

script began 3:12:28
caching off
debug mode off
cache time 3600 sec
indmtime not found in cache
cached index is fresh
recompiling index.xml
index compiled in 0.3018 secs
read index
read issues/index.xml
identified 26 volumes, 101 issues
array (
  'id' => '10007880',
)
regenerated static HTML
article source is 'HTML'
source file encoding is 'ASCII'
read as 'Windows-1252'
completed in 0.3289 secs