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

Master Thesis (2022)
Author(s)

I.E. Dijcks (TU Delft - Electrical Engineering, Mathematics and Computer Science)

Contributor(s)

E. Demirović – Mentor (TU Delft - Algorithmics)

AE Zaidman – Graduation committee member (TU Delft - Software Engineering)

Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright
© 2022 Isha Dijcks
More Info
expand_more
Publication Year
2022
Language
English
Copyright
© 2022 Isha Dijcks
Graduation Date
21-06-2022
Awarding Institution
Delft University of Technology
Programme
Computer Science
Faculty
Electrical Engineering, Mathematics and Computer Science
Reuse Rights

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.

Files

License info not available