26 Multi-agent systems versus common solving techniques
in section3.4, where the VRP is presented in an entirely new way. The advantage in using a MAS is therefore not the computation speed, but the fact that the problem is presented in a different way compared to the old strategies, which in the long run could lead to effective solvers. It is important to mention that the system design should only be MAS, if the system can benefit from it, but it is sometime necessary to try to use a MAS, even though it is not obvious, in order to spot new effective solution strategies.
Multi-agent systems own a number strengths and weaknesses compared to other strategies that solves the same problem. First of all if the problem can be partioned, it is possible to receive a gain in computational performance, but it is important that the communication cost is kept down, to get a fast solution. Additionally a MAS is scalable, which means that it is easy to change or remove agents. A MAS is also robust, if it has agents that supplement each other.
Chapter
5
Sudoku
In this chapter a brief introduction to Sudoku is given, by presenting the terminology and the rules in the puzzle. Then a solution strategy is presented that can help solve the puzzle. Finally it is shown that Sudoku belongs to the class ofN P-Complete problems.
5.1 Behind the puzzle
Sudoku is not an entirely new invention. It started already in 1783 with the Swiss mathematician Leonard Euler, who invented Latin Squares, but Sudoku puzzles, as we know them today, were first published in 1979 under the name Number Place.
Later on the Japanese gave the puzzle the name Sudoku.
A Latin Square problem is not entirely the same as a Sudoku puzzle, but they have many similarities. A Latin Square is a grid of size n×n, which contains all the numbers from 1 through n exactly once in every row and column. The Sudoku problem has the following definition.
General Sudoku:
A general Sudoku puzzle consists of a n2 ×n2 grid, which is divided into n×n squares, where n is the order of the puzzle. Throughout this thesis the following notation of the Sudoku properties is used.
28 Sudoku
• A cell refers to one of then4 entries in the grid.
• The value of a cell refers to the number placed in the cell.
• A row-,column- orsquare-domain refers to the rows, columns and squares of the grid.
• A candidate is a number that could be placed in the cell.
• A clue is a value in a cell that is already given in the problem instance.
• The order of the puzzle refers to the size of n. A typical 9×9 grid, will therefore be a puzzle of order 3.
A Sudoku puzzle has the following constraints:
• Each cell must have a value from 1 to n2.
• Each of the row, column and square domains must contain the values from 1 ton2 exactly once.
These constraints will trough out the report be referred to, as the Sudoku con-straints.
The difference between a Latin Square and a solved Sudoku puzzle is therefore that a Sudoku is more constrained than the Latin Square, as a valid Sudoku must also satisfy the square constraints. The fact that each row and column constraint must be satisfied in a valid Sudoku puzzle shows that every solved Sudoku is also a Latin Square, but not the other way around.
At figure 5.1a classical order 3 Sudoku grid is displayed, with and without initial values (clues).
Not every order 3 problem instance is considered to be a real Sudoku puzzle. It is therefore often in the literature defined that a proper problem instance satisfies the condition:
Condition: A Sudoku problem instance must have a unique solution, which can be determined by stepwise making logical conclusions based on the values already present in the puzzle.
A puzzle is only considered a proper Sudoku problem instance, throughout this thesis, if this holds.
5.1 Behind the puzzle 29
(a) Empty Sudoku grid (b) Sudoku grid with clues
Figure 5.1: Sudoku problem instances.
A Sudoku problem instance contains a number of predefined cell values, clues. The clues provide the player with the initial information to start determining the solution to the puzzle.
According to [24] an empty classical grid have 5.472.730.538 possible solutions, if the puzzle does not have any clues, and symmetry is taken into account.
Rating the Sudoku puzzle
A Sudoku puzzle is usually associated with a difficulty rating, which indicates how easy or difficult a given puzzle is to solve. The rating of a Sudoku puzzle is however not a standardized method. The obvious factors in determining a Sudoku puzzles rating would be the number of clues and the placement of the clues. One may argue that intuitively a Sudoku with few clues are more difficult that a Sudoku with many clues. Although this is right in many cases, it is not true for all Sudoku puzzles. There exists puzzles that have many clues, but which are more difficult than some puzzles with few clues. Likewise the placement of the clues will give rise to different difficulties. A Sudoku puzzle with a certain placement of the clues can be very different in rating, compared to a Sudoku puzzle with the same placement of clues, but where the values of the clues are different. This concludes that neither the number of clues nor the placement, is enough to determine the difficulty rating of a puzzle.
In the Sudoku community a good rating reflects how difficult a puzzle is for a human to solve. This could be reflected by the number and difficulty of the strategies
30 Sudoku
necessary to solve the puzzle. Recently a puzzle has been developed, known as Qassim Hamza, which has proven to be extremely difficult to solve, because all basic solution methods will not advance this puzzle towards a solution. See the puzzle in figure5.2.
Figure 5.2: Puzzle known as Qassim Hamza. Very hard puzzle to solve.
The number of clues and their placement, are not useful for determining difficulty, but instead they are believed to be the main factors in determining if a puzzle has a unique solution. It is not known what the minimum number of clues are, to ensure that the puzzle has one unique solution. It is argued in [35] that the minimum number in a classical Sudoku is 17, but this is not proved. In [24] they give an example on a puzzle with 17 clues with one solution, but underline that the minimum number could be even smaller. One might think that a puzzle with many given clues is likelier to have a unique solution, but this is not necessarily the case. In [24] they give an example of a puzzle with 29 clues that actually have two different solution.
An important part of solving a Sudoku puzzles is to keep track of the candidates in the undetermined cells. In figure5.3both the determined values and the candidates are displayed with respectively large and small font. The candidate values are the key for using clever strategies that can help solve the puzzle.