The Art of Solving Sudokus

Introduction
In this notebook we will look at so-called artificial neural networks, and how these can be “programmed” to solve optimization problems. More specifically we will look at a meta heuristic using such artificial neural networks, which is inspired by physical phenomena like the cooling down of gases or the occurrence of permanent magnetization under certain conditions. The underlying physical model used to explain these phenomena, can also be used to “solve” other optimization problems. To demonstrate the use of this meta heuristic we will apply it to the popular Sudoku game. We will first show how the heuristic can be applied to solve the Sudoku, and secondly how the heuristic itself can be related to the more intuitive approach commonly used to solve a Sudoku by hand. Finally we will discuss what its weak points are, and we will indicate some possible improvements to the meta-heuristics.

Meta-heuristics
In combinatorial optimization exact solutions are sometimes hard to find due to the size of the optimization problem and the time it takes to solve the problem. In such cases it can be beneficial to use approximation algorithms, which do not guarantee to find the best solution, but often find a near optimal solution in a reasonable time span. One can define “meta heuristics” as general patterns for such algorithmic approaches to approximate optimal solutions for problems in combinatorial optimization. Usually meta heuristics are applied in case exact solutions cannot be found in time, however it is also worthwhile to apply meta heuristics to easier optimization problems, where exact solutions can be found, so that one can compare the outcome of the meta heuristic to these exact solutions. In the following notes we will focus on the meta heuristic Mean Field Annealing. We will describe how the meta heuristic works and apply it to a simple optimization problem, which corresponds to solving the popular Sudoku game. In this case we will focus on the stochastic nature of Mean Field Annealing, point out some "peculiar" behaviour of the meta heuristic and suggest a way to measure the quality of the solutions found.

The Sudoku game
The Sudoku-game consists of a 9x9 square of 81 fields. The purpose of the game is to fill in all fields using the integer numbers 1, 2,..., 9, in such a way that each column, each row and each of the nine smaller 3x3-squares consists of all nine different integers. Since there are a lot of possibilities to fill in a blank 9x9 square in this way, some of the fields are pre-filled. For these fields the integers are fixed and given in advance, and thus putting constraints on the possible solutions. The other fields have to be filled in by the Sudoku player. A good Sudoku contains enough pre-filled fields to have one unique solution. An example of a Sudoku follows below:
[[Insert Picture]]

One way for solving the Sudoku is to keep track of possible values for each field, that is to maintain a list for each field consisting of all possible integers, excluding the integers that are already used, but also excluding integers that cannot be used based on more “advanced” reasoning. Such a list for each field can be constructed easily by looking at the column, the row and 3x3-square, to which the field belongs. We can start constructing these lists for an arbitrary field, do the same for a next (perhaps less) arbitrary field, and continue this way, using of course the additional information we obtained from each list.
For some Sudoku’s these lists are sufficient to fill in all fields, because after some iterations each list uniquely determines the integer value for the corresponding field. These are the easy ones. For more difficult Sudoku’s it takes more effort; we have to combine the information from the lists for several fields, and sometimes even that will not be enough, and we have to go through all remaining possibilities.

This intuitive approach for solving Sudoku’s is quite similar to what one can accomplish using artificial neural networks and the mean field annealing meta heuristic. Before detailing on those artificial neural networks it is good to already highlight these similarities:

1. We first pick a field at random, to investigate on its possible values. The randomness can be decreased by learning from the past, that is using information obtained in previous steps.
2. For each field we keep track of the possible values by maintaining a list of those values. These lists will be used in next iterations to determine or update the list for other fields.

What will be interesting is to see why some Sudoku’s are that hard to solve and why some of them are just a piece of cake. We will see that this relates directly to what artificial neural networks and mean field annealing will do for us. In the end we hope that this provides us with means to determine while solving problems with the mean field annealing meta heuristic whether we are heading the right way, or will get stuck at some "solution" that does not solve our problem.