俺も別件でちょっと前に必要があって
テトロミノによる敷き詰めを自動生成するコード書いたわ

１枚１枚敷き詰めていくと思うけど、その途中で
「今後どんなに工夫しても絶対敷き詰め出来ない」っていう状態になることが多いので
それをうまく検出して早々に巻き戻すことがポイントだったような記憶がある