Изменения

Перейти к: навигация, поиск

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

4003 байта добавлено, 00:11, 16 марта 2016
Добавлены игровые действия.
# ''ориентация'' — поворот на 0°, 90°, 180° или 270° по часовой стрелке относительно ''базовой ориентации'' фигуры (на илл. 1).
# ''позиция'' центра фигуры на поле, выбираемая из <tex>\{1,\dots,m\} \times \{1,\dots,n\}</tex>. Позицией SQ считается местоположение ее левой верхней клетки, так как ее центр лежит на границе четырех клеток, а не внутри одной.
# значение ''зафиксирована'' (англ. ''fixed'') или ''не зафиксирована''(англ. ''unfixed''), определяющее, может ли фигура продолжать двигаться.
В ''исходном'' состоянии фигуры она имеет базовую ориентацию, ее позиция такова, что верхний ряд ее клеток содержится в ряду <math>m</math>, а центр в столбце <math>\lfloor n/2 \rfloor</math>, и она не зафиксирована.
: '''Игровые действия'''.
Для фигуры <math>P=\langle t,o,\langle i,j \rangle , fixed \rangle.</math> допустимых действий нет. Для фигуры <math>P=\langle t,o,\langle i,j \rangle , unfixed \rangle.</stubmath> на данном игровом поле <math>B</math> допустимы следующие действия:# ''Поворот по часовой стрелке''. Новым состоянием фигуры будет <math>R(P,90^{\circ},B)</math>.# ''Поворот против часовой стрелки''. Новым состоянием фигуры будет <math>R(P,-90^{\circ},B)</math>.# ''Сдвиг влево''. Если клетки слева от фигуры свободны в <math>B</math>, фигура <math>P</math> может быть сдвинута влево на один столбец. Новым состоянием фигуры будет <math>\langle t,o,\langle i,j - 1 \rangle , unfixed \rangle.</math># ''Сдвиг вправо''. Аналогично сдвигу влево; новым состоянием будет <math>\langle t,o,\langle i,j + 1 \rangle , unfixed \rangle.</math># ''Снижение'' на один ряд, если все клетки под фигурой свободны в <math>B</math>. Новое состояние — <math>\langle t,o,\langle i - 1,j \rangle , unfixed \rangle.</math># ''Фиксация'', если хотя бы одна клетка под фигурой занята в <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>, определяемое следующим образом:# Новое поле <math>B'</math> — это поле <math>B</math> с заполненными клетками фигуры <math>P</math>.# Если фигура зафиксирована таким образом, что для некоторого горизонтального ряда <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> становится пустым. Фиксация одной фигуры может привести к освобождению более чем одного ряда.# Если исходное состояние следующей фигуры в <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>.
74
правки

Навигация