Helmut Alt, Hans Bodlaender, Marc van Kreveld, Günter Rote,
and Gerard
Tel:
Wooden geometric puzzles: design and hardness proofs
- In: Proceedings of the fourth conference on Fun with
Algorithms
(FUN 2007). Castiglioncello, June 2007, Editors: Pilu Crescenzi,
Giuseppe Prencipe, and Geppino Pucci. Lecture Notes in Computer
Science, 4475, Springer-Verlag, 2007, pp. 16–29. doi:10.1007/978-3-540-72914-3_4
- Theory of Computing Systems 44 (2009), 160–174. doi:10.1007/s00224-008-9104-3
Abstract
We discuss some new geometric puzzles and the complexity of their
extension to arbitrary sizes. For gate puzzles and two-layer puzzles we
prove NP-completeness of solving them. Not only the solution of puzzles
leads to interesting questions, but also puzzle design gives rise to
interesting theoretical questions. This leads to the search for
instances of
partition that use only integers and are uniquely solvable. We show
that
instances of polynomial size exist with this property. This result also
holds
for partition into k subsets with the same sum: We
construct
instances of n integers with subset sum O(nk+1),
for
fixed k.
Last update: May 14, 2008.