RodionGork's blog

By RodionGork, 10 years ago, In Russian

Уважаемые гуру, привет!

Есть популярная игрушка, для которой "популярного" названия я не знаю — видел её как "Color Cubes", "Brick Breaker", "Cube Crasher". Вот онлайновый пример.

Судь такая — прямоугольное поле, скажем, 20*30 заполняется квадратами 4 или 5 цветов. За каждый ход можно снимать группы квадратов одного цвета. Группой считаются соседствующие (по стороне) квадраты, т.е.:

1 2 1 1 1
2 2 1 3 3
3 2 2 1 1

Здесь есть одна группа цвета 2 из 5 квадратов и 3 группы цвета 1, из 4, 2 и 1 квадрата.

За снятые группы начисляются очки — причём обычно гораздо выгоднее снимать большие группы — впрочем прогрессия варьируется обычно вместе с правилами, например она может расти как N^2 или 2^N-1.

В некоторых вариантах снимать группы из 1 кубика нельзя, в некоторых даже из 2. В некоторых за это штраф и т.п.

Заинтересовал вопрос — есть ли алгоритмическое решение которое позволяет для заданной начальной ситуации определить последовательность ходов, ведущей к максимально возможному результату (или сам максимальный результат)?

Или же с ростом размеров поля только эвристические решения возможны, неоптимальные?

Допускаю что это может зависеть от варианта правил, в частности от прогрессии очков.

В общем, подскажите если кто-то встречался, пожалуйста!

  • Vote: I like it
  • +8
  • Vote: I do not like it