2 queen, $5\times 5$ chess board problem

245 Views Asked by At

Prove the following:
In $5\times 5$ chess board the least amount of queens you need in order to threaten on each square is 3.
(Square threat: the queens threatens on each square in the diagonals,row and column from the queens position).

I just need to show that you can't threaten the whole $5\times 5$ board with 2 queens.

2

There are 2 best solutions below

0
On

A case analysis is sufficient. Let the top left corner by black.

You need both a B queen and a W queen (we can see this by counting their max range of W and B).

If the W queen is on the boundary, then 3 W boundary squares remain to be covered and their position makes it impossible to be covered by a B queen.

If the W queen is not on the boundary, then 2 W squares on the same column must be covered by a B queen (which must be in that column) and now you can see that covering all B squares is not possible.

2
On

You can place at most 1 queen in the center, and then for symmetry of rotating and mirroring, you should have at least 1 queen on A1, A2, or B2.

Now allow that the other one can also be placed outside of the center.

Then a simple case analysis.. (Finding e.g. triplets that can't be covered)