производительность — Block Puzzle, решающий алгоритм C ++

Я хочу сделать алгоритм для решения Блок пазлы, но максимально эффективно. Я уже сделал легкий путь (отступление).

Я представлял все в виде матриц — большая матрица, которой должны соответствовать кусочки, — все в 0, в начале, и кусочки — это матрицы с 1, если пространство заполнено, или 0, если пространство пусто.
Теперь следующая возможная более эффективная идея — всегда проверять, завершена ли строка, прежде чем перейти к следующей. Я имею в виду, что у меня может быть кусок, представленный как
0 1 0
1 1 1
0 1 0
(крест). Если крестик будет помещен в угол, программа будет бесполезно выполнять полный возврат к неверному решению, поэтому она должна вернуться и попробовать другой фрагмент.

Я могу предоставить кусок кода, если обязательно, как я уже сказал, я сделал только простой неэффективный возврат.
У кого-нибудь есть идеи получше? Может ли в этом случае использоваться динамическое программирование?