Finding a Hamiltonian Path in a Cube with Specified Turns is Hard (Preprint)

スポンサーリンク

概要

• 論文の詳細を見る

• 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 N3 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.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.21(2013) No.3 (online)------------------------------

• 2013-05-15

著者

• Jayson Lynch

  MIT Computer Science and Artificial Intelligence Laboratory

• Zachary Abel

  MIT Department of Mathematics

• Sarah Eisenstat

  MIT Computer Science and Artificial Intelligence Laboratory

関連論文

• Computational Complexity of Piano-Hinged Dissections
• Finding a Hamiltonian Path in a Cube with Specified Turns is Hard (Preprint)

スポンサーリンク