Abstract: A disentanglement puzzle consists of mechanically interlinked pieces, and thepuzzle is solved by disentangling one piece from another set of pieces. A string puzzleconsists of strings entangled with one or more wooden pieces. We consider the generalizedstring puzzle problem whose input is the layout of strings and a wooden board withholes embedded in the 3-dimensional Euclidean space. We present a polynomial-timetransformation from an arbitrary instance f of the 3SAT problem to a string puzzle s suchthat f is satisﬁable if and only if s is solvable. Therefore, the generalized string puzzleproblem is NP-hard.Keywords: disentanglement puzzle; polynomial-time reduction; NP-hard1. IntroductionA disentanglement puzzle consists of mechanically interlinked pieces, and the puzzle is solved bydisentangling one piece or a set of pieces from another set of pieces. A typical disentanglement puzzleis a wire puzzle, which is one of the most fundamental and popular playthings.A wire puzzle consists of two or more entangled stiff wires. Wires may or may not be closed loops,and they have complex shapes. Normally, wire puzzles are solved by disentangling one piece fromanother set of pieces without cutting or bending the wires.A string puzzle is also a disentanglement puzzle, which is an intellectual training toy especially foryoung children. To avoid accidental injury, it is composed entirely of natural materials, instead of stiff
['Chuzo Iwamoto', 'Kento Sasaki', 'Kenichi Morita']
A Polynomial-Time Reduction from the 3SAT Problem to the Generalized String Puzzle Problem