|
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
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 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 |
|