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