Почему это прямолинейный подход не сработает? Ещё как сработает, если мы за скоростью не гонимся.
Тупо помещать 3 фигурки в каждую клетку в 4-х ориентациях и проверять, что вылезает, а что накладывается.

(40*4)^3 вариантов размещений, на каждую 7*3 проверок, всего 86 016 000 операций.
Ну пусть каждая проверка это 20 инструкций и инструкции не всегда по одному такту
При тактовой частоте 3 гигагерца — это 1760 / 3000 секунд, т.е. меньше секунды.