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
- N Queens Problem
- 4 Queens Problem
- 9 Queens Problem
- Queens and Knights
- Knight's Tour
Contributed by Roger Hui.