1 ?ééü
????
è?o???·¨??Dèòaò???àí??·????￡?a??·???￡??éò??a??μ??êìa￡?è??′?óD?￡¨àyè?￡?NPíê??D?[9])?é?D?¨D?oíì?êa?é????μ?êμ?êD??ü?￡?ú±????D￡??ò????′ó?a?????èà′ì????í?T?1·??éó??·?￡?ò????ê×?è?èê?ó??·oí?üμ?ò?D?±???￡???ê?óDò??¨μ???2?D??êìaμ?NPíê??D?×?è?á??óμ?ó??·?D￡?è?oó?¤?÷￡¨UN￡??ú????ò?D??é????μ??é?D?¨D??￡?ò??′óò?D?êμó?μ??÷ìa?D???¨3?NPíê??D??￡

±???ê??ùóúò??μáDμ?????￡??aê?ó??-ê?μ?NPíê??D?ê??éê?àí1¤?§?oDemaine, Hohenberger and Liben-Nowell from MIT [7]ìá3?μ?￡??aê??ú?ù?ü?aμ?ê??￡?¤?÷?ò?ˉ[3]￡?2￠?úáao??ú?ˉ????[2]?D×?á?·￠±í?￡[13]oí[14]??é?ê?ìáμ?μ??????êìa??DDá?±íê??￡′óá?μ??¤?Y?¤?÷á??ò???ùìá3?μ??aD?1?μ?μ??yè·D??￡?í?T?1·??éê?ò???μ￥?úó??·￡??a??ó??·óé???úμ???′ó?é×é?t?????ú?-±???μ???D?ó??·°?é?D?3é?￡í??ò?éò?Dy×aoí????ò??ˉ??μ????￡è?1?ò???DD??óé×é?t?é×é3é￡??ò??DD??3y?￡?a??ó??·éè??μ??÷òa??μ?ê?±￡3????é?@@¤ê±??í???ó??·?￡?ù????μ??êìa?ù±?é?ê?ò?????μ??￡???¨ò???o?êêμ?ó??·??°?￡¨?ò3??aò????í?T?1·??é??°?￡?￡?oíò???óDDòμ?óD?Tò??a?μáD×é?t?é￡???°?±???3y?a??·?ê?ê??é?üμ??e￡? NPíê??D?μ??¤?Y?y?ú??éù?￡?á1?±í?÷￡??éò?ê??ù??μ?3·????êìaμ?êμàyD?3é?àμ±?′?óμ??í?T?1·??é??°?￡??a??·?°?ê???°??éò?±???3y?￡????°?μ?ê1ó??a??á????êìa￡o?éò??ú??°??Dí?ó??·?e￡???á?è??a?èμ?′e°???o?ê???o?è?o???°????éò?′?μ?￡???óèo?êêμ?×÷?·?￡áíò????êìa×??é?D?¨￡oè?1?ó??§μ??à?￥×÷ó?ê?ò?D?????￡?è?oó?D?¨ê?·?ê?×é?tDòáD?Do?óDμ??3D??°?????±DòáD￡??ùóD?aD??êìa???úoó???D?a???￡

1 Introduction

Any algorithm requires a theoretical analysis. Such an analysis may address issues like complexity (e.g., NP-completeness [9]), decidability and practical properties concerning special cases.In this paper we would like to discuss the Tetris game in this light. We will first describe the game and some of its variants, show NP-completeness of a certain decision problem naturally attached to the game and then prove (un)decidability in some other cases. We conclude with some practical topics that arise from the NP-completeness proof.

This paper is based on a series of articles that begins with the original NP-completeness proof of Demaine, Hohenberger and Liben-Nowell from MIT [7], that was well-noticed in the popular press. The proof was simplified in [3], leading to a joint journal paper [2]. In [13] and[14] the other issues mentioned above were dealt with. For full proofs we refer to these papers.

Tetris is a one-person game where random pieces consisting of four blocks fall down, one at a time, in an originally empty rectangular game board. The player is allowed to rotate and horizontally move the falling piece. If an entire row of the board is filled with blocks, it is removed (?°cleared?±). The main purpose of the game is to keep on playing as long as possible.

The decision problem under consideration is essentially the following. Given a partially filled game board (referred to as a Tetris configuration), and an ordered finite known series of pieces, is it possible to play in such a way that the whole board is cleared? The NP-completeness proof is by reduction. It is shown that instances of the so-called 3-Partition problem can be translated into rather involved Tetris configurations, where solutions correspond with boards that can be cleared. The configurations used suggest the question of constructibility: which configurations can be reached during game play? The rather surprising answer appears to be that almost any configuration can be reached, given suitable pieces. Another issue has to do with decidability: if the user interaction is somewhat bounded, is it then decidable whether certain natural sets of piece sequences contain ?°clearing?± sequences? All these topics will be addressed in the sequel.