1 介绍
任何算法都需要一个理论分析。这种分析，可以解决的问题，如复杂性（例如，NP完整性[9])可判定性和特殊情况下的实际性能。在本文中，我们将从这个角度来讨论俄罗斯方块游戏。我们将首先描述游戏和它的一些变种，显示有一定的决策性问题的NP完整性自然连接到游戏中，然后证明（UN）在其他一些情况下的可判定性。我们从一些实用的主题中断定出NP完整性。
本文是基于一系列的文章，开始与原始的NP完整性是麻省理工学院Demaine, Hohenberger and Liben-Nowell from MIT [7]提出的，这是众所周知的事。证明简化[3]，并在联合期刊论文[2]中做了发表。[13]和[14]对上述提到的其他问题进行了表述。大量的证据证明了我们所提出的这些观点的正确性。俄罗斯方块是一个单机游戏，这个游戏由随机的四大块组件下落在原本空的矩形游戏板上形成。玩家可以旋转和水平移动下跌片。如果一整行都由组件块组成，则该行清除。这个游戏设计的主要目的是保持尽可腀@な奔渫娓糜蜗贰Ｋ悸堑奈侍饣旧鲜且韵录傅恪８ㄒ桓龊鲜实挠蜗访姘澹虺莆桓龆砺匏狗娇槊姘澹鸵桓鲇行虻挠邢抟阎盗凶榧椋灞磺宄庵址绞绞强赡艿穆穑 NP完整性的证据正在减少。结果表明，可以是所谓的3分区问题的实例形成相当复杂的俄罗斯方块面板，解决方案是面板可以被清除。该面板的使用解决了该问题：可以在面板中玩游戏吗？而令人惊讶的答案似乎是几乎任何面板都可以达到，给予合适的作品。另一个问题做可判定：如果用户的相互作用是一些界面，然后判定是否是组件序列中含有的某些“清算”序列，所有这些问题将在后文中解决。
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.
