The 9 Queens Problem was posed by Wim Henk Bodlaender in 2004: On an 8-by-8 chessboard, place one pawn and 9 queens so that the queens do not attack each other. We find all solutions to this puzzle. The approach is a simpler version of the one used in the Queens and Knights problem.

```n    =: 8

MT   =: ' ' -.~ ' .qQP? qq??? Q?Q?? P??P? ?????'
MTy  =: (%:#MT){.MT
MTx  =: (##])MTy
merge=: MT {~ MTx&i.@[ + MTy&i.@]

UI   =: >,{;~i.n
QI   =: 0 0 -.~ (0&,. , ,.&0 , ,.~ , (,.|.)) i: n
mask =: 3 : 'UI e."2 UI +"1"1 2 y'
QT   =: '.Qq' {~ (=i.n*n)+2*mask QI

pp=: 4 : 0
if. '.'=y{x do. 'P' y}x  return. end.
if. 'Q'=y{x do. (\$x)\$'?' return. end.
'i j'=. (n,n)#:x i. 'Q'
'p q'=. (n,n)#:y
v=. i.n
if.     i=p do. '.' ((v=q) ];.(_2+j<q) v+n*i)} 'P' y}x
elseif. j=q do. '.' ((v=p) ];.(_2+i<p) j+n*v)} 'P' y}x
elseif. 1   do.
u=. n#.(#~ *./"1@(e.&v)) (p+i:n),.q+i:((i-j)=p-q){_1 1*n
'.' ((u=y) ];.(_2+i<p) u)} 'P' y}x
end.
)

init4=: 4 : 0
'i j'=. (n,n)#:y
r=. ((i.n) e. 0,j) <;.1 (n*i)+i.n
c=. ((i.n) e. 0,i) <;.1 j+n*i.n
(*./"1@('?'&~:) # ]) merge/"2 x {~ >,{(r,c)-.&.>y
)

qp=: 4 : 0
assert. 4<:x
assert. y e. i.*:n
qt=. QT pp"1 y
z=. qt init4 y
for_j. (-i.) x-4 do.
z=. ~.((+/"1 b)#z) merge qt {~ (n*n)|I.,b=. j (] *. (<:+/"1)) '.'=z
end.
)

see  =: ,~@%:@# \$ 'QP.' {~ 'QP' i. ]

var  =: ~.@(] , |:&.> , |.&.> , |."1&.>)^:3
uvar =: ~. @: ({.@(/:~)@var&>) @: (<@<@see"1)```

A config is an n*n (n=:8) element string recording the placement of queens (Q) and the pawn (P) together with the coverage, the squares under attack by queens already on the board. below is a config. Q indicates a square where a queen is placed, on row 2 and column 6. q indicates a square under attack. "." indicates a free square.

```   x=: '....q.q......qqqqqqqqqQq.....qqq....q.q....q..q...q...q..q....q.'
(n,n) \$ x
....q.q.
.....qqq
qqqqqqQq
.....qqq
....q.q.
...q..q.
..q...q.
.q....q.```

QT is an n*n row table of configs, one for each possible placement of a queen.  merge merges two configs.

```   \$ QT
64 64

(<n,n) \$&.> (22{QT) ; (49{QT) ; (22{QT) merge 49{QT
┌────────┬────────┬────────┐
│....q.q.│.q.....q│.q..q.qq│
│.....qqq│.q....q.│.q...qqq│
│qqqqqqQq│.q...q..│qqqqqqQq│
│.....qqq│.q..q...│.q..qqqq│
│....q.q.│.q.q....│.q.qq.q.│
│...q..q.│qqq.....│qqqq..q.│
│..q...q.│qQqqqqqq│qQqqqqqq│
│.q....q.│qqq.....│qqq...q.│
└────────┴────────┴────────┘```

x pp y puts a pawn in position y of x , a config with has exactly one queen, and produces the updated config.

x init4 y generates all initial "cross" configurations of 4 queens and a pawn on position y ,  given x of all configs with one queen and a pawn on position y .

```   qt=. QT pp"1 ] 11
\$ qt
64 64

(<n,n) \$&.> (9{QT) ; 9{qt
┌────────┬────────┐
│qqq.....│qqq.....│
│qQqqqqqq│qQqP....│
│qqq.....│qqq.....│
│.q.q....│.q.q....│
│.q..q...│.q..q...│
│.q...q..│.q...q..│
│.q....q.│.q....q.│
│.q.....q│.q.....q│
└────────┴────────┘

z=. qt init4 11
\$ z
26 64
8 8 \$ 0{z
qqqQqqqq
QqqPqQqq
qqqQqqqq
q.qqqqqq
qqqq.q.q
qq.qqqq.
q..q.q.q
q..q.qq.

see&.> <"1 ]8{.z
┌────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┐
│...Q....│...Q....│...Q....│...Q....│...Q....│...Q....│...Q....│...Q....│
│Q..P.Q..│Q..P.Q..│Q..P.Q..│Q..P.Q..│Q..P..Q.│Q..P..Q.│Q..P..Q.│Q..P..Q.│
│...Q....│........│........│........│...Q....│........│........│........│
│........│........│........│........│........│...Q....│........│........│
│........│........│........│........│........│........│........│........│
│........│...Q....│........│........│........│........│...Q....│........│
│........│........│...Q....│........│........│........│........│...Q....│
│........│........│........│...Q....│........│........│........│........│
└────────┴────────┴────────┴────────┴────────┴────────┴────────┴────────┘```

x qp y finds all solutions of placing x queens on a board with one pawn in position y .

We need only consider pawn placements in the upper left quadrant (the others being obtainable by reflections and rotations); of those, only the positions in the upper triangle need to be considered. Moreover, a pawn must be positioned so that queens can be placed on either side of it on the same row and on the same column. Thus:

```   i.8 8
0  1  2  3  4  5  6  7
8  9 10 11 12 13 14 15
16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63

t=: 9 qp&.> 10 11 18 19 27
#&> t
2 4 6 2 10
\$ r=: ; t
24 64

see 0{r
..Q.....
Q.P....Q
...Q....
......Q.
..Q.....
.....Q..
.Q......
....Q...```

var and uvar from the Queens and Knights page are used to suppress rotational and reflectional variants.

```   u=: uvar r
\$ u
16