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

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

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

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

//картинки//

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

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

В исходном состоянии фигуры она имеет базовую ориентацию, ее позиция такова, что верхний ряд ее клеток содержится в ряду [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].

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

//stub//