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.