Essays/N Queens Problem
Place n queens on an n by n board so that none attacks another. (That is, no queen is on the same row, column, or diagonal as another.)
A Solution
A verb that finds all solutions to the n queens problem can be found in the for. page of the dictionary:
queens=: 3 : 0
z=.i.n,*n=.y
for. }.z do.
b=. -. (i.n) e."1 ,. z +"1 _ ((-i.){:$z) */ _1 0 1
z=. ((+/"1 b)#z),.n|I.,b
end.
)
A k-arrangement x has k queens on a k-by-n board where none of queens attack another. To generate all k+1-arrangements leading from x, place a queen on all the places on row k which are not on the any of the columns or diagonals attacked by the queens in x. The 1-arrangements are 0, 1, 2, ..., n-1; the n-arrangements are all the solutions to the n queens problem.
For example, 0 2, 0 3, and 0 4 are valid 2-arrangements for the 8 queens problem. The 3-arrangements leading from these are:
0 2 4 0 2 5 0 2 6 0 2 7 0 3 1 0 3 5 0 3 6 0 3 7 0 4 1 0 4 6 0 4 7
qcheck checks a solution to the n queens problem.
qcheck=: 3 : 0 assert. 1=#$y assert. (i.#y)-:/:~y assert. (=i.#y) >: y =&:|&:(-/~) i.#y 1 ) queens 6 1 3 5 0 2 4 2 5 1 4 0 3 3 0 4 1 5 2 4 2 0 5 3 1 qcheck"1 queens 6 1 1 1 1 qcheck ?.~ 6 |assertion failure: qcheck | (=i.#y)>:y=&:|&:(-/~)i.#y
We now exhibit all solutions of the 8 queens problem.
$ t= queens 8 92 8
var and uvar from the Queens and Knights page are used to suppress rotational and reflectional variants.
var =: ~.@(] , |:&.> , |.&.> , |."1&.>)^:3
uvar=: ~. @: ({.@(/:~)@var&>)
u=: uvar <"0 ((i.8 8) e. ])&.> <"1 t+"1 ]8*i.8
$ u
12
load 'viewmat'
rgb=: 192,0,:255 0 0
rgb&viewmat&> (2 <. (~:/~8$0 1) + 2 * ])&.> u
That is, the 8 queens problem has 92 solutions, or 12 unique ones if rotational and reflectional variants are considered the same.
A Concise Solution
If conciseness is of primary concern then the following is worthy of consideration. Here it is assumed that n>1 .
queensx=: 3 : 0
p=. |: perm y
c=. |: comb2 y
|: p #"1~ c */@:~:&(|@-/) c{p
)
perm =: ! A.&i. ]
comb2 =: (, #: I.@,@(</)&i.)~
mask =: [ */@:~:&(|@-/) {
queenst=: comb2 (] #"1~ mask)&.|: perm
(queens -: queensx)"0 ]2+i.7
1 1 1 1 1 1 1
(queens -: queenst)"0 ]2+i.7
1 1 1 1 1 1 1
queenst f.
(, #: I.@,@(</)&i.)~ (] #"1~ [ */@:~:&(|@-/) {)&.|: ! A.&i. ]
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 ⍳n , which are the column indices, with the row indices understood to be ⍳n . With this, the number of possibilities is reduced from n!n×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 ¯1 . Conversely, if the line connecting two queens has slope 1 or ¯1 , the two queens share a diagonal. Therefore, we seek to eliminate all permutations specifying a pair of queens where
((change in y) ÷ (change in x)) ∊ 1 ¯1 ,
or
(|change in y) = (|change in x)
Let p←perm n be a function where rows of p are all the permutations of ⍳n ; and c←n comb m be a function where rows of c are all size n combinations of ⍳m . We can now solve the n queens problem:
∇ z←kweens n;c;p ⍝ all solns to the <n> queens problem p←perm n c←2 comb n z←((|-/p[;c])^.≠|-/c)⌿p ∇
(See Appendix for definitions of perm and comb .) For each permutation, we compute the change in column indices (y) and the change in row indices (x) for all distinct pairs of queens. A permutation is a solution if and only if the absolute values of these are unequal.
Depth First Search
For large n , the number of solutions is very large and it is impractical to find all of them. queensw below uses a depth first search, stopping on finding the first solution (or on failing to find a solution). The search is guided by Warnsdorff's heuristic, invented in 1823 to solve the Knight's Tour, and is used to advantage here. Warnsdorff's heuristic favors sons having the fewest grandsons. At each step, all sons are stacked, that is, all sons are searched eventually if necessary, so that the algorithm always finds a solution if there is one.
queensw=: 3 : 0
j=. i.-y
d=. ((-i.)y)*/_1 0 1
stack=. ,&.> i.->.-:y
while. #stack do.
p=. >{:stack
if. y=#p do. return. end.
q=. p,"1 0 j-.p+(-#p){.d
stack=. (}:stack),<"1 q\:j#@-."1 2 q+"1 2 (_1-#p){.d
end.
)
For example:
] s=: queensw 29 0 4 8 12 2 17 21 25 10 14 6 22 26 7 15 19 23 27 1 5 28 9 3 20 11 24 16 18 13 qcheck s 1 rgb=: 192,0,:255 0 0 rgb viewmat (2 <. (~:/~(#s)$0 1) + 2 * ]) s=/i.#s
Collected Definitions
queens=: 3 : 0
z=.i.n,*n=.y
for. }.z do.
b=. -. (i.n) e."1 ,. z +"1 _ ((-i.){:$z) */ _1 0 1
z=. ((+/"1 b)#z),.n|I.,b
end.
)
qcheck=: 3 : 0
assert. 1=#$y
assert. (i.#y)-:/:~y
assert. (=i.#y) >: y =&:|&:(-/~) i.#y
1
)
var =: ~.@(] , |:&.> , |.&.> , |."1&.>)^:3
uvar=: ~. @: ({.@(/:~)@var&>)
queensx=: 3 : 0
p=. |: perm y
c=. |: comb2 y
|: p #"1~ c */@:~:&(|@-/) c{p
)
perm =: ! A.&i. ]
comb2 =: (, #: I.@,@(</)&i.)~
mask =: [ */@:~:&(|@-/) {
queenst=: comb2 (] #"1~ mask)&.|: perm
queensw=: 3 : 0
j=. i.-y
d=. ((-i.)y)*/_1 0 1
stack=. ,&.> i.->.-:y
while. #stack do.
p=. >{:stack
if. y=#p do. return. end.
q=. p,"1 0 j-.p+(-#p){.d
stack=. (}:stack),<"1 q\:j#@-."1 2 q+"1 2 (_1-#p){.d
end.
)
See also
Contributed by Roger Hui.