Пентамино

У Кнута вроде было общее решение для таких проблем http://www-cs-faculty.stanford.edu/~knuth/papers/dancing.tex.gz

Решение найдётся, но долго.
http://search.cpan.org/~dami/Games-Pentominos-1.0/lib/Games/Pentominos.pm
Так вроде быстро разное гуглится.

Предварительно для всех фигур создать все возможные повороты и отражения.

Перебирать все пустые ячейки столбцами сверху вниз, слева направо. Для каждой ячейки перебирать фигуры. Если получилось, то рекурсия.

Задача «собрать все элементы в прямоугольник» решается относительно быстро даже на 386-м (40 МГц).

Там не прямоугольник, а произвольная фигура, про которую предполагается только то, что её можно заполнить - она поступает на вход программы

а где такое тестовое?

не прямоугольник, а произвольная фигура

Берёшь прямоугольник, покрывающий фигуру, и добавляешь условие «являющийся частью фигуры» к «все пустые ячейки».

да в одной фирме, которая занимается играми - самостоятельно ничего в этой области не получается, возможно, потому, что хочу сразу 3d, но не хочу unity. Может, и выйдет что, а то админство или php надоели уже совсем

Что-то не пойму - сейчас сделал класс фигуры, который инициализируется матрицей вроде

int FIG0[5][5]=
{
  {1,1,1,1,0},
  {0,0,1,0,0},
  {0,0,0,0,0},
  {0,0,0,0,0},
  {0,0,0,0,0}
};

Потом в конструкторе из неё делаются повороты и отражения

А я тупо вручную все координаты вбил (некоторые были отрицательные). (0,0) у фигуры у меня всегда был занят.

«накладывать»(тоже пока не представляю, как)

сопоставляешь со сдвигом. Если все единички ложатся на пустые места, фигура подошла, двигаешься дальше.

Не пойму, как правильно - в одном случае не находит решения, хотя оно есть, в другом уходит в бесконечный цикл. Есть структура данных, в которой хранится лог того, что делали с каждой ячейкой - четырехмерный массив bool(x,y, номер фигуры, номер поворота), значение определяет, пытались в данную ячейку поставить эту фигуру с таким поворотом или нет. Если в какой-то из ячеек не нашли решений, то отходим на последнюю ячейку, с которой что-то делали, и убираем оттуда фигуру. Не пойму, нужно ли я этом случае помечать все ячейки, связанные с этой фигурой, как доступные - если их освобождать, то уходит в бесконечный цикл(кажется - через несколько минут по кругу начинают идти несколько повторяющихся вариантов), а если не освобождать, то выдается результат «решений нет», хотя они есть. Видимо, нужно освобождать при каком-то условии, только не пойму, при каком

Сделай рекурсией.

Но ведь в данном случае это не имеет значения - проблема с возвратом, а не с обходом. Сейчас происходит следующее: для каждой ячейки поля её в память записываются все попытки вставить фигуру и разворот. Если эта фигура уже есть на поле, соответствующая ячейка памяти просто проскакивается. Если потом выяснилось, что нужно идти назад, память обнуляется, ищется предыдущая ячейка, в которой что-то делали с полем, действие откатывается, потом проверяется, все ли варианты для данной ячейки уже были испробованы - если все, то память тоже обнуляется и продолжается ход назад, а вот если не все, то новый цикл начинается с проблемной ячейки и первой фигуры, которую еще не пробовали установить на ней. Если память заканчивается в самой первой ячейке, то работа программы заканчивается с результатом «нет решений». Не вижу здесь ошибки, но это не работает: не видит решений, даже если они есть:(

Я тоже не вижу ошибки в описании. Возможно проблема в той части, которая «кладёт» фигуру на поле.

С рекурсией проще, потому что ты формулируешь «контракт»: что должно быть на входе, что на выходе. Если ты можешь доказать/показать корректность этой функции, твоя программа автоматически становится корректной. А уже работающий рекурсивный алгоритм потом разматываешь в цикл.

у тебя не хватает отсечений поэтому долго.

отсечение например такое - при вставки (при поиске в глубину рекурсией перебором)- пустая область обязана быть односвязной - без этого ты перебираеш(тратиш время) на заведомо нерешаемые(например когда одна из областей оказывается одной клеткой)

правильно!!! запрограммированный перебор через поиск в глубину обязан находить решение если оно существует.

регулярные выражения не пробовал?