LINUX.ORG.RU

Пентамино

 , , ,


0

1

Прислали мне тестовое, скорее всего, не сделаю, но интересно стало. Не могу найти информацию по алгоритму поиска решения головоломки пентамино - на вход поступает законченная фигура в виде текстового файла из нолей и единиц, на выходе нужно разбить эту фигуру на части заданными деталями. В общих чертах, кажется, нужно следующее: сделать рекурсию до тех пор, пока неразбитая часть не равна одной из элементарных фигур, а если она не равна, то, начиная с, допустим, левого верхнего угла подставлять любую фигуру, затем: если она не подходит, переходим к следующей, если подходит, начинаем разбивать то, что получилось в результате. Если в конце концов получается фигура, не соответствующая ни одной из элементарных, идем на шаг назад и ставим другую фигуру(нужно хранить id фигуры, примененной на прошлом шаге - т.к. рекурсия, можно хоть до первого шага подняться). Только кажется, что такой перебор с возвратом может никогда не найти нужное решение. Кажется, должен быть стандартный алгоритм, который нужно адаптировать к этому случаю. Никто не знает, какой?

★★★★

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

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

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

i-rinat ★★★★★ ()
Последнее исправление: i-rinat (всего исправлений: 1 )
Ответ на: комментарий от i-rinat

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

wingear ★★★★ ()
Ответ на: комментарий от wingear

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

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

i-rinat ★★★★★ ()
Ответ на: комментарий от trashymichael

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

wingear ★★★★ ()
Ответ на: комментарий от i-rinat

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

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}
};
Потом в конструкторе из неё делаются повороты и отражения, а еще я придумал метод, принимающий координату, на которой мы «сейчас» и - по ссылке, чтобы можно было прямо там фигуру «начертить», основной массив - только вот что в этом методе делать, не пойму: расположить все фигуры в матрице так, чтобы они касались какого-то из её углов, и, исходя из этого, брать нужное «направление» и «накладывать»(тоже пока не представляю, как) матрицу фигуры на основной массив?

wingear ★★★★ ()
Ответ на: комментарий от wingear

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

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

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

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

i-rinat ★★★★★ ()
Ответ на: комментарий от i-rinat

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

wingear ★★★★ ()
Ответ на: комментарий от i-rinat

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

wingear ★★★★ ()
Ответ на: комментарий от wingear

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

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

i-rinat ★★★★★ ()
4 ноября 2013 г.

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

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

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

qulinxao ★★☆ ()

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

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.