Заполнение фигурами (перебор)

[Symbolist]

Задание таково: дано клеточное поле NxM (M и N не меньше 2 и не превосходят 20), в некоторых клетаках которого расположены черные клетки (не могут быть заполнены). Необходимо заполнить данное поле фигурами след. типа (различные повороты считаются различными фигурами, итого 8 фигур) и предоставить все возможные решения.
.__.
|__|__.
|__|__|
.________.
|__|__|__|
....|__|.....
Сам алгоритм перебора не доставляет трудностей, однако есть проблема с оптимизацией.
Каким образом стоит начинать заполнение (с некоторой фиксированной клетки - не вариант, т.к. может существовать область с черными клетками, для которой существует достаточно мало вариантов заполнения, что сократит перебор)? Возможно ли на как можно раннем этапе выполения программы узнать, что данное заполнение беспереспективно?
Буду благодарен даже за молейшую подсказку.