[перепроведении это от math.stackexchange]Нахождение максимальное количество баллов в «пузырь поп» игра
Рассмотрим следующую игру: есть N × N поле, где каждая ячейка случайным образом окрашены в одном из m цветов. Пусть a группа ячеек представляет собой набор однотипных клеток s.t. каждая ячейка в группе имеет по крайней мере один общий край с другой ячейкой с одним цветом. Группа s≥k может быть «выскочена», то есть удалена из поля, и игроку присваивается оценка для нее. Когда группа удаляется, остальные ячейки смещаются s.t. ни одна клетка не содержит под ним пустую ячейку (в основном, остальные ячейки «падают»). Если столбец исчезает в результате всплытия, каждый непустой столбец слева от него смещается на одну ячейку вправо. Игра заканчивается, когда на поле нет групп. Счет является функцией s, и в итоге вычисляется совокупный балл. Цель игры - получить максимальный кумулятивный балл.
Вопрос в том, есть ли алгоритм, позволяющий рассчитать максимально возможный конечный балл для заданного начального расположения ячеек? Я подозреваю, что это связано с поиском графа, но у меня мало опыта в таких вещах. Кто-нибудь может предложить, как можно подойти к такой проблеме? Я также думал о том, чтобы что-то делать с клеточными автоматами, но я действительно сомневаюсь в этом подходе (как бы забавно это ни было).