NP-полнота игры Тетрис

Тетрис — популярная игра, созданная в середине 1980-х математиком Алексеем Пажитновым.

Формальные правила

Игровое поле — расчерченный на клетки прямоугольник размером [math]m[/math] горизонтальных рядов (строк) на [math]n[/math] вертикальных (столбцов). Примем следующую индексацию: снизу вверх и слева направо. [math]\langle i, j \rangle[/math]-я клетка либо свободна, либо занята. В допустимом состоянии поля ни один горизонтальный ряд не заполнен целиком и нет ни одной полностью пустой строки, которая бы лежала ниже занятой клетки. При оценке допустимости некоторых действий будем считать, что все клетки вне игрового поля всегда заняты и тем самым ограничивают поле.

SQ

LG

RG

LS

RS

I

T

Игровые фигуры — семь различных фигур, получаемых соединением четырех единичных клеток по каким-либо из сторон. Каждая фигура имеет центр (на илл. 2). Состояние фигуры [math]P[/math] — кортеж из четырех элементов, а именно:

1. тип фигуры — SQ (square), LG (left gun), RG (right gun), LS (left snake), RS (right snake), I или T.
2. ориентация — поворот на 0°, 90°, 180° или 270° по часовой стрелке относительно базовой ориентации фигуры (на илл. 1).
3. позиция центра фигуры на поле, выбираемая из [math]\{1,\dots,m\} \times \{1,\dots,n\}[/math]. Позицией SQ считается местоположение ее левой верхней клетки, так как ее центр лежит на границе четырех клеток, а не внутри одной.
4. значение зафиксирована (англ. fixed) или не зафиксирована (англ. unfixed), определяющее, может ли фигура продолжать двигаться.

В исходном состоянии фигуры она имеет базовую ориентацию, ее позиция такова, что верхний ряд ее клеток содержится в ряду [math]m[/math], а центр в столбце [math]\lfloor n/2 \rfloor[/math], и она не зафиксирована.

Поворот фигуры. Модель поворота — функция [math]R : \langle P,\theta,B \rangle \mapsto P'[/math], где [math]P[/math] и [math]P'[/math] — состояния фигуры, [math]\theta \in \{-90^{\circ},90^{\circ}\}[/math] — угол поворота, а [math]B[/math] — игровое поле. На [math]R[/math] налагаются следующие условия:

1. Если [math]P = \langle t,o,\langle i,j \rangle,f\rangle[/math] и поворот допустим, то [math]P' = \langle t,(o + \theta) \mod 360^{\circ},\langle i',j' \rangle,f\rangle[/math] для некоторых [math]i'[/math] и [math]j'[/math]. Если поворот недопустим, то [math]P' = P[/math].
2. При определении допустимости поворота, [math]R[/math] рассматривает окрестность констатного размера у фигуры [math]P[/math] — то есть, только клетки на заданном расстоянии от позиции [math]P[/math] влияют на [math]R[/math], а положение фигуры на игровом поле значения не имеет.
3. Если все клетки в окрестности [math]P[/math] свободны, то поворот допустим.
4. Если поворот допустим, то [math]P'[/math] не занимает ни одной клетки, уже занятой в [math]B[/math].

Игровые действия.

Для фигуры [math]P=\langle t,o,\langle i,j \rangle , fixed \rangle.[/math] допустимых действий нет. Для фигуры [math]P=\langle t,o,\langle i,j \rangle , unfixed \rangle.[/math] на данном игровом поле [math]B[/math] допустимы следующие действия:

1. Поворот по часовой стрелке. Новым состоянием фигуры будет [math]R(P,90^{\circ},B)[/math].
2. Поворот против часовой стрелки. Новым состоянием фигуры будет [math]R(P,-90^{\circ},B)[/math].
3. Сдвиг влево. Если клетки слева от фигуры свободны в [math]B[/math], фигура [math]P[/math] может быть сдвинута влево на один столбец. Новым состоянием фигуры будет [math]\langle t,o,\langle i,j - 1 \rangle , unfixed \rangle.[/math]
4. Сдвиг вправо. Аналогично сдвигу влево; новым состоянием будет [math]\langle t,o,\langle i,j + 1 \rangle , unfixed \rangle.[/math]
5. Снижение на один ряд, если все клетки под фигурой свободны в [math]B[/math]. Новое состояние — [math]\langle t,o,\langle i - 1,j \rangle , unfixed \rangle.[/math]
6. Фиксация, если хотя бы одна клетка под фигурой занята в [math]B[/math]. Новое состояние — [math]\langle t,o,\langle i,j \rangle , fixed \rangle.[/math]

Траекторией [math]\sigma[/math] фигуры [math]P[/math] называется последовательность допустимых действий, начинающихся в исходном состоянии и заканчивающихся действием-фиксацией. Результатом траектории фигуры [math]P[/math] на игровом поле [math]B[/math] является новое поле [math]B'[/math], определяемое следующим образом:

1. Новое поле [math]B'[/math] — это поле [math]B[/math] с заполненными клетками фигуры [math]P[/math].
2. Если фигура зафиксирована таким образом, что для некоторого горизонтального ряда [math]r[/math] каждая клетка [math]r[/math] в поле [math]B'[/math] заполнена, то ряд [math]r[/math] освобождается. Для всех [math]r' \geqslant r[/math] следует заменить ряд [math]r'[/math] в [math]B'[/math] рядом [math]r'+1[/math] в [math]B'[/math]. Ряд [math]m[/math] в [math]B'[/math] становится пустым. Фиксация одной фигуры может привести к освобождению более чем одного ряда.
3. Если исходное состояние следующей фигуры в [math]B'[/math] заблокировано, игра заканчивается (игрок проигрывает).

Для игры [math]\langle B_0,P_1,\dots,P_p \rangle[/math], последовательностью траекторий [math]\Sigma[/math] является такая последовательность [math] B_0,\sigma_1,B_1,\dots,\sigma_p,B_p[/math], что для любого [math]i[/math] траектория фигуры [math]P_i[/math] на поле [math]B_{i-1}[/math] приводит к полю [math]B_i[/math]. Однако, если существует действие [math]\sigma_q[/math] при некотором [math]q \leqslant p[/math], приводящее к проигрышу, то последовательность [math]\Sigma[/math] завершается на [math]B_q[/math], а не на [math]B_p[/math].

NP-полнота игры

Рассмотрим следующую проблему, называемую k-cleared rows ([math]G,\Sigma[/math]): в игре [math]G[/math], приводит ли [math]\Sigma[/math] к освобождению хотя бы [math]k[/math] рядов до проигрыша? Вспомним проблему 3-Partition, которая является NP-полной. Она звучит так: можно ли разбить заданное мультимножество целых чисел на тройки чисел так, чтобы у всех троек сумма была одинакова?

Теорема:

3-Partition сводится к k-cleared rows.