Informatik, TU Wien

Pleaching Pencil-&-Paper Picture Puzzles

Guest talk by Maarten Löffler, Utrecht University, the Netherlands.

The Algorithms & Complexity group and the Vienna Canter for Logic and Algorithms (VCLA) cordially invite you to a guest talk by Maarten Löffler from Utrecht University.

Abstract

Pencil-and-paper puzzles (e.g., Sudoku) are a popular pastime for both children and adults. Their main appeal lies in the logical solving process, but in some genres the puzzler is additionally rewarded when the solved puzzle reveals a picture (e.g., Nonograms). We introduce free-form variants of classic puzzle genres containing non-rectilinear or even curved elements. We study the underlying geometry: what constraints are there on the shapes and location of puzzle elements? How can we measure aspects of puzzles like solvability, difficulty, originality, fun, etc.? Finally, we use these geometric properties to develop automatic generators of puzzles: you draw a picture, and the system gives you a puzzle that solves to that picture.

Biography

Maarten Löffler is an assistant professor at Utrecht University in computational geometry and graph drawing. He obtained his PhD in 2009 on geometric uncertainty, and afterwards spent two years at the University of California in Irvine. He has a passion for pencil-and-paper puzzles, participating in the World Championship in 2003 and 2006.