25. N Queens Problem

{(⍵⌿⍨+/b),⍺|⍸,b←~(⍳⍺)∊⍤1⍪↑⍵,.+(k-⍳k←⊃⌽⍴⍵)∘.ׯ1 0 1}

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 solution in J can be found in [51d]. Translated into APL:

queens←{
  arr←{(⍵⌿⍨+/b),⍺|⍸,b←~(⍳⍺)∊⍤1⍪↑⍵,.+(k-⍳k←⊃⌽⍴⍵)∘.ׯ1 0 1}
  ⍵ arr⍣⍵ ⍉⍪⍬
}

A k-arrangement ⍵ has k queens on a k-by-n board where none of queens attack another. To generate all k+1-arrangements leading from ⍵ , 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 ⍵ . The 0-arrangements are 1 0⍴0 ←→ ⍉⍪⍬ ; 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

assert←{⍺←'assertion failure' ⋄ 0∊⍵:⍺ ⎕signal 8 ⋄ shy←0}

qcheck←{
  assert 1=≢⍴⍵:
  assert(⍳≢⍵)≡{⍵[⍋⍵]}⍵:
  assert(∘.=⍨⍳≢⍵)≥(|∘.-⍨⍵)=|∘.-⍨⍳≢⍵:
  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[3] assert(∘.=⍨⍳≢⍵)≥(|∘.-⍨⍵)=|∘.-⍨⍳≢⍵:
         ∧

We now exhibit all solutions of the 8 queens problem.

   ⍴ t← queens 8
92 8

Rotational and reflectional variants can be suppressed using ideas from [84]:

   var←(∪(⊢,⍉¨,⊖¨,⌽¨))⍣3
   u← ∪ {t⌷⍨⊃⍋⍪t←↑var⊂⍵}¨ (⊂8 8⍴⍳64) ∊¨ ↓t+⍤1⊢8×⍳8
   ⍴ u
12

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 . The logic is explained in the first section of [70]:

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:

kweens←{
  p←perm ⍵
  c←2 comb ⍵
  ((|-/p[;c])^.≠|-/c)⌿p
}

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 Warnsdorf’s heuristic, invented in 1823 to solve the Knight’s Tour, and is used to advantage here. Warnsdorf’s heuristic favors children having the fewest children. At each step, all children are stacked, that is, all children are searched eventually if necessary, so that the algorithm always finds a solution if there is one.

queensw←{
  j←⌽⍳⍵
  d←(⍵-⍳⍵)∘.ׯ1 0 1
  f←{
    ⍺=≢p←⊃⌽⍵:p
    q←p,⍤1 0⊢j~p+⍤¯1⊢(-≢p)↑d
    ⍺ ∇ (¯1↓⍵),↓q⌷⍨⊂⍒j(≢~)⍤1 2⊢q+⍤¯1⍤1 2⊢(¯1-≢p)↑d
  }
  ⍵ f ,¨⌽⍳⌈⍵÷2
}

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

Appeared in APL in [70] and in J in [85].