Essays/4 Queens Problem

From J Wiki
Jump to: navigation, search

A problem was posed on the Wikipedia Eight Queens Problem discussion page: Can 4 queens cover (attack all squares of) the (8,8) chessboard?

Since there are only 4!8*8 or 635376 different placements of 4 queens on an (8,8) chessboard, it is feasible to do an exhaustive analysis of all possible placements. Thus:

comb=: 4 : 0
 k=. i.>:d=.y-x
 z=. (d$<i.0 0),<i.1 0
 for. i.x do. z=. k ,.&.> ,&.>/\. >:&.> z end.
 ; z
)

cov=: 3 : 0 " 2
 r=. ,(|:y){"_1 M
 d=. N#. (*./"1@(e.&(i.N)) # ]) ((#D)#y)+(y*&#D)$D
 I *./@e. r,d
)

qcover=: 4 : 0
 N=: y
 I=: i.N*N
 M=: (,: |:) i.N,N
 D=: 0 0 -.~ (,.~ , ] ,. |.)i: N-1
 (cov@((N,N)&#:) # ]) x comb N*N
)

x comb y finds all size-x combinations of i.y and is from the for. page of the dictionary.

cov y is 1 if and only if y covers the N,N chessboard, where y is a 2-column matrix of the row and column indices of the placement of the queens. Within cov , r are the squares covered by rectangular moves and d are those covered by diagonal moves.

x qcover y finds all solutions of covering the (y,y) chessboard using x queens.

The question is answered in the negative:

   $ 4 qcover 8
0 4

That is, it is not possible to cover the (8,8) chessboard with 4 queens.

We now exhibit all solutions of covering the (7,7) chessboard with 4 queens.

   $ t= 4 qcover 7
86 4

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

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

   u=: uvar <"0 ((i.7 7) e. ])&.> <"1 t
   $ u
13
   load 'viewmat'
   rgb=: 192,0,:255 0 0
   rgb&viewmat&> (2 <. (2|i.7 7) + 2 * ])&.> u

Essays 4q7.jpg



See also


Contributed by Roger Hui.