Essays/4 Queens Problem
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
See also
Contributed by Roger Hui.