cmats ← ##.queens N ⍝ The N-Queens Problem
Place N Queens on an N×N chessboard such that no queen is attacking any other.
This coding returns all unique solutions for the given board as a vector of
character matrices with '⍟' representing a queen. Trivially equivalent solutions
that represent rotations and reflections are omitted.
Technical notes:
There are many ways to approach this problem. A simple but rather expensive
method is to generate all permutations (see →pmat←) of ⍳⍵ and then filter out
those that represent a solution. The approach used here is a tree search: First,
place a queen anywhere in the first row (or "rank" in chess-speak). Next, place
a second queen in the second rank on any square not attacked by the first one.
Continue placing queens on "safe" squares in successive ranks until either all
ranks have been covered (a configuration that constitutes a solution) or until a
rank is reached where all squares are attacked by previously placed queens. In
the latter case, "back track" to the last rank where all squares have not yet
been tried and after moving that queen to a different square, try again.
For a standard 8×8 chessboard, there are 96 solutions but these include 2 ref-
lections and 4 rotations of each "distinct" solution, so in fact there are only
12 interesting solutions. Part of the challenge is to avoid generating or to re-
move these duplicates.
During the search, the current state of play is represented by two vectors, each
item of which corresponds to a rank. The first is a simple vector of placements
already made and the second, a vector of vectors of remaining free squares per
rank. For example, after placing the first 4 queens, the state of play might
look like this:
file: 0 1 2 3 4 5 6 7
┌───────────────┐ ⍟ placed queen.
rank: 0 │· ⍟ · · · · · ·│ ○ free square.
1 │· · · ⍟ · · · ·│
2 │· · · · · · ⍟ ·│
3 │⍟ · · · · · · ·│
4 │· · ○ · · · · ○│
5 │· · · · ○ ○ · ·│
6 │· · · · ○ ○ · ·│
7 │· · ○ · · ○ · ○│
└───────────────┘
The vector of placements is 1 3 6 0, and the vector of free squares is (2 7),
(4 5)(4 5)(2 5 7). Placing the next queen in column 2, would render the state of
play:
file: 0 1 2 3 4 5 6 7
┌───────────────┐ ⍟ placed queen.
rank: 0 │· ⍟ · · · · · ·│ ○ free square.
1 │· · · ⍟ · · · ·│
2 │· · · · · · ⍟ ·│
3 │⍟ · · · · · · ·│
4 │· · ⍟ · · · · ·│
5 │· · · · ○ ○ · ·│
6 │· · · · · ○ · ·│
7 │· · · · · · · ○│
└───────────────┘
with placement vector: 1 3 6 0 2, and free-square vector: (4 5)(5)(7).
The search is implemented by passing the placement vector as left argument and
free-square vector as right argument to inner function [search]: The tree search
consists of appending in turn, each free square from the next rank, to the
placement vector and recursively calling search with a reduced vector of free
squares. Search returns if either any of the ranks contain no free squares:
(⊂⍬)∊⍵, or no ranks remain: 0=⍴⍵, which constitutes a solution. Notice a small
detail: the result when there are no free squares must be suitably enclosed:
0⍴⊂⍬, so that in the three cases where there are no solutions queens¨0 2 3, the
overall result is a vector of _matrices_ in common with all other cases.
search←{ ⍝ Search for all solutions.
(⊂⍬)∊⍵:0⍴⊂⍬ ⍝ stitched: abandon this branch.
0=⍴⍵:rmdups ⍺ ⍝ all done: solution!
hd tl←(⊃⍵)(1↓⍵) ⍝ head 'n tail of remaining ranks.
next←⍺∘,¨hd ⍝ possible next steps.
rems←hd free¨⊂tl ⍝ unchecked squares.
↑,/next ∇¨rems ⍝ ... in following ranks.
}
[Free] returns a new vector of free-squares after those in check from the next
placement have been removed:
free←{⍵~¨⍺+(⍴⍵)↑cvex} ⍝ Unchecked squares.
As [cvex], is invariant during the search, it is computed initially as an optim-
isation.
cvex←(1+⍳⍵)×⊂¯1 0 1 ⍝ Checking vectors.
Given that the final solution vector must contain no duplicates, a further opti-
misation is to start the tree search from only half of the squares in the first
rank. Any solution resulting from a search starting from the remaining squares
must constitute a "reflected" solution. So instead of:
squares←⍵⍴⊂⍳⍵ ⍝ (0 1 2 3 4 5 6 7) (0 1 2 3 4 5 6 7) ···
we have:
squares←(⊂⍳⌈⍵÷2),1↓⍵⍴⊂⍳⍵ ⍝ (0 1 2 3) (0 1 2 3 4 5 6 7) ···
which _halves_ the total search time.
[rmdups] discards "boring" equivalent solutions by generating all 4 rotations
and 2 reflections and then rejecting the putative solution if it isn't the
most attractive member of this set:
rmdups←{ ⍝ Ignore duplicate solution.
rots←{{⍒⍵}\4/⊂⍵} ⍝ 4 rotations.
refs←{{⍋⍵}\2/⊂⍵} ⍝ 2 reflections.
best←{(⊃⍋↑⍵)⊃⍵} ⍝ best (=lowest) solution.
all8←,↑refs¨rots ⍵ ⍝ all 8 orientations.
(⍵≡best all8)⊃⍬(,⊂⍵) ⍝ ignore if not best.
}
Finally, [fmt] renders each solution as a character matrix with '·' for an empty
square and '⍟' for an occupied one. Each matrix is spread horizontally to make
it appear more square-shaped on the screen.
fmt←{ ⍝ Format solution.
chars←'·⍟'[(↑⍵)∘.=⍳⍺] ⍝ char array of placed queens.
expd←1↓,↑⍺⍴⊂0 1 ⍝ expansion mask.
↑¨↓↓expd\chars ⍝ vector of char matrices.
}
Alternative Codings
-------------------
The following, perhaps rather opaque coding, is remarkable in that it is a
_single expression_ for the vector of unique solutions to the problem in the
same way that {+/⍵÷⍴⍵} is a single expression for the mean value of a numeric
vector. It contains no guards; just applications of operators to operands and
functions to arguments. The code assumes an index-origin and migration-level of
0.
{⍵{↑¨↓↓(2|1↓⍳2×⍺)\((↑⍵)∘.=⍳⍺)⊃¨⊂'·⍟'}∪{{(⊃⍋↑⍵)⊃⍵},↑⍵}¨{{⍋⍵}\2/⊂⍵}¨∘{{⍒⍵}\4/⊂⍵}¨⍵{(⍺=,↑⍴¨⍵)/⍵},¨↑⍬{↑(⍺⍺,⍺)∇∇(1↓⍵⍵~¨⍺+(1+⍳⍴⍵⍵)×⊂¯1 0 1)/((⊃⍵⍵)~⍺+¯1 0 1),⊂⍵,⊂⍺⍺,⍺}(1↓⍵⍴⊂⌽⍳⍵)/(⌽⍳⌈⍵÷2),⊂0⍴⊂⍬}
We can prove that it works by pasting it into the session and appending an argu-
ment (such as 8) after remembering to set ⎕io←0. To examine it further, we might
find it helpful to assign a name and use the editor to split it up a little:
qn←{
⍵{
↑¨↓↓(2|1↓⍳2×⍺)\((↑⍵)∘.=⍳⍺)⊃¨⊂'·⍟'
}∪{
{(⊃⍋↑⍵)⊃⍵},↑⍵
}¨{
{⍋⍵}\2/⊂⍵
}¨∘{
{⍒⍵}\4/⊂⍵
}¨⍵{
(⍺=,↑⍴¨⍵)/⍵
},¨↑⍬{
↑(⍺⍺,⍺)∇∇(1↓⍵⍵~¨⍺+(1+⍳⍴⍵⍵)×⊂¯1 0 1)/((⊃⍵⍵)~⍺+¯1 0 1),⊂⍵,⊂⍺⍺,⍺
}(1↓⍵⍴⊂⌽⍳⍵)/(⌽⍳⌈⍵÷2),⊂0⍴⊂⍬
}
The left side (top in the wrapped version) of the expression is much the same as
[queens], except that the slightly shorter and quicker: '·⍟'[(↑⍵)∘.=⍳⍺] has been
replaced by the slightly purer ((↑⍵)∘.=⍳⍺)⊃¨⊂'·⍟', in order to avoid APL's argu-
ably anomalous square-bracket syntax.
The main difference is in the search sub-expression, which uses _reduce /_
rather than _each ¨_ to recur along ranks.
↑⍬{
↑(⍺⍺,⍺)∇∇(1↓⍵⍵~¨⍺+(1+⍳⍴⍵⍵)×⊂¯1 0 1)/((⊃⍵⍵)~⍺+¯1 0 1),⊂⍵,⊂⍺⍺,⍺
}(1↓⍵⍴⊂⌽⍳⍵)/(⌽⍳⌈⍵÷2),⊂0⍴⊂⍬
The operand of the outer reduction is a function derived from the inner dyadic
operator whose left and right array operands are the placement and free-square
vectors respectively:
↑··· ⍝ disclose result of reduction.
·⍬{ ⍝ left operand: placement vector.
··· ⍝ inner dyadic operator.
}(1↓⍵⍴⊂⌽⍳⍵)··· ⍝ right operand: free-square vector.
···········/··· ⍝ reduction with above derived function.
The argument to the reduction is the vector of squares in the first rank and
emulates queens in representing only half of the files as an optimisation. The
final item is the vector of solutions so-far and is enclosed to ensure the
correct rank for the three cases where there are no solutions.
············(⌽⍳⌈⍵÷2),⊂0⍴⊂⍬
The inner dyadic operator then, has operands/arguments:
Left argument: next square in current rank.
Left operand: current placement vector.
Right operand: free-square vector.
Right argument: vector of solutions-so-far.
This leaves just the code _inside_ the operator, which is another reduction
using a recursive call with new values for the left and right operands:
↑(⍺⍺,⍺)∇∇(1↓⍵⍵~¨⍺+(1+⍳⍴⍵⍵)×⊂¯1 0 1)/((⊃⍵⍵)~⍺+¯1 0 1),⊂⍵,⊂⍺⍺,⍺
This breaks down as a reduction:
↑··································· ⍝ disclose result of reduction.
·······∇∇··························· ⍝ recursive call on operator with
·(⍺⍺,⍺)····························· ⍝ operands: extended placement vector
·········(1↓⍵⍵~¨⍺+(1+⍳⍴⍵⍵)×⊂¯1 0 1)· ⍝ and reduced free-square vector.
···································/ ⍝ ... reduction.
The argument to the reduction is the vector of solutions-so-far extended with
the new path and prefixed with the vector of remaining squares in the next rank:
····································((⊃⍵⍵)~⍺+¯1 0 1),⊂⍵,⊂⍺⍺,⍺
The new path: _⍺⍺,⍺_ does not constitute a solution if it's shorter than ⍵
items. These 'short' solutions are removed later when full-length vectors are
filtered out by the next function:
⍵{ ⍝ board size.
(⍺=,↑⍴¨⍵)/⍵ ⍝ filter out full-length solutions.
}
Roger Hui suggests this coding. Transliterated from J, it finds all solutions
including reflections and rotations:
queens←{⍵{((+/b)⌿⍵),⍺|(,b)/⍳×/⍴b←~↑(⊂⍳⍺)∊¨(↓⍵)+[0]¨⊂(c-⍳c←1↓⍴⍵)∘.ׯ1 0 1}⍣⍵⍳1 0}
See: http://jsoftware.com/jwiki/Essays/N_Queens_Problem
This coding, which includes reflections and rotations, uses depth-first travers-
al operator →trav←:
qtrav←{ ⍝ N-queens using trav DFS.
subs←{(⊂⍵),¨(⍳⍴⊃⍺)~atk ⍵} ⍝ sub-trees of tree-node ⍵.
accm←{⍺,((⍴⍵)=⍴⊃⍺)/⊂⍵} ⍝ accumlation of N-placement.
atk←{↑(⊂⍵)+¯1 0 1×⊂⌽⍳⍴⍵} ⍝ columns under attack in row 1+⍵.
fmt←{⍵∘.=⍳⍴⍵} ⍝ formatted as bool matrix.
fmt¨(↓0 ⍵⍴0)accm trav subs ⍬ ⍝ formatted solutions.
}
See also this YouTube video: https://www.youtube.com/watch?v=DsZdfnlh_d0
Examples:
1 disp∘queens¨0 1 2 3 4 5 6 ⍝ solutions for small boards.
┌───┬───┬─────┬───────┬─────────┬─────────────────────┬─────────────┐
│┌⊖┐│┌→┐│┌⊖──┐│┌⊖────┐│┌→──────┐│┌→────────┬─────────┐│┌→──────────┐│
││ ⌽││⍟↓││ ⌽││ ⌽││· ⍟ · ·│││⍟ · · · ·│· ⍟ · · ·│││· ⍟ · · · ·││
│└⊖┘│└→┘│└──→┘│└────→┘││· · · ⍟│││· · ⍟ · ·│· · · · ⍟│││· · · ⍟ · ·││
│ │ │ │ ││⍟ · · ·│││· · · · ⍟│· · ⍟ · ·│││· · · · · ⍟││
│ │ │ │ ││· · ⍟ ·↓││· ⍟ · · ·│⍟ · · · ·│││⍟ · · · · ·││
│ │ │ │ │└──────→┘││· · · ⍟ ·↓· · · ⍟ ·↓││· · ⍟ · · ·││
│ │ │ │ │ │└────────→┴────────→┘││· · · · ⍟ ·↓│
│ │ │ │ │ │ │└──────────→┘│
└───┴───┴─────┴───────┴─────────┴─────────────────────┴─────────────┘
queens 7
┌─────────────┬─────────────┬─────────────┬─────────────┬─────────────┬─────────────┐
│⍟ · · · · · ·│⍟ · · · · · ·│· ⍟ · · · · ·│· ⍟ · · · · ·│· ⍟ · · · · ·│· ⍟ · · · · ·│
│· · ⍟ · · · ·│· · · ⍟ · · ·│· · · ⍟ · · ·│· · · · ⍟ · ·│· · · · ⍟ · ·│· · · · · ⍟ ·│
│· · · · ⍟ · ·│· · · · · · ⍟│⍟ · · · · · ·│⍟ · · · · · ·│· · · · · · ⍟│· · ⍟ · · · ·│
│· · · · · · ⍟│· · ⍟ · · · ·│· · · · · · ⍟│· · · ⍟ · · ·│· · · ⍟ · · ·│· · · · · · ⍟│
│· ⍟ · · · · ·│· · · · · ⍟ ·│· · · · ⍟ · ·│· · · · · · ⍟│⍟ · · · · · ·│· · · ⍟ · · ·│
│· · · ⍟ · · ·│· ⍟ · · · · ·│· · ⍟ · · · ·│· · ⍟ · · · ·│· · ⍟ · · · ·│⍟ · · · · · ·│
│· · · · · ⍟ ·│· · · · ⍟ · ·│· · · · · ⍟ ·│· · · · · ⍟ ·│· · · · · ⍟ ·│· · · · ⍟ · ·│
└─────────────┴─────────────┴─────────────┴─────────────┴─────────────┴─────────────┘
3 4⍴ queens 8
┌───────────────┬───────────────┬───────────────┬───────────────┐
│⍟ · · · · · · ·│⍟ · · · · · · ·│· ⍟ · · · · · ·│· ⍟ · · · · · ·│
│· · · · ⍟ · · ·│· · · · · ⍟ · ·│· · · ⍟ · · · ·│· · · · ⍟ · · ·│
│· · · · · · · ⍟│· · · · · · · ⍟│· · · · · ⍟ · ·│· · · · · · ⍟ ·│
│· · · · · ⍟ · ·│· · ⍟ · · · · ·│· · · · · · · ⍟│⍟ · · · · · · ·│
│· · ⍟ · · · · ·│· · · · · · ⍟ ·│· · ⍟ · · · · ·│· · ⍟ · · · · ·│
│· · · · · · ⍟ ·│· · · ⍟ · · · ·│⍟ · · · · · · ·│· · · · · · · ⍟│
│· ⍟ · · · · · ·│· ⍟ · · · · · ·│· · · · · · ⍟ ·│· · · · · ⍟ · ·│
│· · · ⍟ · · · ·│· · · · ⍟ · · ·│· · · · ⍟ · · ·│· · · ⍟ · · · ·│
├───────────────┼───────────────┼───────────────┼───────────────┤
│· ⍟ · · · · · ·│· ⍟ · · · · · ·│· ⍟ · · · · · ·│· ⍟ · · · · · ·│
│· · · · ⍟ · · ·│· · · · · ⍟ · ·│· · · · · ⍟ · ·│· · · · · · ⍟ ·│
│· · · · · · ⍟ ·│⍟ · · · · · · ·│· · · · · · · ⍟│· · ⍟ · · · · ·│
│· · · ⍟ · · · ·│· · · · · · ⍟ ·│· · ⍟ · · · · ·│· · · · · ⍟ · ·│
│⍟ · · · · · · ·│· · · ⍟ · · · ·│⍟ · · · · · · ·│· · · · · · · ⍟│
│· · · · · · · ⍟│· · · · · · · ⍟│· · · ⍟ · · · ·│· · · · ⍟ · · ·│
│· · · · · ⍟ · ·│· · ⍟ · · · · ·│· · · · · · ⍟ ·│⍟ · · · · · · ·│
│· · ⍟ · · · · ·│· · · · ⍟ · · ·│· · · · ⍟ · · ·│· · · ⍟ · · · ·│
├───────────────┼───────────────┼───────────────┼───────────────┤
│· ⍟ · · · · · ·│· · ⍟ · · · · ·│· · ⍟ · · · · ·│· · ⍟ · · · · ·│
│· · · · · · ⍟ ·│· · · · ⍟ · · ·│· · · · ⍟ · · ·│· · · · · ⍟ · ·│
│· · · · ⍟ · · ·│· ⍟ · · · · · ·│· · · · · · · ⍟│· ⍟ · · · · · ·│
│· · · · · · · ⍟│· · · · · · · ⍟│· · · ⍟ · · · ·│· · · · ⍟ · · ·│
│⍟ · · · · · · ·│⍟ · · · · · · ·│⍟ · · · · · · ·│· · · · · · · ⍟│
│· · · ⍟ · · · ·│· · · · · · ⍟ ·│· · · · · · ⍟ ·│⍟ · · · · · · ·│
│· · · · · ⍟ · ·│· · · ⍟ · · · ·│· ⍟ · · · · · ·│· · · · · · ⍟ ·│
│· · ⍟ · · · · ·│· · · · · ⍟ · ·│· · · · · ⍟ · ·│· · · ⍟ · · · ·│
└───────────────┴───────────────┴───────────────┴───────────────┘
{⊃⍴queens ⍵}¨0 to 16 ⍝ Number of solutions for various boards.
0 1 0 0 1 2 1 6 12 46 92 341 1787 9233 45752 285053 1846955
See also: kt sudoku pmat queensX trav X
Back to: contents
Back to: Workspaces