﻿ The N Queens Problem

The N Queens Problem
Roger Hui

Problem: place n queens on an n×n chess board so that no two are on the same row, column, or diagonal. (Call this the n queens property.) Determine all such configurations.

An Initial Solution

We represent the chess board by an n,n matrix. An arrangement of the n queens are the row and column indices of their locations on a board; a solution is an arrangement satisfying the n queens property.

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 row (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.

Computational Considerations

It is hard to imagine a more succinct n queens function than kweens ! However, for all its “elegance”, kweens has two rather large drawbacks:

 • It is voracious for work space. For concreteness, consider the case n←8 . The intermediate expression p[;c] has shape (!8),(2!8),2 , requiring 9031704 bytes on IBM-based APL systems. • It is grossly inefficient. Again, consider the case n←8 . No solution can begin with ⍳2 ; yet, in the array p , there are !6 such arrangements, and for each of these, 2!8 slopes are computed, for a total of 20160-1 redundant slope computations. And this is just for arrangements beginning with ⍳2 !

We present an alternative which avoids these pitfalls, by not generating too many intermediate invalid arrangements.

The method is recursive. Let a k-solution be the column indices of queens placed on the first k rows, with no pair sharing a row, column, or diagonal. The 1-solutions are (n,×n)⍴⍳n . Now, assume we have all k-solutions; we wish to generate all (1+k)-solutions. The queen on the next row can be placed on columns not occupied in the first k rows, and are not on any diagonals occupied in those rows. For example,

```   0 1 2 3 4 5 6 7
0 . × . . . . . .
1 . . . × . . . .
2 . . . . . × . .
3 + . + . . . . +
```

from the 3-solution 1 3 5 , we get the 4-solutions 1 3 5 0 , 1 3 5 2 , and 1 3 5 7 . If a k-solution has no possible next entry, we know it cannot be part of a solution and can be ignored.

```∇ z←queens n;b;i;k;m;s
⍝ all solns to the <n> queens problem
s←2+n
k←0
z←(n,×n)⍴⍳n
→l20
l10:m←1↑⍴z
b←(m×s)⍴1
i←⍉(k,m)⍴s×(⍳m)-⎕io
b[1+i+z]←0
b[i+⎕io⌈z+(⍴z)⍴⌽⎕io-⍳k]←0
b[i+(1+⎕io+n)⌊z+(⍴z)⍴⌽2-⎕io-⍳k]←0
b←(0,(n⍴1),0)/(m,s)⍴b
z←((+/b)⌿z),(,b)/(×/⍴b)⍴⍳n
l20:→(n>k←1+k)⍴l10
∇
```

(Note: The expression (+/b)⌿z in the penultimate line uses SHARP APL’s replicate function , a generalization of compression. A specialized version of replicate is:

```∇ z←l rep mat;c;i
⍝ replicate mat[i;] l[i] times
c←0<l
i←(+/l)⍴0
i[+\¯1↓(⍳⍳1),c/l]←1
z←(c⌿mat)[+\i;]
∇                       )

```

Interlude: Pictures, Reflections, and Rotations

Earlier, we identified a permutation p with the coordinates (⍳n;p) in an n,n matrix: ⍳n are the row indices; p the column indices. Let the picture of a permutation p be the matrix of '.'s, with locations specified by p being '×' (say). It is simple to convert from permutations to pictures and vice versa:

```∇ z←pic p
⍝ pictures of permutations <p>
z←'.×'[⎕io+p∘.=⍳¯1↑⍴p]
∇

∇ z←unpic p
⍝ permutations corresp. to pictures <p>
z←(⎕io+¯1↑⍴p)-+/∨\p∊'×'
∇
```

Since a 1-1 correspondence exists between permutations and pictures having exactly one '×' on each row and each column, we shall frequently speak of a permutation and its picture interchangeably.

The (horizontal) reflection of a matrix m is ⊖m , and the ○÷2 rotation of m is the rotation of m by ○÷2 radians (⊖⍉m); the reflection androtation of permutation p are, respectively, the reflection androtation of the picture of p .

```   20314    42031    03142    31420
..×..    ....×    ×....    ...×.
×....    ..×..    ...×.    .×...
0 ...×.  1 ×....  2 .×...  3 ....×
.×...    ...×.    ....×    ..×..
....×    .×...    ..×..    ×....

41302    13024    24130    02413
....×    .×...    ..×..    ×....
.×...    ...×.    ....×    ..×..
4 ...×.  5 ×....  6 .×...  7 ....×
×....    ..×..    ...×.    .×...
..×..    ....×    ×....    ...×.
```

The reflection of p is easily seen to be ⌽p . What about the ○÷2 rotation q of p ? If m←pic p , then (⊖⍉m)[i;j] ←→ m[(n+⎕io-~⎕io)-j;i] , and q are the coordinates (((n+⎕io-~⎕io)-p;⍳n) . Converting into standard form (so that the row indices are ⍳n) , q←⍋(n+⎕io-~⎕io)-p , or, more (most) concisely, q←⍒p .

A natural next question is an expression for the ○÷¯2 rotation q of p . q←⍒⍒⍒p , since the ○÷¯2 rotation is the same as the ○3÷2 rotation; and q←⌽⍒⌽p , since rotating by ○÷¯2 is the same as reflecting, then rotating by ○÷2 , then reflecting again. Hence, within the domain of permutations, we have ⍒⍒⍒ ←→ ⌽⍒⌽ .

What is ⍋p ? It is the inverse of p . In terms of pictures, pic ⍋p ←→ ⍉pic p (graph of the inverse). But ⍉pic p ←→ pic ⌽⍒p ; hence ⍋ ←→ ⌽⍒ . An algebraic proof is p[⍋p] ←→ ⌽p[⍒p] ←→ p[⌽⍒p] , so ⍋ ←→ ⌽⍒ .

We now describe informally the minisystem PRR for proving some identities involving strings of the symbols + ⌽ ⍒ ⍋ on permutations. The symbols are interpreted in PRR as functions on the digits 0 1 2 3 4 5 6 7 , with the following definitions:

 +k k itself ⌽k 8|4+k ⍒k 1↑k↓ 1 2 3 0 7 4 5 6 ⍋k 1↑k↓ 5 6 7 4 3 0 1 2

The digits represent the reflectional and rotational variants of a permutation; the rules are based on their geometry. (See the eight 5x5 pictures above.)

A string of symbols defines a function on the starting digit 0 ; the ending digit is obtained by applying each symbol in the string, from right to left. Two strings are equivalent if their ending digits are equal. It is a metatheorem that equivalences in PRR are equivalences in APL within the domain of permutations. Some equivalences and their proofs:

```   Equivalences        Proof
⍒⍒⍒⍒ ←→ +           01230  00
⍋⍋   ←→ +           050    00
⌽⌽   ←→ +           040    00
⍒⍒⍒  ←→ ⌽⍒⌽         0123   0473
⍋    ←→ ⌽⍒          05     015
⍒⍒⍒  ←→ ⍋⌽          0123   043
⌽⍋   ←→ ⍒           051    01
⍒⍋   ←→ ⌽           054    04
⍒⍋⍒  ←→ ⍋           0165   05

```

Essentially Different Solutions

We return to the n queens problem. Fact: if a permutation satisfies the n queens property, then so do its reflections and rotations. We can add a twist to the n queens problem by requiring only the essentially different solutions. Two solutions are essentially the same if one can be obtained from the other by reflections and/or rotations; they are essentially different otherwise.

This is simple, since we know how to reflect and rotate permutations. For each solution, consider the lexicographically least of the solutions essentially the same as it, then take only those having distinct minima.

```∇ z←unique p;i;j;n
⍝ the essentially different of permutations <p> (matrix)
n←''⍴1↓⍴p
i←n⊥n⍴n
j←4
l10:i←i⌊(n⊥⍉p)⌊n⊥⍉⌽p
p←rot p
→(×j←j-1)⍴l10
i←i[j←⍋i]
z←p[(i≠¯1↓0,i)/j;]
∇
```

Function rot , which computes ○÷2 rotations, uses a less elegant but provably more efficient equivalent of ⍒p :

```  q[(n+⎕io-~⎕io)-p]←q←⍳n
q ←→ ⍒p

∇ z←rot p;rho
⍝ ○÷2 rotation of permutations <p>
n←1⌈¯1↑rho←⍴p
z←(×/rho)⍴2
z[((¯1⌽⍳⍴rho)⍉(¯1⌽rho)⍴(n+⎕io-~⎕io)+n×(⍳×/¯1↓rho)-
⎕io)-p]←rho⍴⍳n
z←rho⍴z
∇
```

Since the n queens problem is traditionally stated with n←8 , we conclude by discussing some results for the 8 queens problem. There are 92 solutions, with 12 essentially different ones. The expression

```(36⍴(8⍴1),0)\ 3 8 32 ⍴ (⎕io+ 0 2 1 3)⍉pic 3 4 8 ⍴
unique queens 8
```

generates a pleasing display.

Appendix: Functions perm and comb

```∇ p←perm n;i;ind;t
⍝ all permutations of ⍳n
p←(×n,n)⍴⎕io
→(1≥n)⍴0
t←perm n-1
p←(0,n)⍴ind←⍳n
i←n-~⎕io
l10:p←(i,((i≠ind)/ind)[t]),[⎕io] p
→(⎕io≤i←i-1)⍴l10
∇

∇ r←n comb m;cons;ct;i;j;offset;t
⍝ all size <n> combinations of ⍳m
i←1+(×n)×m-n
cons←''⍴2+i-offset←1-⎕io
ct←(⎕io↓0),i⍴j←1
r←(i,×n)⍴⍳i
→l30
l10:i←offset+cons-2
r←⎕io,t←1+r
l20:r←r,[⎕io](cons-i),t←(ct[i],0)↓t
→(1<i←i-1)⍴l20
ct←+\ct
l30:→(n≥j←1+j)⍴l10
∇
```

The results of perm and comb are in lexicographic order. Much more elegant definitions of these functions exist. For example, the following is by R. De Haas of Edmonton, Alberta:

```∇ r←n combin m;t
⍝ all size <n> combinations of ⍳m
t←⍉(m⍴2)⊤⌽(⍳2*m)-⎕io
z←((n!m),n)⍴(,(n=+/t)⌿t)/(m×n!m)⍴⍳m
∇
```

However, comb can be many times faster, and requires less work space.

Acknowledgments

The ideas described herein were developed with computational support from I.P. Sharp Associates.

Originally appeared as The N Queens Problem, APL Quote Quad, Volume 11, Number 3, 1981-03.

 created: 2008-04-11 13:55 updated: 2013-06-17 10:30