Affiliations: Institut für Informatik,
Heinrich-Heine-Universität Düsseldorf, 40225 Düsseldorf, Germany.
rothe@cs.uni-duesseldorf.de
Note: [] Address for correspondence: Institut für Informatik,
Heinrich-Heine-Universität Düsseldorf, 40225 Düsseldorf,
Germany
Abstract: Holzer and Holzer [10] proved that the Tantrix™ rotation puzzle
problem is NP-complete. They also showed that for infinite rotation puzzles,
this problem becomes undecidable. We study the counting version and the unique
version of this problem. We prove that the satisfiability problem
parsimoniously reduces to the Tantrix™ rotation puzzle problem. In particular,
this reduction preserves the uniqueness of the solution, which implies that the
unique Tantrix™ rotation puzzle problem is as hard as the unique
satisfiability problem, and so is DP-complete under polynomial-time randomized
reductions, where DP is the second level of the boolean hierarchy over NP.
Keywords: computational complexity, rotation puzzle, tiling of the plane, parsimonious reduction , counting problem
