Computational complexity of string puzzles
Chihiro Iwamoto, Kento Sasaki, Kenichi Morita · Computing: The Australasian Theory Symposium · 2012
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 is a type of disentanglement puzzle, which consists of strings entangled with one or more wooden pieces. In this paper, 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 f of the 3SAT problem to a string puzzle s such that f is satisfiable if and only if s is solvable. Therefore, the generalized string puzzle problem is NP-hard.