摘要翻译：
Tetravex是一个广泛使用的单人电脑游戏，在这个游戏中，你会得到$n^2$单位的瓷砖，每条边都有一个数字标签。目标是将每个瓦片放置在$N$×$N$平方中，以便所有相邻的边都用相同的数字标记。不幸的是，玩Tetravex在计算上很困难。更确切地说，我们证明了判定是否存在四凸板的平铺是NP完全的。因此，决定在哪里放置瓷砖是NP困难的。这可能有助于解释为什么Tetravex是一个很好的谜题。这个结果补充了许多涉及平铺的单人游戏的类似结果。例如，NP-完备性结果已经显示：俄罗斯方块的离线版本、KPlumber（它涉及包含管道图纸的旋转瓷砖，以形成一个连接的网络），以及最短滑动拼图问题。它提出了一些悬而未决的问题。例如，无限版是图灵完成的吗？我们如何产生真正令人困惑的四维问题，因为随机NP完全问题往往容易得令人惊讶？我们能观察到相变行为吗？在保证有唯一解的情况下，问题的复杂性又如何呢？我们如何生成具有独特解的谜题？
---
英文标题：
《Tetravex is NP-complete》
---
作者：
Yasuhiko Takenaga and Toby Walsh
---
最新提交年份：
2009
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Computational Complexity        计算复杂度
分类描述：Covers models of computation, complexity classes, structural complexity, complexity tradeoffs, upper and lower bounds. Roughly includes material in ACM Subject Classes F.1 (computation by abstract devices), F.2.3 (tradeoffs among complexity measures), and F.4.3 (formal languages), although some material in formal languages may be more appropriate for Logic in Computer Science. Some material in F.2.1 and F.2.2, may also be appropriate here, but is more likely to have Data Structures and Algorithms as the primary subject area.
涵盖计算模型，复杂度类别，结构复杂度，复杂度折衷，上限和下限。大致包括ACM学科类F.1（抽象设备的计算）、F.2.3（复杂性度量之间的权衡）和F.4.3（形式语言）中的材料，尽管形式语言中的一些材料可能更适合于计算机科学中的逻辑。在F.2.1和F.2.2中的一些材料可能也适用于这里，但更有可能以数据结构和算法作为主要主题领域。
--
一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--

---
英文摘要：
  Tetravex is a widely played one person computer game in which you are given $n^2$ unit tiles, each edge of which is labelled with a number. The objective is to place each tile within a $n$ by $n$ square such that all neighbouring edges are labelled with an identical number. Unfortunately, playing Tetravex is computationally hard. More precisely, we prove that deciding if there is a tiling of the Tetravex board is NP-complete. Deciding where to place the tiles is therefore NP-hard. This may help to explain why Tetravex is a good puzzle. This result compliments a number of similar results for one person games involving tiling. For example, NP-completeness results have been shown for: the offline version of Tetris, KPlumber (which involves rotating tiles containing drawings of pipes to make a connected network), and shortest sliding puzzle problems. It raises a number of open questions. For example, is the infinite version Turing-complete? How do we generate Tetravex problems which are truly puzzling as random NP-complete problems are often surprising easy to solve? Can we observe phase transition behaviour? What about the complexity of the problem when it is guaranteed to have an unique solution? How do we generate puzzles with unique solutions?
---
PDF链接：
https://arxiv.org/pdf/0903.1147