Essays/9 Queens Problem
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.