# Essays/9 Queens Problem

Jump to navigation Jump to search

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. x 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
load 'viewmat'
rgb=: 192,0,255 0 0,: 255 255 0
rgb&viewmat&> (0 1 2 2 3 3 {~ (~:/~8\$0 1) + '..QQP' i. ])&.> u
```

See also

Contributed by Roger Hui.