Puzzle games can be very enjoyable and is popular amongst kids as well as adults. Many of you may know the game Sudoku; where by the goal of the game is to fill in the remaining empty cells with each number from 1-9 appearing no more than once from each column, each row and each of the nine sub-grids. Sudoku is a type of logic-based numerical puzzle game that has a unique solution once completed. The most common form of a Sudoku is constructed as a 9×9 grid with nine 3×3 sub-grids and is primarily partially completed. Sudoku has become appealing among puzzle enthusiasts and involves complex thinking and practice. Available daily in newspapers, mobiles and many more, this addictive and brain-teasing puzzle game has become one of the most popular games to play since the time of the Rubik’s cube.
This dissertation discusses the mathematical side involved in Sudoku. There is no mathematics in actually solving a Sudoku but more of how it is used from a creator’s side. The 9×9 grid will be considered in the majority of the report; however a glimpse into other size grids will be discussed briefly also known as variants. Mathematicians have been questioning ‘ How many unique solutions are there in a Sudoku?’ Essentially meaning what are the possible ways of filling in an empty Sudoku grid so that each row, column and sub-grid contains the numbers 1 through 9. Your first thought of an answer may be a couple of thousands, but as you understand the concepts behind a Sudoku, you begin to grasp a whole new aspect.
Combinatorics and permutation group theory are largely interwoven with analysing Sudoku. For that reason, I aim to explore these theories and understand how it applies to the methods of enumerating Sudoku grids. In particular I will be looking at Felgenhauer and Jarvis’s approach to enumerating all possible Sudoku grids where they employ several mathematical concepts. Furthermore I will uncover the importance of Latin squares and its use of constructing Sudoku’s.
There are many constraints in regards to when are similar solutions considered different such as solutions of similar structure, symmetry etc. Preserving symmetries are known as relabeling symbols, band permutations, reflection, transposition and rotation. Burnside’s Lemma theorem is one of their techniques in computing the number of essentially different solutions.
Many difficult problems are of the type called nondeterministic-polynomial known as an NP-complete problem. This will direct me onto the debate on whether Sudoku is an NP-complete problem.
Sudoku’s can take many forms and shapes. These are called Sudoku variants and consist of rectangular regions, Sudoku’s with a large region having no clues (numbers), an empty row, column or sub-grid and many more! Here I will research the logic behind irregular Sudoku’s as well as examining any occurring patterns or whether it has occurred by chance.
1. 2 Latin squares and Sudoku
Sudoku is also a special case of Latin squares. The Swiss mathematician, Leonhard Euler made many fundamental discoveries during 1782 including Latin squares. A Latin square is an N x N matrix where by a set of N characters are arranged such that each row and column contains one of each character. This is also in the case of a Sudoku, when complete, with an additional constraint that the nine sub-grids must hold the numbers 1-9. A reduction can be made to any Latin square by permuting the rows and columns. This arrangement is an aspect of combinatorics and is most commonly referred to as enumeration. Enumerative combinatorics is a classic area of Combinatorics and involves counting the number of infinite class of finite sets. Counting combinations and counting permutations are two of the most common forms.
The number of valid Latin squares is known to be approximately 5. 525 x 10²â·. Write about Colbourn’s proof
1. 3 Combinatorics and Permutation group theory
Combinations and permutations have slightly different meaning. Combinations are the number of different ways of selecting n objects from a set but the order of events is not important. From a set of 3 objects, let’s call these 1, 2 and 3. If for example I was asked to pick the number of ways of selecting 2 objects out of the 3, there would be three combinations 12, 23 and 13. 12 = 21 since the order of each pair is not important. A permutation on the other hand does consider the position. Therefore if I was to use the above example, there would be six permutations. A simpler way to calculate a larger set would be to use formula 1:
Formula 1.
= =
Where is the combination formula, is the permutation formula, n is the total number of objects and r is the number to be arranged
Both methods are one way of computing the number of possible Sudoku solutions and this will be looked at later in the report.
Chapter 2
Enumerating possible Sudoku solutions
2. 1 Distinct Sudoku solutions
There are many approaches to enumerating possible Sudoku solutions. To enumerate every possible Sudoku solution, a Sudoku differs from another if they are not identical. Thus all solutions will be consider unless they are like for like. Felgenhauer and Jarvis was the first to enumerate the Sudoku grid solutions directly in 2005.
There approach was to analyze the permutations of the top row used in valid solutions. Their knowledge of the complexity in computing the number of Latin squares has made them aware of how they should go about getting an answer with fewer computations. Hence by using relabeling this could shorten the number of counts.
To make it easier, each sub-grid is given an abbreviation seen in figure 3.
B1
B2
B3
B4
B5
B6
B7
B8
B9
Figure 1. Abbreviated sub-grid with top band (Felgenhauer and Jarvis, 2006)
Firstly they consider every solution to filling in blocks B2, B3, given that B1 is in standard form. To work out every possible way of arranging B1 on its own would essentially be computing the number of permutations of 9 symbols. There are 9! of filling in B1. The main operation they use is called relabeling.
1
2
3
4
5
6
7
8
9
Figure 2. B1 in standard form (Felgenhauer and Jarvis, 2006)
Felgenhauer and Jarvis have found that B2 and B3 is the same as the transpose of B2′ and B3′. Therefore the number of ways of arranging B1, B2 and B3 and B1, B2′ and B3′ to a complete grid is equally the same. This means that computing one set of possibilities will cut down the number of solutions. Inevitably, there are few pairs of B2 and B3 that needs to be worked out and as well as using reduction the number of possibilities for the top band of a Sudoku grid is 9! x 2612736 = 948109639680. The next section involves brute force computation. As running through all 2612736 possibilities would be exceedingly tedious for B2 and B3, Felgenhauer and Jarvis attempts to ‘ identify configurations of the numbers in these blocks which give the same number of ways of completing to a full grid.’ This in return, will cut down the number possibilities.
Permuting B2 and B3 in every way such that the result gives a unique solution will preserve the number of complete grids. This is the same for B5 and B6, and B8 and B9. However this changes B1 from its standard form, so an additional relabeling of B1 needs to be performed. Another approach to reducing the number of possibilities is to permute the columns in each block and permute the rows of any block.
Reducing the number of possible ways by permuting.
Lexicographical reduction
Permutation reduction
Column reduction
As a result of these methods, Felgenhauer and Jarvis have found that there are approximately 6670903752021072936960 ≈ 6. 671 x 10²¹ Sudoku solutions. In light of this result, there are fewer solutions than Latin squares due to the fact that there is that extra restriction of 9 sub-grids. That being said, there will be no shortage of Sudoku puzzles any time soon. Verification of this result has been confirmed by several other mathematicians – Ed Russell to be more precise.
2. 2 Essentially different Sudoku grids
Whether symmetrical Sudoku grids are considered as two separate solutions is another method of enumerating the possible solutions. In this case, the only solutions are ones that are essentially different. Lets say two Sudoku grids are equivalent if one is a transformation of the other by applying any number of symmetries. If however, no such chain of symmetries can occur between two grids, it is essentially different.
Two Sudoku grids are the same if we can get from one to the other by applying some sort of symmetry. For instance, take figure 3 & 4 below; the set of 3’s in the first grid can be interchanged by the placements of the set of 1’s, effectively producing the second grid.
Figure 3. Valid Sudoku grid
Figure 4. Another valid Sudoku grid from Figure 1
As well as this, a solution is said to be the same as another if any two columns or rows are swapped. The first column and second column in figure 3 can be exchanged to give figure 5. The two solutions are said to be symmetrical because the transformation still produces a valid Sudoku grid.
Figure 5. First and second column swapped from Figure 1.
Another form of symmetries includes rotational grids. A rotation of Figure 3 by 90 degrees generates a new valid Sudoku grid shown in Figure 6.
Figure 6. Rotational of 90 degrees from figure 1
Any of these operations performed on a valid grid maintains the property of it being valid and this is known as symmetries of a grid. When an object is subject to these operations, certain properties are preserved. An example would be if one performs symmetry on to a Sudoku grid and repeats this operation once more, the final transformation is itself symmetric. In addition a symmetrical object can be transformed back to its original state by another form of symmetry. Performing several symmetries on a Sudoku grid can also be achieved by grouping its neighbouring pair. So the first symmetry can be paired with the second or the second can be paired with the third and so on. The resulting transformation is nevertheless the same either way. From these properties, it is inevitable to say that the set of symmetries of any Sudoku grid form a group.
A group is a set G if it satisfies the following properties:
CLOSURE – If f and g are elements of G, then f·g is also an element of G.
ASSOCIATIVITY – If f, g, and h are elements of G, then f·(g·h)=(f·g)·h must satisfy.
IDENTITY ELEMENT – There is an element e in G such that g·e= e·g= g for all g in G.
INVERSE – For any element g of G, there is another element d of G such that g·d= d·g= e, where e is the identity element. (The element d = g-1.)
The symmetry group is thus generated by the transformations of: re-labelling the nine digits, permuting the three stacks (3 vertical blocks of a Sudoku), permuting the three bands (3 horizontal blocks of a Sudoku), permuting the three columns within a stack, permuting the three rows within a band, and any reflection or rotation. These can be combined to form other elements of the group and together they comprise of the symmetry group G. Given that any element of G can be mapped so that it takes one grid to another, we can say that the set of valid Sudoku grids has a finite number of elements. Thus G has finitely many symmetries.
The association between symmetrical Sudoku grids are in fact an equivalence relation and satisfies the following three properties:
for grids A, B and C in set G
Reflexivity – A = A
Symmetry – If A = B then B = A
Transitivity – If A = B and B = C then A = C
Let A be any valid Sudoku grid, we must consider all the grids that are equivalent to a valid Sudoku grid A. To do this, we firstly have to group together grids that are essentially the same so that we can partition the set of grids. This will break the set of Sudoku grids into subsets, with groups that contain no relating elements within each other. The term subset can be called equivalence classes and is denoted by X/G. In any equivalence class, there are elements that are equivalent to each other by symmetry. The total number of elements in X/G is equal to the number of essential Sudoku grids.
To calculate the number of essentially different Sudoku grids, we shall look at all the symmetries neglecting the re-labelling of the nine digits for the time being. The number of distinct symmetries founded by Russell and Jarvis (2006) is said to contain 3359232 (pg 4). In this finite group H, we need to take the average number of grids fixed by an element of H, up to re-labelling. Next we need to verify the number of fixed points of all elements in H. Russell and Jarvis have found that there are 275 classes of symmetries using a software package called GAP. It is interesting to note that some of the elements in H have the same number of fixed grids. In other words, we only need to count the number of fixed points for one symmetry for each of the 275 classes. However there exist symmetries in H that have no fixed points. Subsequently, there is no need to count the number of fixed grids for those that have no fixed points. That being said, there are only 27 out of 275 classes that contain fixed points, meaning fewer computations.
Rotman. J. J (1995) demonstrate that ‘ if X is a finite G-set and | X/G| is the number of G-orbits of X, then Formula 2 holds where, for gÑ” G, X is the number of xÑ” X fixed by g’ (pg 58-61). Using this notion, we have established that the number of valid Sudoku grids is of a finite set and X/G is the number of essentially different Sudoku grids, so we can obtain the number of essentially different Sudoku grids by using the Burnside Lemma Theorem.
Formula 2. Burnside Lemma Theorem (Rotman, 1995)
Burnside Lemma Theorem is a useful tool when dealing with symmetry with a set of countable objects. When used to enumerate the essentially different Sudoku grid, the set of equivalent grids form an orbit of the symmetric group. The number orbits are essentially the number of different grid solutions. This may sound slightly (ALOT) trickier to compute, nonetheless Russell and Jarvis have shown that the number of essentially different Sudoku grids is 5, 472, 730, 538 with the implementation of Burnside’s Lemma Theorem.
Chapter 3
Nondeterministic polynomials
3. 1 NP-complete and Sudoku
Sudoku’s may relate to a variety of problems, in particularly, whether Sudoku is an NP-complete problem. It is known that NP-complete problems are one of the most complicated cases in NP, also referred to as nondeterministic-polynomial. Its rival, P problems relates to NP as both being in the same complexity class. Mathematicians have yet to solve whether NP-complete problems can be solved in polynomial time or more commonly whether P = NP. Consequently being one of the greatest unsolved mathematical problems. The majority of computer scientists believe that P ≠NP, as a result would mean that NP-complete problems are significantly trickier to compute than to verify. Unfortunately, nobody has yet found an efficient algorithm, not even with the use of computers available today.
A problem is said to be NP-complete when its solution can be proved in polynomial time. And if that problem can be solved in polynomial time, all problems in NP can be solved too. An interesting characteristic of NP-complete problems is that the time frame to solve the problem increases rapidly as the size of the problem gets larger. If that is the case and Sudoku’s are NP-complete, solving a Sudoku of higher order (say 17² x 17²) will become increasingly challenging algorithmically then the standard 3² x 3² version – were talking trillions of years.
It has been shown that Sudoku does belong to the category of NPC problems by Takayuki Yato of the Univeristy of Tokyo (2003). An exchange for the notation ASP-completeness (shorthand for Another solution problem), led the proof of NP-completeness of ASP. Their proof uses reduction in order to obtain the required polynomial-time ASP from the problem of Latin squares by Colbourn (1984) who has verified, ‘ the NP-completeness of ASP of Latin square completion’
Another accountable source by Provan states that, ‘ It is known that solving general-sized Sudoku puzzles is NP-hard, even for square grids with blocks consisting of the sets of rows and columns (Latin Squares) or for p2 x p2 grids with blocks consisting of rows, columns, and the p2 partitioned p x p subsquares.’
Mathematical programmes such as the 0-1 linear programming and the knapsack problems are also cases of NP-complete problems. A full list of other problems that are NP-complete can be found in Garey and Johnson (1979).
Chapter 4
Sudoku Variants
4. 1 Variation
The classic form of a 9×9 Sudoku are polyominoes. There are other variations of Sudoku’s that can be applied to the rules of Sudoku. There are puzzles of the size 6×6 with 2×3 regions or a 12×12 grid of 4×3 regions. More so, there are other fascinating Sudoku variants such as Greater than Sudoku.
Chapter 5
Personal Critical Review
The progress I have made during the duration of this project, have been fairly slow but surely getting there. Having said this on many occasions, I have still not conquered my time management skills! The project started very slow which meant I was behind schedule. Nevertheless my organisational skills have kept me on balance. The GANT chart has been of great help in doing so.
What has kept me going throughout this project in particular would be self discipline and motivation. This project has proven that I am capable of working to my own initiative, but also well within a group; my time during the group project. Furthermore, my time on this project has definitely promoted a better mentality of my future ambitions.
I have learnt that it is crucial to read a lot, as well as reading as broadly as I can. This in turn have aided in the running of my project. With other coursework deadlines, I made that a priority and had no time to meet with my supervisor. I understand that meeting with my supervisor is equally important because a supervisor is there to encourage and to advice on any difficult obstacles I may encounter.
An area of interest to proof whether NP-complete problems can be solved in polynomial time, was left open as future work. This could be the next step of extending this report that little bit further.
Chapter 6
Conclusion
A challenging problem for further research is to proof whether NP-complete problems can be solved in polynomial time. This has yet to be solved and anyone who has a formal proof will be rewarded $1 million dollars by The Clay Mathematics Institute.
