Towards Generic Solving, Generation, and Rating Methods for Strategy-Solvable Pen and Paper Puzzles

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.
Computer Science