Finding a Hamiltonian Path in a Cube with Specified Turns is Hard
Finding a Hamiltonian Path in a Cube with Specified Turns is Hard
复制标题
在具有指定匝数的立方体中找到哈密顿路径很困难
DOI：
10.2197/ipsjjip.21.368
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
T. Schardl
中科院分区：
文献类型：
--
作者：
Zachary Abel;E. Demaine;M. Demaine;Sarah Eisenstat;J. Lynch;T. Schardl
本文证明了在N ×N ×N立方体图中寻找一条Hamilton路的NP-完全性，该图的圈数正好是沿着该路的沿着指定长度，从而建立了Snake Cube谜题的NP-完全性：将一个由N3个单位立方体组成的链折叠成一个N × N × N立方体，这些单位立方体在面中心处连接（通常用一条穿过所有立方体的线）.沿着这条路径，我们证明了一个普适性结果：锯齿形链（它必须使每个单元旋转）可以折叠成4×4×4加细后的任意多边形立方体，或折叠成2 × 2 × 2加细后的任意Hamilton多边形立方体。
We prove the NP-completeness of finding a Hamiltonian path in an N ×N ×N cube graph with turns exactly at specified lengths along the path. This result establishes NP-completeness of Snake Cube puzzles: folding a chain of N 3 unit cubes, joined at face centers (usually by a cord passing through all the cubes), into an N × N × N cube. Along the way, we prove a universality result that zig-zag chains (which must turn every unit) can fold into any polycube after 4×4×4 refinement, or into any Hamiltonian polycube after 2 × 2 × 2 refinement.