# 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