Breaking it down to the simplistic form of dominos, there's the classic puzzle of placing them a checkerboard with either two white or black squares missing. This is known to be impossible and left as an exercise for the reader =). But what if we're given a less uniform board. Is there any known algorithms other than brute-force to show there is a solution or to even solve the puzzle? We know there have to be an even number of square and an equal number of white and black squares, but that doesn't mean there is a solution.
Moving up in complexity, there's another classic problem of filling an $n \times n$ board with L-triominos except for one marked square. Recursive solutions exist here, but I've never seen anything for non-uniform board or allowing non-L blocks.
Finally we hit the Mosaic puzzle. What if we're given a set of tetris pieces and an irregular board? Can we easily determine if there's a solution? Is it easier if we aren't constrained by the number of each piece we can use?