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

Тетрис, очень популярная видеоигра с падающими сверху фигурками, была изобретена в 1985 году русским компьютерным инженером Алексеем Пажитновым. В 2002 году американские ученые определили класс сложности игры и показали, что он имеет сходства со сложнейшими проблемами математики, которые требуют исчерпывающего анализа для нахождения решения и не решаются с помощью простых алгоритмов.

В тетрисе фигурки падают сверхуна игровое поле и движутся к его нижнему краю. Во время того, как фигурка опускается, игрок может вращать ее и двигать по горизонтали. Форма фигурок, которые используются в игре, называется тетрамино, они состоят из четырех квадратов, соединенных вместе и образующих несложную геометрическую фигуру, например, букву Т. Когда падающая фигурка останавливается, натыкаясь на лежащие внизу фигурки, сверху начинает падать еще одна. Полностью заполнившиеся горизонтальные ряды пропадают, и ряды над ними падают на одну клетку вниз. Игра заканчивается, когда на поле недостаточно места для появления новой фигурки. Целью игрока является как можно более долгая игра и набор очков за заполненные ряды.

В 2002 году Эрик Дэмейн, Сьюзан Хохенбергер и Дэвид Либен-Ноэл исследовали обобщенную версию игры, в которой игровое поле может быть любых размеров. Они установили, что задача заполнения максимального числа рядов с помощью фигурок выбранной последовательности является NP-полной (“NP” обозначает “недетерминированной полиномиальной”). Хотя правильность решения таких задач можно проверить, само нахождение решения занимает огромное время. Классическим примером NP-полной проблемы является задача коммивоя жера, для решения которой необходимо найти оптимальный маршрут, по которому коммивояжер должен двигаться, чтобы посетить все указанные города. Проблемы этого класса являются невероятно сложными, потому что не существует быстрого и рационального алгоритма их решения.