Problem : You are given a NxN matrix and consider if a pair of cells is removed from the square matrix and then if we are able to cover remaining cells of the matrix by a 1x2 tile placing it either horizontally or vertically then the pair of cell removed is called GoodPair.

Problem link : https://www.codechef.com/LOGI2020/problems/CHEFG999

Solution : The given square matrix can be visualised as a NxN chessboard with cells of black and white colour. So we can say that if one pair of cell with opposite colours is removed then only the solution is possible. (As domino tiling matches one black cell with one white cell or vice versa).

I understand that we need to remove cells with different parity of (i+j), but is it ALWAYS possible? Can someone explain the proof of it or provide a constructive approach to lay out the tiles?