Abstract

In this paper we introduce several innovative variants on the classic Connect-The-Dots puzzle. We study the underlying geometric principles and investigate methods for the automatic generation of high-quality puzzles from line drawings.

Specifically, we introduce three new variants of the classic Connect-The-Dots puzzle. These new variants use different rules for drawing connections, and have several advantages: no need for printed numbers in the puzzle (which look ugly in the final drawing), and perhaps more challenging “game play”, making the puzzles suitable for different age groups. We study the rules of all four variants in the family, and design principles describing what makes a good puzzle. We identify general principles that apply across the different variants, as well as specific implementations of those principles in the different variants. We make these mathematically precise in the form of criteria a puzzle should satisfy.

Furthermore, we investigate methods for the automatic generation of puzzles from a plane graph that describes the input drawing. We show that the problem of generating a good puzzle –one satisfying the mentioned criteria– is computationally hard, and present several heuristic algorithms.

Using our implementation for generating puzzles, we evaluate the quality of the resulting puzzles with respect to two parameters: one for similarity to the original line drawing, and one for ambiguity; i.e. what is the visual accuracy needed to solve the puzzle.

Corresponding Publications

The Connect-The-Dots Family of Puzzles: Design and Automatic Generation

Maarten Löffler, Mira Kaiser, Tim van Kapel, Gerwin Klappe, Marc van Kreveld, Frank Staals

ACM Transactions on Graphics, 2014

Presented at SigGraph 2014.

Download Local Copy View Slides Export Citation

@article{pointpuzzles2014,
  author = {L{\"o}ffler, Maarten and Kaiser, Mira and
                  van Kapel, Tim and Klappe, Gerwin and
                  van Kreveld, Marc and Staals, Frank},
  title = {The Connect-The-Dots Family of Puzzles: Design and Automatic Generation},
  journal = {ACM Transactions on Graphics},
  issue_date = {July 2014},
  volume = {33},
  number = {4},
  month = {jul},
  year = {2014},
  issn = {0730-0301},
  pages = {72:1--72:10},
  numpages = {10},
  doi = {10.1145/2601097.2601224},
  publisher = {ACM},
  address = {New York, NY, USA},
  keywords = {algorithms, geometry, pencil-and-paper puzzles},
  category = {other},
  url = {https://dl.acm.org/authorize?N95144},
  note = {Presented at SigGraph 2014.},
}

Clear Unit-Distance Graphs

Marc van Kreveld, Maarten Löffler, Frank Staals

Abstr. 29th European Workshop on Computational Geometry (EuroCG), 2013

Download Local Copy View Slides Export Citation

@article{clear_unit-distance_graphs_connect_the_dot2013,
  author = {van Kreveld, Marc and L{\"o}ffler, Maarten and Staals, Frank},
  title = {Clear Unit-Distance Graphs},
  journal = {Abstr. 29th European Workshop on Computational Geometry (EuroCG)},
  year = {2013},
  location = {Braunschweig, Germany},
  numpages = {4},
  url = {http://www.ibr.cs.tu-bs.de/alg/eurocg13/booklet_eurocg13.pdf},
  project = {pointpuzzles2014},
  category = {other},
}