The Mathematical Mystery Behind Sudoku Mathematics Essay

The Mathematical Mystery Behind Sudoku Mathematics Essay conundrum granuloses roll in the hay 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(prenominal) government issue from 1-9 appearing no more than once from each column, each row and each of the club sub- footb every last(predicate) fields. Sudoku is a type of logic-based numerical puzzle game that has a unique solution once completed. The most common multifariousness of a Sudoku is constructed as a 99 grid with nine 33 sub-grids and is primarily partially completed. Sudoku has deform appealing among puzzle enthusiasts and involves complex thinking and practice. Available daily in newspapers, mobiles and some(prenominal) a nonher(prenominal) more, this addictive and brain-teasing puzzle game has become one of the most popular games to play since the time of the Rubiks cube.This dissertati on discusses the mathematical side involved in Sudoku. on that point is no mathematics in actually solving a Sudoku but more of how it is used from a creators side. The 99 grid leave be considered in the majority of the report however a glimpse into other size grids will be discussed briefly withal known as variants. Mathematicians grant been inquiring How many unique solutions ar there in a Sudoku? Essentially meaning what be the possible ship expressive style of filling in an empty Sudoku grid so that each row, column and sub-grid contains the sum ups 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 company 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 Jarviss approach to enumerating all possible Sudoku grids where they employ some(prenominal) mathematical concepts. Furthermore I will uncover the importance of Latin squares and its use of constructing Sudokus.There are many constraints in regards to when are similar solutions considered dissimilar such as solutions of similar structure, symmetry etc. Preserving symmetries are known as relabeling symbols, band permutations, reflection, transposition and rotation. Burnsides Lemma theorem is one of their techniques in deliberation the quash of essentially various solutions.Many difficult hassles 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.Sudokus whoremonger take many forms and shapes. These are called Sudoku variants and consist of rectangular regions, Sudokus with a large region having no clues ( turn of take downtss), an empty row, column or sub-grid and many more Here I will research the logic behind irregular Sudokus as well as examining any occurring patterns or whether it has occurred by chance.1.2 Latin squares and SudokuSudoku is alike a special content 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 even off 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 spare constraint that the nine sub-grids must hold the numbers 1-9. A reduction stick out be made to any Latin square by permuting the rows and columns. This formation 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 in impermanent class of finite sets. Counting combinations and counting permutations are two of th e most common forms.The number of valid Latin squares is known to be slightly 5.525 x 10. Write about Colbourns proof1.3 Combinatorics and renewal assembly theoryCombinations and permutations have slightly different meaning. Combinations are the number of different slipway of selecting n targets from a set but the order of events is not burning(prenominal). From a set of 3 objects, lets 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 tether 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 1Formula 1.= =Where is the combination formula, is the permutation formula, n is the total number of objects and r is the number to be arrangedBoth methods are one way of cypher the number of possible Sudoku solutions and this will be looked at later in the report.Chapter 2Enumerating possible Sudoku solutions2.1 Distinct Sudoku solutionsThere are many approaches to enumerating possible Sudoku solutions. To calculate 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 list 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 disembowel it easier, each sub-grid is given an abbreviation seen in figure 3.B1B2B3B4B5B6B7B8B9 get word 1. Abbreviated sub-grid with top band (Felgenhauer and Jarvis, 2006)Firstly the y 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.123456789Figure 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 require 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 a nd 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 reductionPermutation reductionColumn reductionAs 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 restri ction of 9 sub-grids. That macrocosm said, there will be no shortage of Sudoku puzzles any time soon. Verification of this result has been confirmed by several(prenominal) other mathematicians Ed Russell to be more precise.2.2 Essentially different Sudoku gridsWhether 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 drawstring of symmetries can occur between two grids, it is essentially different.Two Sudoku grids are the same provided the first grid can be converted to the endorsement by applying some sort of symmetry. For instance, take figure 3 4 below the set of 3s in the first grid can be interchanged by the placements of the set of 1s, effectively producing the second grid.1728649354935172866 58293174247359618865172349319486527586721493924638751731945862Figure 3. Valid Sudoku grid372864915491537286658291374247159638865372149139486527586723491924618753713945862Figure 4. Another valid Sudoku grid from Figure 1As 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.732864915941537286568291374427159638685372149319486527856723491294618753173945862Figure 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.795382641328164597146957832967413258432875916581629374874536129659241783213798465Figure 6. Rotational of 90 degrees from figure 1These operations performed above maintain the property of it being valid and t his 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 form a group of any Sudoku grid.A group is a set G if it satisfies the following propertiesCLOSURE If f and g are elements of G, then fg is also an element of G.ASSOCIATIVITY If f, g, and h are elements of G, then f(gh)=(fg)h must satisfy.IDENTITY ELEMENT There is an e lement e in G such that ge=eg=g for all g in G.INVERSE For any element g of G, there is another element d of G such that gd=dg=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 terce stacks (3 vertical blocks of a Sudoku), permuting the three bands (3 horizontal blocks of a Sudoku), permuting the three columns deep down a stack, permuting the three rows indoors a band, and any reflection or rotation. Any two transformations can be merged to shape other elements 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 propertiesfor grids A, B and C in set GReflexi vity A = ASymmetry If A = B then B = A transitivity If A = B and B = C then A = CLet 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. This can also be referred to as 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 enumerate all essential 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 find the a verage 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 mailboat called GAP. It is interesting to note that some of the elements in H contain equivalent fixed grids. In other words, it is now easier to work out as each of the classes contains one symmetry. However a number of symmetries in H have no fixed points. Subsequently, it is not necessary to calculate 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- sectors of X, then Formula 2 holds where, for gG, X is the number of xX 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 Burnsides Lemma Theorem.Chapter 3Nondeterministic polynomials3.1 NP-complete and SudokuSudokus 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 nondeterm inistic-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 work in polynomial time or more commonly whether P = NP. Consequently being one of the greatest un understand mathematical problems. The majority of estimator 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 Sudokus 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 tone 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 completionAnother 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 o f NP-complete problems. A full list of other problems that are NP-complete can be found in Garey and Johnson (1979).Chapter 4Sudoku Variants4.1 VariationThe classic form of a 99 Sudoku are polyominoes. There are other variations of Sudokus that can be applied to the rules of Sudoku. There are puzzles of the size 66 with 23 regions or a 1212 grid of 43 regions. More so, there are other intrigue Sudoku variants such as Greater than Sudoku.Chapter 5Personal Critical ReviewThe progress I have made during the duration of this project, have been fairly disinclined but surely getting there. Having said this on many occasions, I have still not conquered my time management skills The project started very impenetrable 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 th at 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 all-important(a) 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 6ConclusionA challenging problem for further research is to proof whether NP-complete problems can be solved in polynomial time. This has yet to be solved an d anyone who has a dinner dress proof will be rewarded $1 million dollars by The Clay Mathematics Institute.