Monday, October 20, 2014

Solving and Generating Sudokus

Sudokus, who does not know them - these small boxes containing numbers which can easily get under your skin. The desire and the plan to solve these using a computer then also brought me to the idea of creating Sudokus. Thus, the next posts will be about the solving and generating new Sudokus.
It should be clear that a computer can solve a sudoku relatively easy - it can just try all possibilities and thus eventually come to the solution. Much more difficult is the creation. Here again the actual creation is not the problem - again a filled out Sudoku can be created by trying out. The main difficulty lies in deleting certan fields to achieve a desired difficulty. Furthermore it should also have only one solution. This is, so it is easily controllable / comparable, and every field should only allow one possible number.
Then to the next difficulty: When can we say a sudoku is easy, hard etc? How is this defined? It can be easily observed, that there is no direct connection between the number of deleted fields and the dificulty.
First some words about me: I myself never really solved Sudokus, all my knowledge about them I obtained during the research and writing of this project. All ideas presented here are thus my opinion and can be wrong. About corrections and criticism I would - as always - be very happy.
When I started with the topic I thought that there is some "standard" for creating Sudokus. This seems to be not the case. But one principle, which is often used, is the following: One programs a solving procedure for Sudokus which resembles the human's behaviour. For this one implements different rules, according to which also humans decide. This rules are sorted according to their difficulty, then Sudokus can be categorized by checking which rules the program has to apply to solve them. To determine the fields to be deleted one can either try to apply the rules "backwards", or one also deletes fields randomly and checks the difficulty in every step (I chose to implement this).
Now of course also the question arises, what kind of rules exist and how difficult they are. At the beginning I thought, most of the Sudokus can be solved using some few easy rules (as, for example, deleting a number in a candidate list if it already occurs in a field of the same "group"). But as it seems, there exist many, arbitrary complex rules, which seemingly are also not equal to each other. So I decided for some of these rules and hope, that they are representative and their difficulty is labeled appropiately. The first paper I found was Creating Sudoku Puzzles by SUN. From this I got the mentioned principle. There 4 categories of rules are used, first I thought this was basically everything there exists - but liked mentioned before, there are numerous other rules. The rules mentioned there are also explained on many other websites, like on the German Wikipedia page or the very vast collection of rules www.sudokuwiki.org. Further I took 2 rules from this page. I was motivated, amonst others, by Udo's Blog, he wrote a post about solving Sudokus by trying out.
In the next post I will first explain the used rules. Then I will explain the implementation of a Sudoku solver based on these rules - it should be clear, that the last level of rules is always trying out, since there is no rule which can solve every Sudoku without "guessing". In the last post I will then describe the generation of arbitrary difficulty Sudokus.

With the program from this posting series I also started a new blog, there daily new Sudokus are published.

No comments:

Post a Comment