Видеоигра Тетрис - одна из самых популярных компьютерных игр, когда-либо созданных, возможно, отчасти потому, что её трудность делает ее захватывающей. Цель игры - перемещать и поворачивать падающие геометрические фигуры, чтобы сформировать полные ряды в нижней части игрового поля.
Учёные-математики показали, что проблема, связанная с нитевидными тетроминозами Тетриса, является одной из самых трудных задач, даже если вы знаете, какие фигуры будут дальше.
Эрик Д. Демейн, Сьюзан Хоэнбергер и Дэвид Либен-Ноуэлл из Технологического института Массачусетса определили, что Тетрис квалифицируется как неразрешимая полиномиально-полная задача. То есть, хотя относительно легко проверить, действительно ли решение проблемы, нет эффективного способа оптимизации любой из целей игры. К ним относятся максимизация количества очищенных строк, максимизация количества штук, успешно помещенных до потери, максимизация числа "тетрисов" (очистка четырех строк одновременно) и сохранение высоты сетки как можно ниже в ходе игры.
Исследователи также обнаружили, что Тетрис является неразрешимой полиномиально-сложной задачей, а это означает, что она как минимум решается, как и любая другая проблема НП.
"Пока вы играете в Тетрис, вы действительно решаете сложные задачи", - говорит Демейн.
Интересно, что еще одна, казалось бы, простая, но очень захватывающая игра "Сапер" также является неразрешимой полиномиально-сложной задачей. Так что в следующий раз, когда вы проиграете, успокойтесь. Потому что компьютер, возможно, не смог бы сделать намного лучше.