World Scientific
  • Search
  •   
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

TETRIS IS HARD, EVEN TO APPROXIMATE

    https://doi.org/10.1142/S0218195904001354Cited by:33 (Source: Crossref)

    In the popular computer game of Tetris, the player is given a sequence of tetromino pieces and must pack them into a rectangular gameboard initially occupied by a given configuration of filled squares; any completely filled row of the gameboard is cleared and all filled squares above it drop by one row. We prove that in the offline version of Tetris, it is -complete to maximize the number of cleared rows, maximize the number of tetrises (quadruples of rows simultaneously filled and cleared), minimize the maximum height of an occupied square, or maximize the number of pieces placed before the game ends. We furthermore show the extreme inapproximability of the first and last of these objectives to within a factor of p1-ε, when given a sequence of p pieces, and the inapproximability of the third objective to within a factor of 2-ε, for any ε>0. Our results hold under several variations on the rules of Tetris, including different models of rotation, limitations on player agility, and restricted piece sets.

    This paper is the merged version of two previous papers: "Tetris is Hard, Even to Approximate" by Erik D. Demaine, Susan Hohenberger, and David Liben-Nowell, and "Tetris is Hard, Made Easy" by Ron Breukelaar, Hendrik Jan Hoogeboom, and Walter A. Kosters.1,2

    References

    • E. D. Demaine, S. Hohenberger and D. Liben-Nowell, Tetris is hard, even to approximate, in Proc. 9th Ann. Int. Conf. Computing and Combinatorics (COCOON'03), eds. T. Warnow and B. Zhu, Lecture Notes in Computer Science, Vol. 2697 (Springer-Verlag, July 2003), pp. 351-363. Also available as Technical Report MIT-LCS-TR-865, Laboratory for Computer Science, Massachusetts Institute of Technology (September 2002), and as cs.CC/0210020 . Google Scholar
    • R. Breukelaar, H. J. Hoogeboom and W. A. Kosters, Tetris is hard, made easy, Technical Report 2003-9, Leiden Institute of Advanced Computer Science, Universiteit Leiden (2003) . Google Scholar
    • Tetris, Inc. http://www.tetris.com . Google Scholar
    • D.   Sheff , Game Over: Nintendo's Battle to Dominate an Industry ( Hodder and Stoughton , London , 1993 ) . Google Scholar
    • S. Kim, Games Mag. 66 (2002). Google Scholar
    • M. M. Kostreva and R. Hartman, Multiple objective solution for Tetris, Technical Report 670, Department of Mathematical Sciences, Clemson University (May 1999) . Google Scholar
    • J. Brzustowski, Can you win at Tetris? Master's thesis, University of British Columbia (1992) . Google Scholar
    • H. Burgiel, Mathematical Gazette 194 (1997), DOI: 10.2307/3619195. Google Scholar
    • R. Kaye, Math. Intell. 22(2), 9 (2000), DOI: 10.1007/BF03025367. Crossref, Web of ScienceGoogle Scholar
    • E. D. Demaine, Playing games with algorithms: Algorithmic combinatorial game theory, Proc. 26th Symp. Mathematical Foundations in Computer Science2136, Lecture Notes in Computer Science, eds. J. Sgall, A. Pultr and P. Kolman (2001) pp. 18–32. Google Scholar
    • U. Z. Jenga, Proc. 13th Symp. Discrete Algorithms (2002) pp. 243–246. Google Scholar
    • M. R.   Garey and D. S.   Johnson , Computers and Intractability: A Guide to the Theory of NP-Completeness ( W. H. Freeman and Company , NY , 1979 ) . Google Scholar
    • M. R. Garey and D. S. Johnson, SIAM J. Comput. 4, 397 (1975), DOI: 10.1137/0204035. Crossref, Web of ScienceGoogle Scholar
    • H. J. Hoogeboom and W. A. Kosters, How to construct Tetris configurations, Technical Report 2003-8, Leiden Institute of Advanced Computer Science, Universiteit Leiden (2003) . Google Scholar
    • C. Papadimitriou, J. Comput. Syst. Sci. 31, 288 (1985), DOI: 10.1016/0022-0000(85)90045-5. Crossref, Web of ScienceGoogle Scholar
    Remember to check out the Most Cited Articles!

    Check out these titles in image analysis!