Universal solver for number-placement puzzles

OData support
Rajacsics Tamás
Department of Automation and Applied Informatics

The sudoku puzzle, its countless variations and other number puzzles are widely popular and offer relaxation for any ages. How are they created?

At first sight inconceivably difficult cause and effect relationships operate them, that during solving somehow always point to a single possible solution. How can the creator of the puzzle guarantee that any way someone starts to solve the puzzle it will certainly reach the only correct solution? How can we make a computer program that can verify that an arbitrary puzzle is solvable and has only one solution? Can we ask such a program to show us the logical steps that were used to reach the solution? How can we even give an arbitrary puzzle to a solver algorithm as an input? What ways do we have to generate number puzzles with a given difficulty?

After defining the concept of a number puzzle and reviewing the rules of the most popular number puzzles, I introduce an easily extensible object oriented model and a domain-specific language that can be used to describe a number puzzle so that it can be given to a general solver algorithm.

I review two mathematical models in detail that with their available solvers can be used to generate the solution of number puzzles given in our model.

I present a recursive solver algorithm based on logical deduction methods and show the details of the design and implementation of the created software component and also highlight some interesting points in the rules of the puzzles.

With the created tools I elaborate a method to generate puzzles with the given difficulty and I report the feedback received from users for the generated puzzles.

I demonstrate a user friendly web interface created for the solver component that can be used to build number puzzles and to analyse the steps of their solution.

At the end I compare the performances of the created solvers.


Please sign in to download the files of this thesis.