קולוקוויום בביה"ס למדעי המחשב - On Nonogram and Graph Planarity Puzzle Generation

There are many puzzles in the world, both physical and digital ones. From the algorithms research perspective, a lot of attention has been given to combinatorial and graph-based puzzles and how to solve them with an algorithm. We will focus on puzzles with a geometric component and consider design of the puzzles and algorithms to generate them. Automated generation of puzzles is arguably more useful than automated solving. We will focus on new nonogram puzzles and new graph planarization puzzles, and encounter digitization of polygons with bounded error, Hausdorff and Frechet distance, cubic Bezier curves, simulated annealing, token swapping on graphs, and planar graph drawing.