Helmut Alt, Hans Bodlaender, Marc van Kreveld, Günter Rote, and Gerard Tel:

Wooden geometric puzzles: design and hardness proofs

  1. 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
  2. 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.
  pdf file (gzipped)
other papers about this subject
Last update: May 14, 2008.