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

摘要

In this paper we introduce several innovative variants on the classicrnConnect-The-Dots puzzle. We study the underlying geometricrnprinciples and investigate methods for the automatic generation ofrnhigh-quality puzzles from line drawings.rnSpecifically, we introduce three new variants of the classic Connect-rnThe-Dots puzzle. These new variants use different rules for drawingrnconnections, and have several advantages: no need for printedrnnumbers in the puzzle (which look ugly in the final drawing), andrnperhaps more challenging “game play”, making the puzzles suitablernfor different age groups. We study the rules of all four variantsrnin the family, and design principles describing what makes a goodrnpuzzle. We identify general principles that apply across the differentrnvariants, as well as specific implementations of those principlesrnin the different variants. We make these mathematically precise inrnthe form of criteria a puzzle should satisfy.rnFurthermore, we investigate methods for the automatic generationrnof puzzles from a plane graph that describes the input drawing. Wernshow that the problem of generating a good puzzle –one satisfyingrnthe mentioned criteria– is computationally hard, and present severalrnheuristic algorithms.rnUsing our implementation for generating puzzles, we evaluate thernquality of the resulting puzzles with respect to two parameters: onernfor similarity to the original line drawing, and one for ambiguity;rni.e. what is the visual accuracy needed to solve the puzzle.