Exact cover N-Queens
--------------------
The N-Queens puzzle may be expressed and solved as an exact cover problem:
queensX←{ ⍝ Exact cover N-Queens.
m←⍳3/⍵ ⍝ cell coordinate properties.
r←=/¨1 0 1∘/¨m ⍝ each rank must contain one queen.
f←=/¨0 1 1∘/¨m ⍝ .. file .. .. ..
dm←-/¨⍳2/⍵ ⍝ diagonal labels.
du←{⍵[⍋⍵]}∪,dm ⍝ unique labels.
y←⊖x←dm∘.=du ⍝ x and y diagonals.
m←,[⍳2]x,y,r,f ⍝ constraints matrix.
d←~(⍳1↓⍴m)∊⍳2×⍴du ⍝ mask of required cols.
⍵ ⍵⍴d X m ⍝ exact cover - matrix of queens.
}
⍝ A solution for each of the first 9 N-Queens problems:
queensX¨ 0 to 8
┌┬─┬───┬─────┬───────┬─────────┬───────────┬─────────────┬───────────────┐
││1│0 0│0 0 0│0 1 0 0│0 0 0 0 1│0 0 0 0 1 0│0 0 0 0 0 0 1│0 0 0 0 0 0 0 1│
││ │0 0│0 0 0│0 0 0 1│0 1 0 0 0│0 0 1 0 0 0│0 0 0 0 1 0 0│0 0 0 1 0 0 0 0│
││ │ │0 0 0│1 0 0 0│0 0 0 1 0│1 0 0 0 0 0│0 0 1 0 0 0 0│1 0 0 0 0 0 0 0│
││ │ │ │0 0 1 0│1 0 0 0 0│0 0 0 0 0 1│1 0 0 0 0 0 0│0 0 1 0 0 0 0 0│
││ │ │ │ │0 0 1 0 0│0 0 0 1 0 0│0 0 0 0 0 1 0│0 0 0 0 0 1 0 0│
││ │ │ │ │ │0 1 0 0 0 0│0 0 0 1 0 0 0│0 1 0 0 0 0 0 0│
││ │ │ │ │ │ │0 1 0 0 0 0 0│0 0 0 0 0 0 1 0│
││ │ │ │ │ │ │ │0 0 0 0 1 0 0 0│
└┴─┴───┴─────┴───────┴─────────┴───────────┴─────────────┴───────────────┘
Technical notes:
Function [queensX] constructs a boolean constraint matrix m, in which the col-
mums representing diagonals are optional. As an example, the final constraints
matrix for the inner function for a 4-Queens problem has these regions:
┌───────────────────────────────────── x-diagonal requirements
│ ┌─────────────────────── y-diagonal .. ..
│ │ ┌──────────── rank (row) .. ..
│ │ │ ┌──── file (col) .. ..
│ │ │ │
┌─────────────┬─────────────┬───────┬───────┐
│0 0 0 1 0 0 0│0 0 0 0 0 0 1│1 0 0 0│1 0 0 0│
│0 0 1 0 0 0 0│0 0 0 0 0 1 0│1 0 0 0│0 1 0 0│
│0 1 0 0 0 0 0│0 0 0 0 1 0 0│1 0 0 0│0 0 1 0│
│1 0 0 0 0 0 0│0 0 0 1 0 0 0│1 0 0 0│0 0 0 1│
│0 0 0 0 1 0 0│0 0 0 0 0 1 0│0 1 0 0│1 0 0 0│
│0 0 0 1 0 0 0│0 0 0 0 1 0 0│0 1 0 0│0 1 0 0│
│0 0 1 0 0 0 0│0 0 0 1 0 0 0│0 1 0 0│0 0 1 0│
│0 1 0 0 0 0 0│0 0 1 0 0 0 0│0 1 0 0│0 0 0 1│
│0 0 0 0 0 1 0│0 0 0 0 1 0 0│0 0 1 0│1 0 0 0│
│0 0 0 0 1 0 0│0 0 0 1 0 0 0│0 0 1 0│0 1 0 0│
│0 0 0 1 0 0 0│0 0 1 0 0 0 0│0 0 1 0│0 0 1 0│
│0 0 1 0 0 0 0│0 1 0 0 0 0 0│0 0 1 0│0 0 0 1│
│0 0 0 0 0 0 1│0 0 0 1 0 0 0│0 0 0 1│1 0 0 0│
│0 0 0 0 0 1 0│0 0 1 0 0 0 0│0 0 0 1│0 1 0 0│
│0 0 0 0 1 0 0│0 1 0 0 0 0 0│0 0 0 1│0 0 1 0│
│0 0 0 1 0 0 0│1 0 0 0 0 0 0│0 0 0 1│0 0 0 1│
├─────────────┴─────────────┼───────┴───────┤
│1 0 0 0 0 0 0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│
│0 1 0 0 0 0 0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│
│0 0 1 0 0 0 0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│
│0 0 0 1 0 0 0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│
│0 0 0 0 1 0 0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│
│0 0 0 0 0 1 0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│
│0 0 0 0 0 0 1 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│
│0 0 0 0 0 0 0 1 0 0 0 0 0 0│0 0 0 0 0 0 0 0│
│0 0 0 0 0 0 0 0 1 0 0 0 0 0│0 0 0 0 0 0 0 0│
│0 0 0 0 0 0 0 0 0 1 0 0 0 0│0 0 0 0 0 0 0 0│
│0 0 0 0 0 0 0 0 0 0 1 0 0 0│0 0 0 0 0 0 0 0│
│0 0 0 0 0 0 0 0 0 0 0 1 0 0│0 0 0 0 0 0 0 0│
│0 0 0 0 0 0 0 0 0 0 0 0 1 0│0 0 0 0 0 0 0 0│
│0 0 0 0 0 0 0 0 0 0 0 0 0 1│0 0 0 0 0 0 0 0│
└───────────────────────────┴───────────────┘
│ │
│ └──────── padding for required reqts.
└────────────────────────────── dummy rows for optional reqts.
See also: X queens
Back to: contents
Back to: Workspaces