Полиномиальное решение времени для Tetris Puzzle

Это головоломка, основанная на Tetris. В этой головоломке нам даются последовательности следующих n частей, которые будут падать сверху. Наша задача - максимизировать счет до его GameOver. Не существует полиномиального алгоритма времени, известного для общего тетриса, но в этой головоломке допускаются только я (прямые) тетроминоны. Хотя его не разрешают вращать.

Итак, вот ограничения:

Плата представляет собой прямоугольник W x H
Нам даны последовательности следующих n тетроминонов
Разрешены только тетроминоны (горизонтальные или вертикальные)
Вращение ролика не разрешено
Строки очищаются по мере их заполнения.
Совет изначально пуст.
1 балл присваивается за очищенную строку.
Игра заканчивается, когда тетроминоны складываются вверху игрового поля.

Найдите максимальный результат, который можно получить.

Пример:

8 x 6 доска. Следующие 7 тетроминонов [——,|,|,——,|,——,|], где '——' представляет горизонтальный я tetramino и | представляет вертикальный я tetramino.

Максимально возможная оценка в этом случае равна 3, используя следующую стратегию ('.' представляет собой пустую доску, '#' представляет собой часть тетрамино).

Initially:
........
........
........
........
........
........
1st move:
........
........
........
........
........
####....
2nd Move:
........
........
.......#
.......#
.......#
####...#
3rd Move:
........
........
......##
......##
......##
####..##
4th Move:
........
........
......##
......##
####..##
####..##
5th Move:
........
........
.....###
.....###
####.###
####.###
6th Move:
........
........
.....###
####.###
####.###
####.###
7th Move:
........
........
....####
########
########
########  // bottom 3 rows are cleared so score is 3
final state:
........
........
........
........
........
....####

Даже лучший алгоритм, который я мог бы получить, занимает экспоненциальное время, когда я сохраняю состояние верхнего уровня текущей платы (то есть, насколько высок каждый столбец). Таким образом, этот алгоритм займет время O((H^W)*n), так как для каждого столбца есть H возможностей для высоты.

Можно ли это решить в полиномиальное время с помощью динамического программирования или какого-нибудь жадного алгоритма?

Ответ 1

Я попытаюсь угадать:

Плата представляет собой двоичную матрицу W x H.

Последовательности tetrominoes являются двоичной строкой s длины n, 1 для вертикальной, 0 для горизонтальной.

Попробуем проблему решения: если задана произвольная доска и произвольная последовательность s тетроминонов длины n, есть ли выигрышная последовательность перемещения?

На каждом шаге вы можете сделать не более W выбор: положение tetronmino.

Чтобы проверить, есть ли для заданной доски и последовательности тетроминонов выигрышная последовательность проверки перемещения CanWin (B (n)) со следующим алгоритмом:

 CanWin(B(i)):
   if Filled(B(i)) return false
   if (i == n and not Filled(B(i))) return true
   choose position in 0..W-1
   B(i+1) = UpdateBoard(Bi, s(i+1), position)
   return CanWin(B(i+1))

Вы можете проверить, заполняет ли доска O (W), проверяя верхнюю строку. Вы можете обновить плату, проверив коллизии в O (H). [Необходимо учитывать стирание строк] Затем вы можете решить, есть ли выигрышная последовательность в O (nW (H) ^ W).

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

Теперь алгоритм экспоненциальный, но вы можете memoized рекурсию с набором данных, размер которого не более 2 ^ (W x H + 1 ) x W.

С тех пор я не знаю, как подсчитать количество напоминаний.

Примечания:

В этой версии вы не можете вести тетромино во время падения сверху.
В рекурсии могут возникать циклы из-за стирания строки. Вы должны удалить это правило из своей проблемы.
Статья Тетрис жестко, даже приближенно догадывается в заключении, что тетрис с одним горизонтальным/вертикальным тетромином является полиномиальным временем.

Ответ 2

Я не могу понять, как это можно сделать быстрее, чем наихудший случай экспоненциального времени. Некоторые мысли:

Игра заканчивается, когда либо: n тетроминоны помещаются, либо помещаются тетроминоны выше уровня потери.

Решение может быть найдено быстрее экспоненциального времени. Поскольку единственный способ накопления очков - очистить строки, а так как он равен 1 точке на строку, независимо от того, сколько строк сразу очищается, могут существовать несколько решений. Если тетроминоны остаются на доске после размещения n тетроминонов, то не существует более высокого скоринга (возможно, при меньших ходах не будут отмечены бонусные баллы). В лучшем случае решение можно найти в линейном времени (место n тетромино), наихудший случай экспоненциальный.

Есть, очевидно, трюки или шаблоны, которые мы могли бы использовать, чтобы ускорить процесс. Например, если х число тетроминонов можно доказать, чтобы очистить доску, то если х делит n, мы имеем решение.