Towards Generic Solving, Generation, and Rating Methods for Strategy-Solvable Pen and Paper Puzzles
I.E. Dijcks (TU Delft - Electrical Engineering, Mathematics and Computer Science)
E. Demirović – Mentor (TU Delft - Algorithmics)
AE Zaidman – Graduation committee member (TU Delft - Software Engineering)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Pen and paper puzzles are a fun pastime to test your logical reasoning skills, with Sudoku being the most popular of these puzzles.
While the problem of solving these puzzles is usually in NP-Complete, generating them is more difficult, depending on the type of puzzle.
When generating puzzles for humans, we have to keep in mind how they solve them, as we cannot expect them to brute-force the solution.
Generation methods exist for simple number-based puzzles like the Sudoku, but these methods do not translate to the domain of language-based puzzles.
We take the concept of strategy-solving to mimic human solving methods and apply them to the Raatsel, a language-based puzzle, and the Sudoku, to generalize a common methodology for generating, solving and rating these problem instances.
A new method will be introduced to generate Raatsels using a reduction from Subgraph Isomorphism.
This concept of instance generation with specific properties has many applications outside of puzzles, such as validating correctness and generating training data for machine learning.