The N Queens Problem
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 ,
(|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.
It is hard to imagine a more succinct n queens function than kweens ! However, for all its “elegance”, kweens has two rather large drawbacks:
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
∇ 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 and ⍺ rotation of permutation p are, respectively, the reflection and ⍺ rotation 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 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.
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.