%0 Journal Article
%T A Polynomial-Time Reduction from the 3SAT Problem to the Generalized String Puzzle Problem
%A Chuzo Iwamoto
%A Kento Sasaki
%A Kenichi Morita
%J Algorithms
%D 2012
%I MDPI AG
%R 10.3390/a5020261
%X A disentanglement puzzle consists of mechanically interlinked pieces, and the puzzle is solved by disentangling one piece from another set of pieces. A string puzzle consists of strings entangled with one or more wooden pieces. We consider the generalized string puzzle problem whose input is the layout of strings and a wooden board with holes embedded in the 3-dimensional Euclidean space. We present a polynomial-time transformation from an arbitrary instance£¿£¿ of the 3SAT problem to a string puzzle s such that£¿£¿ is satisfiable if and only if s is solvable. Therefore, the generalized string puzzle problem is NP-hard.
%K disentanglement puzzle
%K polynomial-time reduction
%K NP-hard
%U http://www.mdpi.com/1999-4893/5/2/261