Hint1: Consider the board colored alternating black and white (like a chessboard).