Auto comment: topic has been updated by Mitpro (previous revision, new revision, compare).

First of all, can you solve the problem for a complete square board of size $$$n*n$$$ (without any squares removed) ?
Then, to which types/shapes of boards (maybe not squares) can you transpose this approach ?
Finally, how to link these results with you problem input ?

convert the problem to a graph

use greedy (selecting two connected vertices and continuing with another one)

you might need to try the root for everyone

If there are an odd number of squares it's clearly impossible. Loop over all squares till you find a square $$$u$$$ with degree $$$d \lt 2$$$. If $$$d=0$$$ the square is blocked on all sides so clearly impossible. If $$$d=1$$$, if a solution exists it must have a domino at $$$s$$$ and it's neighbor. Adding this domino may cause other squares to have degree 1, so DFS squares adjacent to the added domino till all squares are degree > 1. If at any point we create surround a square on all sides or cause a self-intersection it's impossible.

If it's possible to DFS till all squares have degree $$$d \gt 1$$$, (I think) It's possible to tile the whole grid, so we're done.

I spent way too long trying to prove this fact. If anyone has a counterexample pls lmk

just build a bipartite graph with one part being the white cells and second part being the black cells, each domino covers 1 black and 1 white cell so if cntblack != cntwhite then answer is NO either way you run a maximum matching algorithm on this graph and print yes if maximum_matching == cnt_black (doesnt matter which since they are equal) and that is it. there is also a dp approach using profile dp