Essays/9 Queens Problem

From J Wiki
Jump to: navigation, 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

Q9.jpg



See also


Contributed by Roger Hui.