Paper by Erik D. Demaine

Reference:

Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, and Tao B. Schardl, “Finding a Hamiltonian Path in a Cube with Specified Turns is Hard”, Journal of Information Processing, volume 21, number 3, July 2013, pages 368–377.

BibTeX

@Article{HamPath_JIP,
  AUTHOR        = {Zachary Abel and Erik D. Demaine and Martin L. Demaine and Sarah Eisenstat and Jayson Lynch and Tao B. Schardl},
  TITLE         = {Finding a {Hamiltonian} Path in a Cube with Specified Turns is Hard},
  JOURNAL       = {Journal of Information Processing},
  journalurl    = {http://www.ipsj.or.jp/english/jip/},
  VOLUME        = 21,
  NUMBER        = 3,
  MONTH         = {July},
  YEAR          = 2013,
  PAGES         = {368--377},

  withstudent   = 1,
  doi           = {https://dx.doi.org/10.2197/ipsjjip.21.368},
  dblp          = {https://dblp.org/rec/journals/jip/AbelDDELS13},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.2197/ipsjjip.21.368">J-STAGE</A>.},
  award         = {Specially Selected Paper},
  awardurl      = {http://www.ipsj.or.jp/english/organization/aboutipsj/award/ssp_award.html},
  papers        = {SnakeCube2D_CCCG2023; FixedAngle_CCCG2022},
}

Abstract:

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³ 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.

Comments:

This paper is also available from J-STAGE.

Availability:

The paper is available in PDF (3387k).

See information on file formats.

[Google Scholar search]

Related papers:

FixedAngle_CCCG2022 (Computational Complexity of Flattening Fixed-Angle Orthogonal Chains)