There is an extremely elegant solution to this modified question as well. In fact, it is always possible to fill a chessboard with dominoes with two squares of opposite color removed, by a very straightforward method (Gomory's Theorem). See Problem 2 at https://www.cut-the-knot.org/do_you_know/chessboard.shtml and note that the result generalizes to any bipartite Hamiltonian graph, such as any rectangular grid with an even number of cells.

(Much more generally, Hall's marriage theorem characterizes which finite bipartite graphs have a perfect matching, and there are polynomial-time algorithms to compute maximum cardinality matchings in arbitrary finite graphs.)