Изменения

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

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

427 байт добавлено, 01:56, 25 марта 2016
м
Нет описания правки
: '''Игровое поле''' — расчерченный на клетки прямоугольник размером <tex>m</tex> горизонтальных рядов (строк) на <tex>n</tex> вертикальных (столбцов). Примем следующую индексацию: снизу вверх и слева направо. <math>\langle i, j \rangle</math>-я клетка либо ''свободна'', либо ''занята''. В допустимом состоянии поля ни один горизонтальный ряд не заполнен целиком и нет ни одной полностью пустой строки, которая бы лежала ниже занятой клетки. При оценке допустимости некоторых действий будем считать, что все клетки вне игрового поля всегда заняты и тем самым ограничивают поле.
//картинки//{| cellpadding="3" style="margin-left: auto; margin-right: auto;"| [[Файл:SQ.png|50px|thumb|right| SQ]]| [[Файл:LG.png|50px|thumb|right| SQ]]| [[Файл:RG.png|50px|thumb|right| SQ]]| [[Файл:LS.png|50px|thumb|right| SQ]]| [[Файл:RS.png|50px|thumb|right| SQ]]| [[Файл:I.png|50px|thumb|right| SQ]]| [[Файл:T.png|50px|thumb|right| SQ]]|} 
: '''Игровые фигуры''' — семь различных фигур, получаемых соединением четырех единичных клеток по каким-либо из сторон. Каждая фигура имеет ''центр'' (на илл. 2). ''Состояние фигуры'' <math>P</math> — кортеж из четырех элементов, а именно:
# ''тип фигуры'' — SQ(''square''), LG(''left gun''), RG(''right gun''), LS(''left snake''), RS(''right snake''), I или T.
# ''ориентация'' — поворот на 0°, 90°, 180° или 270° по часовой стрелке относительно ''базовой ориентации'' фигуры (на илл. 1).
# ''позиция'' центра фигуры на поле, выбираемая из <tex>\{1,\dots,m\} \times \{1,\dots,n\}</tex>. Позицией SQ считается местоположение ее левой верхней клетки, так как ее центр лежит на границе четырех клеток, а не внутри одной.
74
правки

Навигация