А вы не знали? :) Erik Demaine, Susan Hohenberger и David Liben-Nowell из Massachusetts Institute of Technology видимо, игрались в тетрис долго и нудно, и пришли к такому выводу, что тетрис можно свести к известной задаче коммивояжера.
Подобная алгоритмическая сложность по отношению к тетрису заключается в том, что не существует алгоритма с полиномиальной сложностью, способного максимизировать счет в игре, даже в случае, когда известна последовательность падающих фигур.
Это, конечно, очень важное наблюдение, ведь тысячи и тысячи людей по всему миру, играя в тетрис, даже не представляют, как далеки они от Идеальной Игры.
" © hizone.info