Colour all the cells one of two colours (or, shade some cells but not others), such that:
No 2x2 block of cells can show a checkerboard pattern
The border cells cannot be split into four (or more) separate blocks of colours
It is therefore either split into two blocks (one of each colour), or is just a single block of one colour or the other
If the grid has an odd side length (e.g. 9x9):
The number of edge cells of each colour is odd (if the border cells are not all the same colour)
If the grid has both side lengths even (e.g. 8x8):
The border must split into two colours;
the edge cells can be split into dominoes - the border must split between dominoes (all dominoes are wholly one colour or the other).