俄罗斯方块的理论

俄罗斯方块的理论(中文5600字,英文4600字)
1 .介绍
任何算法都需要一个理论分析。这种分析，可以解决的问题，如复杂性（例如，NP完整性[9])可判定性和特殊情况下的实际性能。在本文中，我们将从这个角度来讨论俄罗斯方块游戏。我们将首先描述游戏和它的一些变种，显示有一定的决策性问题的NP完整性自然连接到游戏中，然后证明（UN）在其他一些情况下的可判定性。我们从一些实用的主题中断定出NP完整性。
    本文是基于一系列的文章，开始与原始的NP完整性是麻省理工学院Demaine, Hohenberger and Liben-Nowell from MIT [7]提出的，这是众所周知的事。证明简化[3]，并在联合期刊论文[2]中做了发表。[13]和[14]对上述提到的其他问题进行了表述。大量的证据证明了我们所提出的这些观点的正确性。俄罗斯方块是一个单机游戏，这个游戏由随机的四大块组件下落在原本空的矩形游戏板上形成。玩家可以旋转和水平移动下跌片。如果一整行都由组件块组成，则该行清除。这个游戏设计的主要目的是保持尽可能长时间玩该游戏。所考虑的问题基本上是以下几点。给定一个合适的游戏面板（简称为一个俄罗斯方块面板），和一个有序的有限已知系列组件块，整板被清除这种方式是可能的吗？ NP完整性的证据正在减少。结果表明，可以是所谓的3分区问题的实例形成相当复杂的俄罗斯方块面板，解决方案是面板可以被清除。该面板的使用解决了该问题：可以在面板中玩游戏吗？而令人惊讶的答案似乎是几乎任何面板都可以达到，给予合适的作品。另一个问题做可判定：如果用户的相互作用是一些界面，然后判定是否是组件序列中含有的某些“清算”序列，所有这些问题将在后文中解决。
 
The Theory of Tetris
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 , leading to a joint journal paper . In and[14] the other issues mentioned above were dealt with. For full proofs we refer to these papers.