1632
правки
Изменения
м
rollbackEdits.php mass rollback
{| cellpadding="3" style="margin-left: auto; margin-right: auto;"
| [[Файл:SQ.png|50px|thumb|right| SQ]]
| [[Файл:LG.png|50px|thumb|right| SQLG]]| [[Файл:RG.png|50px|thumb|right| SQRG]]| [[Файл:LS.png|50px|thumb|right| SQLS]]| [[Файл:RS.png|50px|thumb|right| SQRS]]| [[Файл:I.png|50px|thumb|right| SQI]]| [[Файл:T.png|50px|thumb|right| SQT]]
|}
Для ''игры'' <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-полной. Формальное ее условие таково: ввод — последовательность целых чисел <math>a_1,a_2,\dots,a_{3s}</math> и неотрицательное число <math>T</math> такое, что <math>T/4 < a_i < T/2</math> для всех <math>1\leqslant i \leqslant 3s</math>, <tex>\sum_{i=1}^{3s} a_i = sT</tex>; вывод — можно ли <math>\{a_1,\dots,a_{3s}\}</math> разбить на <math>s</math> непересекающихся подмножеств <math>A_1,\dots,A_s</math> так, что для всех <math>1\leqslant j \leqslant s</math> выполняется <tex>\sum_{a_i \in A_j} a_i = T</tex>.
{{Теорема
|statement=
3-Partition сводится к k-cleared rows.
|proof=
Опишем отображение из 3-Partition в k-cleared-rows. Для заданного ввода 3-Partition <math>P = \langle a_1,\dots,a_{3s},T \rangle</math>, составим игру <math>G(P)</math>, поле которой может быть полностью очищено, только если для <math>P</math> в задаче 3-Partition ответ положительный.
[[Файл:board_partition.png|300px|thumb|right| Начальное игровое поле]]
Начальное игровое поле содержит <math>s</math> ''контейнеров'', соответствующих множествам <math>A_1,\dots,A_s</math> в задаче 3-Partition. Последовательность фигур состоит из некоторого числа фигур, соответствующих каждому из <math>a_i</math> и подобранных так, что все фигуры для <math>a_i</math> должны быть помещены в один и тот же контейнер. Существует подходящее решение задачи 3-Partition для <math>\{a_1,\dots,a_{3s}\}</math> в том и только том случае, когда наборы фигур во всех контейнерах имеют одинаковую высоту. Последние три столбца в игровом поле представляют собой ''стопор'', который не дает очистить ряды, пока не подойдет к концу последовательность фигур; если все контейнеры заполнены на одинаковую высоту, то все поле может быть очищено с помощью последней (завершающей) части последовательности.
Игра <math>G</math> состоит из следующих компонент:
: '''Начальное игровое поле.''' Поле имеет <math>6T + 22 + (3s + O(1))</math> строк и <math>6s + 3</math> столбцов. Каждое <math>a_i</math> будет представлено <math>a_i + 1</math> блоками размером <math>6 \times 6 </math>; так как сумма элементов <math>A_j = \{a_i,a_j,a_k\}</math> равна <math>T</math>, получаем <math>6(T+3)=6T+18</math>. В дополнение к этим <math>6T+18</math> рядам, внизу находятся четыре ряда, обеспечивающие корректное положение блокам.
Верхние <math>3s+O(1)</math> рядов (<math>O(1)</math> — это размер окрестности в модели вращения) изначально пусты и представляют собой промежуточную зону, где фигуру можно вращать и двигать, прежде чем она попадет в нижние <math>6T+22</math> рядов. Остальная часть поля может быть логически разделена на <math>s+1</math> части, где первые <math>s</math> частей имеют шесть клеток в ширину, а последняя — три клетки в ширину. Первые <math>s</math> частей — это контейнеры, имеющие следующий вид:
# В первом и втором столбцах пусты все клетки, кроме нижних четырех.
# Третий столбец не имеет занятых клеток.
# В четвертом и пятом столбцах пусты только клетки в тех строках, чей номер по модулю 6 равен 5.
# Шестой столбец не имеет пустых клеток.
Последняя логическая часть — стопор шириной в три клетки:
# В первом столбце заполнены все клетки, кроме двух верхних.
# Во втором столбце заполнены все клетки, кроме верхней.
# В третьей колонке пусты все клетки, кроме второй сверху.
: '''Фигуры.''' Последовательностью фигур для всей игры будет конкатенация последовательностей для каждого <math>a_i</math> и завершающей последовательности. Для каждого числа <math>a_1,\dots,a_{3s}</math> имеем следующие части:
# ''Инициатор'' — последовательность <math>\langle I,LG,SQ \rangle</math>.
# ''Наполнитель'' — последовательность <math>\langle LG,LS,LG,LG,SQ \rangle</math>, повторенная <math>a_i</math> раз.
# ''Завершитель''— последовательность <math>\langle SQ,SQ \rangle</math>.
Вышеописанные части подаются для <math>a_1,a_2,\dots</math> последовательно. После частей, соответствующих <math>a_{3s}</math>, идет завершающая последовательность:
# <math>s</math> фигур <math>I</math> подряд.
# одна фигура <math>RG</math>.
# <math>3T/2 + 5</math> фигур <math>I</math> подряд.
//продолжение
}}
== Источники информации ==
* [http://arxiv.org/abs/cs/0210020 «Tetris is Hard, Even to Approximate» by Erik D. Demaine, Susan Hohenberger, David Liben-Nowell]
[[Категория:NP]]
