What is the largest square you can paint onto a chess board such that you can still place five queens all on unpainted squares where all 64 squares are attacked?

Ans: Square of 5*5

If i were to name the squares similar to cartesian coordinates (x,y):

(1,1) - top left

(8,8) - bottom right

then putting 4 queens in (4,1), (8,4), (5,8), (1,5) and the fifth queen in any position of the following: (2,2), (7,2), (7,7) or (2,7) we can get a square of 5*5

So the solution is a square of 5*5.

-Abhishek.