Mathematics of Sudoku

Last updated

A 24-clue automorphic Sudoku with translational symmetry Sudoku Puzzle (automorphic with translational symmetry).png
A 24-clue automorphic Sudoku with translational symmetry

Mathematics can be used to study Sudoku puzzles to answer questions such as "How many filled Sudoku grids are there?", "What is the minimal number of clues in a valid puzzle?" and "In what ways can Sudoku grids be symmetric?" through the use of combinatorics and group theory.

Contents

The analysis of Sudoku is generally divided between analyzing the properties of unsolved puzzles (such as the minimum possible number of given clues) and analyzing the properties of solved puzzles. Initial analysis was largely focused on enumerating solutions, with results first appearing in 2004. [1]

For classical Sudoku, the number of filled grids is 6,670,903,752,021,072,936,960 (6.671×1021), which reduces to 5,472,730,538 essentially different solutions under the validity preserving transformations. There are 26 possible types of symmetry, but they can only be found in about 0.005% of all filled grids. An ordinary puzzle with a unique solution must have at least 17 clues. There is a solvable puzzle with at most 21 clues for every solved grid. The largest minimal puzzle found so far has 40 clues in the 81 cells.

Puzzles

Minimum number of givens

Ordinary Sudokus (proper puzzles) have a unique solution. A minimal Sudoku is a Sudoku from which no clue can be removed leaving it a proper Sudoku. Different minimal Sudokus can have a different number of clues. This section discusses the minimum number of givens for proper puzzles.

Ordinary Sudoku

A Sudoku with 17 clues Oceans Sudoku17 Puzzle-39451 trimmed.png
A Sudoku with 17 clues
A Sudoku with 17 clues and diagonal symmetry Sudoku Puzzle (a symmetrical puzzle with 17 clues) R4.png
A Sudoku with 17 clues and diagonal symmetry
A Sudoku with 18 clues and orthogonal symmetry Sudoku (18 clue symmetrical).png
A Sudoku with 18 clues and orthogonal symmetry
A Sudoku with 24 clues and complete geometric symmetry Sudoku Puzzle (a puzzle with total symmetry) trimmed.png
A Sudoku with 24 clues and complete geometric symmetry
A Sudoku with 19 clues and two-way orthogonal symmetry Sudoku Puzzle (Tourmaline)R2.png
A Sudoku with 19 clues and two-way orthogonal symmetry

Many Sudokus have been found with 17 clues, although finding them is not a trivial task. [2] [3] A 2014 paper by Gary McGuire, Bastian Tugemann, and Gilles Civario proved that the minimum number of clues in any proper Sudoku is 17 through an exhaustive computer search based on hitting set enumeration. [4]

Symmetrical Sudoku

The fewest clues in a Sudoku with two-way diagonal symmetry (a 180° rotational symmetry) is believed to be 18, and in at least one case such a Sudoku also exhibits automorphism. A Sudoku with 24 clues, dihedral symmetry (a 90° rotational symmetry, which also includes a symmetry on both orthogonal axis, 180° rotational symmetry, and diagonal symmetry) is known to exist, but it is not known if this number of clues is minimal for this class of Sudoku. [5]

Total number of minimal puzzles

The number of minimal Sudokus (Sudokus in which no clue can be deleted without losing uniqueness of the solution) is not precisely known. However, statistical techniques combined with a generator ('Unbiased Statistics of a CSP – A Controlled-Bias Generator'), [6] show that there are approximately (with 0.065% relative error):

Variants

There are many Sudoku variants, partially characterized by size (N), and the shape of their regions. Unless noted, discussion in this article assumes classic Sudoku, i.e. N=9 (a 9×9 grid and 3×3 regions). A rectangular Sudoku uses rectangular regions of row-column dimension R×C. Other variants include those with irregularly-shaped regions or with additional constraints (hypercube).

Regions are also called blocks or boxes. A band is a part of the grid that encapsulates 3 rows and 3 boxes, and a stack is a part of the grid that encapsulates 3 columns and 3 boxes. A puzzle is a partially completed grid, and the initial values are givens or clues. A proper puzzle has a unique solution. A minimal puzzle is a proper puzzle from which no clue can be removed without introducing additional solutions.

Solving Sudokus from the viewpoint of a player has been explored in Denis Berthier's book "The Hidden Logic of Sudoku" (2007) [7] which considers strategies such as "hidden xy-chains".

Mathematical context

The general problem of solving Sudoku puzzles on n2×n2 grids of n×n blocks is known to be NP-complete. [8]

A puzzle can be expressed as a graph coloring problem. [9] The aim is to construct a 9-coloring of a particular graph, given a partial 9-coloring. The Sudoku graph has 81 vertices, one vertex for each cell. The vertices are labeled with ordered pairs (x, y), where x and y are integers between 1 and 9. In this case, two distinct vertices labeled by (x, y) and (x′, y′) are joined by an edge if and only if:

The puzzle is then completed by assigning an integer between 1 and 9 to each vertex, in such a way that vertices that are joined by an edge do not have the same integer assigned to them.

A Sudoku solution grid is also a Latin square. [9] There are significantly fewer Sudoku grids than Latin squares because Sudoku imposes additional regional constraints.

Sudokus from group tables

As in the case of Latin squares the (addition- or) multiplication tables (Cayley tables) of finite groups can be used to construct Sudokus and related tables of numbers. Namely, one has to take subgroups and quotient groups into account:

Take for example the group of pairs, adding each component separately modulo some . By omitting one of the components, we suddenly find ourselves in (and this mapping is obviously compatible with the respective additions, i.e. it is a group homomorphism). One also says that the latter is a quotient group of the former, because some once different elements become equal in the new group. However, it is also a subgroup, because we can simply fill the missing component with to get back to .

Under this view, we write down the example, Grid 1, for .

Each Sudoku region looks the same on the second component (namely like the subgroup ), because these are added regardless of the first one. On the other hand, the first components are equal in each block, and if we imagine each block as one cell, these first components show the same pattern (namely the quotient group ). As outlined in the article of Latin squares, this is a Latin square of order .

Now, to yield a Sudoku, let us permute the rows (or equivalently the columns) in such a way, that each block is redistributed exactly once into each block – for example order them . This of course preserves the Latin square property. Furthermore, in each block the lines have distinct first component by construction and each line in a block has distinct entries via the second component, because the blocks' second components originally formed a Latin square of order (from the subgroup ). Thus we arrive at a Sudoku (rename the pairs to numbers 1...9 if you wish). With the example and the row permutation above, we arrive at Grid 2.

Grid 1 – The addition table in
(0,0)(0,1)(0,2)
(0,1)(0,2)(0,0)
(0,2)(0,0)(0,1)
(1,0)(1,1)(1,2)
(1,1)(1,2)(1,0)
(1,2)(1,0)(1,1)
(2,0)(2,1)(2,2)
(2,1)(2,2)(2,0)
(2,2)(2,0)(2,1)
(1,0)(1,1)(1,2)
(1,1)(1,2)(1,0)
(1,2)(1,0)(1,1)
(2,0)(2,1)(2,2)
(2,1)(2,2)(2,0)
(2,2)(2,0)(2,1)
(0,0)(0,1)(0,2)
(0,1)(0,2)(0,0)
(0,2)(0,0)(0,1)
(2,0)(2,1)(2,2)
(2,1)(2,2)(2,0)
(2,2)(2,0)(2,1)
(0,0)(0,1)(0,2)
(0,1)(0,2)(0,0)
(0,2)(0,0)(0,1)
(1,0)(1,1)(1,2)
(1,1)(1,2)(1,0)
(1,2)(1,0)(1,1)
Grid 2 – Generating a Sudoku
(0,0)(0,1)(0,2)
(1,0)(1,1)(1,2)
(2,0)(2,1)(2,2)
(1,0)(1,1)(1,2)
(2,0)(2,1)(2,2)
(0,0)(0,1)(0,2)
(2,0)(2,1)(2,2)
(0,0)(0,1)(0,2)
(1,0)(1,1)(1,2)
(0,1)(0,2)(0,0)
(1,1)(1,2)(1,0)
(2,1)(2,2)(2,0)
(1,1)(1,2)(1,0)
(2,1)(2,2)(2,0)
(0,1)(0,2)(0,0)
(2,1)(2,2)(2,0)
(0,1)(0,2)(0,0)
(1,1)(1,2)(1,0)
(0,2)(0,0)(0,1)
(1,2)(1,0)(1,1)
(2,2)(2,0)(2,1)
(1,2)(1,0)(1,1)
(2,2)(2,0)(2,1)
(0,2)(0,0)(0,1)
(2,2)(2,0)(2,1)
(0,2)(0,0)(0,1)
(1,2)(1,0)(1,1)

For this method to work, one generally does not need a product of two equally-sized groups. A so-called short exact sequence of finite groups of appropriate size already does the job. Try for example the group with quotient- and subgroup . It seems clear (already from enumeration arguments), that not all Sudokus can be generated this way.

Jigsaw sudokus

A Sudoku whose regions are not (necessarily) square or rectangular is known as a Jigsaw Sudoku. In particular, an N×N square where N is prime can only be tiled with irregular N-ominoes. For small values of N the number of ways to tile the square (excluding symmetries) has been computed (sequence A172477 in the OEIS ). [10] For N ≥ 4 some of these tilings are not compatible with any Latin square; i.e. all Sudoku puzzles on such a tiling have no solution. [10]

Solutions

The answer to the question 'How many Sudoku grids are there?' depends on the definition of when similar solutions are considered different.

Ordinary Sudoku

All solutions

For the enumeration of all possible solutions, two solutions are considered distinct if any of their corresponding (81) cell values differ. Symmetry relations between similar solutions are ignored., e.g. the rotations of a solution are considered distinct. Symmetries play a significant role in the enumeration strategy, but not in the count of all possible solutions.

The first known solution to complete enumeration was posted by QSCGZ (Guenter Stertenbrink) to the rec.puzzles newsgroup in 2003, [11] [12] obtaining 6,670,903,752,021,072,936,960 (6.67×1021) distinct solutions.

In a 2005 study, Felgenhauer and Jarvis [13] [12] analyzed the permutations of the top band used in valid solutions. Once the Band1 symmetries and equivalence classes for the partial grid solutions were identified, the completions of the lower two bands were constructed and counted for each equivalence class. Summing completions over the equivalence classes, weighted by class size, gives the total number of solutions as 6,670,903,752,021,072,936,960, confirming the value obtained by QSCGZ. The value was subsequently confirmed numerous times independently. A second enumeration technique based on band generation was later developed that is significantly less computationally intensive. This subsequent technique resulted in roughly needing 1/97 of the number of computation cycles as the original techniques, but was significantly more complicated to set up.

Essentially different solutions

The sudoku symmetry group

The precise structure of the sudoku symmetry group can be expressed succinctly using the wreath product (≀). The possible row (or column) permutations form a group isomorphic to S3S3 of order 3!4 = 1,296. [4] The whole rearrangement group is formed by letting the transposition operation (isomorphic to C2) act on two copies of that group, one for the row permutations and one for the column permutations. This is S3S3C2, a group of order 1,2962 × 2 = 3,359,232. Finally, the relabelling operations commute with the rearrangement operations, so the full sudoku (VPT) group is (S3S3C2) × S9 of order 1,218,998,108,160.

Fixed points and Burnside's lemma

The set of equivalent grids which can be reached using these operations (excluding relabeling) forms an orbit of grids under the action of the rearrangement group. The number of essentially different solutions is then the number of orbits, which can be computed using Burnside's lemma. The Burnside fixed points are grids that either do not change under the rearrangement operation or only differ by relabeling. To simplify the calculation the elements of the rearrangement group are sorted into conjugacy classes, whose elements all have the same number of fixed points. It turns out only 27 of the 275 conjugacy classes of the rearrangement group have fixed points; [14] these conjugacy classes represent the different types of symmetry (self-similarity or automorphism) that can be found in completed sudoku grids. Using this technique, Ed Russell and Frazer Jarvis were the first to compute the number of essentially different sudoku solutions as 5,472,730,538. [14] [15]

Completeness of the sudoku symmetry group

Excluding relabeling, the operations of the sudoku symmetry group all consist of cell rearrangements which are solution-preserving, raising the question of whether all such solution-preserving cell rearrangements are in the symmetry group. In 2008, Aviv Adler and Ilan Adler showed that all solution-preserving cell rearrangements are contained in the group, even for general grids. [16]

See also

Related Research Articles

<span class="mw-page-title-main">Automorphism</span> Isomorphism of an object to itself

In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphisms of an object forms a group, called the automorphism group. It is, loosely speaking, the symmetry group of the object.

<span class="mw-page-title-main">Symmetric group</span> Type of group in abstract algebra

In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group defined over a finite set of symbols consists of the permutations that can be performed on the symbols. Since there are such permutation operations, the order of the symmetric group is .

<span class="mw-page-title-main">Latin square</span> Square array with symbols that each occur once per row and column

In combinatorics and in experimental design, a Latin square is an n × n array filled with n different symbols, each occurring exactly once in each row and exactly once in each column. An example of a 3×3 Latin square is

<span class="mw-page-title-main">Polyomino</span> Geometric shapes formed from squares

A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge. It is a polyform whose cells are squares. It may be regarded as a finite subset of the regular square tiling.

<span class="mw-page-title-main">Parity (mathematics)</span> Property of being an even or odd number

In mathematics, parity is the property of an integer of whether it is even or odd. An integer is even if it is divisible by 2, and odd if it is not. For example, −4, 0, and 82 are even numbers, while −3, 5, 7, and 21 are odd numbers.

<span class="mw-page-title-main">Wreath product</span> Group formed from the action of one group on many copies of another, based on the semidirect product

In group theory, the wreath product is a special combination of two groups based on the semidirect product. It is formed by the action of one group on many copies of another group, somewhat analogous to exponentiation. Wreath products are used in the classification of permutation groups and also provide a way of constructing interesting examples of groups.

17 (seventeen) is the natural number following 16 and preceding 18. It is a prime number.

In mathematics, specifically group theory, the index of a subgroup H in a group G is the number of left cosets of H in G, or equivalently, the number of right cosets of H in G. The index is denoted or or . Because G is the disjoint union of the left cosets and because each left coset has the same size as H, the index is related to the orders of the two groups by the formula

<span class="mw-page-title-main">Polycube</span> Shape made from cubes joined together

A polycube is a solid figure formed by joining one or more equal cubes face to face. Polycubes are the three-dimensional analogues of the planar polyominoes. The Soma cube, the Bedlam cube, the Diabolical cube, the Slothouber–Graatsma puzzle, and the Conway puzzle are examples of packing problems based on polycubes.

<span class="mw-page-title-main">Kakuro</span> Type of logic puzzle

Kakuro or Kakkuro or Kakoro is a kind of logic puzzle that is often referred to as a mathematical transliteration of the crossword. Kakuro puzzles are regular features in many math-and-logic puzzle publications across the world. In 1966, Canadian Jacob E. Funk, an employee of Dell Magazines, came up with the original English name Cross Sums and other names such as Cross Addition have also been used, but the Japanese name Kakuro, abbreviation of Japanese kasan kurosu, seems to have gained general acceptance and the puzzles appear to be titled this way now in most publications. The popularity of Kakuro in Japan is immense, second only to Sudoku among Nikoli's famed logic-puzzle offerings.

<span class="mw-page-title-main">Sudoku</span> Logic-based number-placement puzzle

Sudoku is a logic-based, combinatorial number-placement puzzle. In classic Sudoku, the objective is to fill a 9 × 9 grid with digits so that each column, each row, and each of the nine 3 × 3 subgrids that compose the grid contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution.

<span class="mw-page-title-main">Dihedral group of order 6</span> Non-commutative group with 6 elements

In mathematics, D3 (sometimes alternatively denoted by D6) is the dihedral group of degree 3 and order 6. It equals the symmetric group S3. It is also the smallest non-abelian group.

<span class="mw-page-title-main">Rubik's Cube group</span> Mathematical group

The Rubik's Cube group is a group that represents the structure of the Rubik's Cube mechanical puzzle. Each element of the set corresponds to a cube move, which is the effect of any sequence of rotations of the cube's faces. With this representation, not only can any cube move be represented, but any position of the cube as well, by detailing the cube moves required to rotate the solved cube into that position. Indeed with the solved position as a starting point, there is a one-to-one correspondence between each of the legal positions of the Rubik's Cube and the elements of . The group operation is the composition of cube moves, corresponding to the result of performing one cube move after another.

In the mathematical field of combinatorics, given a collection of subsets of a set , an exact cover is a subcollection of such that each element in is contained in exactly one subset in . One says that each element in is covered by exactly one subset in . An exact cover is a kind of cover. It is non-deterministic polynomial time (NP) complete and has a variety of applications, ranging from the optimization of airline flight schedules, cloud computing, and electronic circuit design.

<span class="mw-page-title-main">Glossary of Sudoku</span>

This is a glossary of Sudoku terms and jargon. Sudoku with a 9×9 grid is assumed, unless otherwise noted.

Latin squares and quasigroups are equivalent mathematical objects, although the former has a combinatorial nature while the latter is more algebraic. The listing below will consider the examples of some very small orders, which is the side length of the square, or the number of elements in the equivalent quasigroup.

In mathematics, a combinatorial explosion is the rapid growth of the complexity of a problem due to how the combinatorics of the problem is affected by the input, constraints, and bounds of the problem. Combinatorial explosion is sometimes used to justify the intractability of certain problems. Examples of such problems include certain mathematical functions, the analysis of some puzzles and games, and some pathological examples which can be modelled as the Ackermann function.

<span class="mw-page-title-main">Sudoku solving algorithms</span> Algorithms to complete a sudoku

A standard Sudoku contains 81 cells, in a 9×9 grid, and has 9 boxes, each box being the intersection of the first, middle, or last 3 rows, and the first, middle, or last 3 columns. Each cell may contain a number from one to nine, and each number can only occur once in each row, column, and box. A Sudoku starts with some cells containing numbers (clues), and the goal is to solve the remaining cells. Proper Sudokus have one solution. Players and investigators use a wide range of computer algorithms to solve Sudokus, study their properties, and make new puzzles, including Sudokus with interesting symmetries and other properties.

Sudoku codes are non-linear forward error correcting codes following rules of sudoku puzzles designed for an erasure channel. Based on this model, the transmitter sends a sequence of all symbols of a solved sudoku. The receiver either receives a symbol correctly or an erasure symbol to indicate that the symbol was not received. The decoder gets a matrix with missing entries and uses the constraints of sudoku puzzles to reconstruct a limited amount of erased symbols.

<i>Taking Sudoku Seriously</i> 2011 book about sudoku

Taking Sudoku Seriously: The math behind the world's most popular pencil puzzle is a book on the mathematics of Sudoku. It was written by Jason Rosenhouse and Laura Taalman, and published in 2011 by the Oxford University Press. The Basic Library List Committee of the Mathematical Association of America has suggested its inclusion in undergraduate mathematics libraries. It was the 2012 winner of the PROSE Awards in the popular science and popular mathematics category.

References

  1. Lin, Keh Ying (2004), "Number of Sudokus", Journal of Recreational Mathematics, 33 (2): 120–24.
  2. "プログラミングパズル雑談コーナー". .ic-net.or.jp. Archived from the original on 12 October 2016. Retrieved 20 October 2013.
  3. "Minimum Sudoku". Csse.uwa.edu.au. Archived from the original on 26 November 2006. Retrieved 20 October 2013.
  4. 1 2 McGuire, G.; Tugemann, B.; Civario, G. (2014). "There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem". Experimental Mathematics. 23 (2): 190–217. arXiv: 1201.0749 . doi:10.1080/10586458.2013.870056.
  5. Taalman, Laura (2007), "Taking Sudoku seriously", Math Horizons, 15 (1): 5–9, doi:10.1080/10724117.2007.11974720, JSTOR   25678701, S2CID   126371771 . See in particular Figure 7, p. 7.
  6. Berthier, Denis (4 December 2009). "Unbiased Statistics of a CSP – A Controlled-Bias Generator" . Retrieved 4 December 2009.
  7. Berthier, Denis (November 2007). The Hidden Logic of Sudoku (Second, revised and extended ed.). Lulu.com. ISBN   978-1847534729.
  8. Yato, Takayuki; Seta, Takahiro (2003). "Complexity and Completeness of Finding Another Solution and Its Application to Puzzles". IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. E86-A (5): 1052–1060.
  9. 1 2 Lewis, R. A Guide to Graph Colouring: Algorithms and Applications. Springer International Publishers, 2015.
  10. 1 2 de Ruiter, Johan (15 March 2010). "On Jigsaw Sudoku Puzzles and Related Topics (Bachelor Thesis)" (PDF). Leiden Institute of Advanced Computer Science (LIACS).
  11. QSCGZ (Guenter Stertenbrink) (21 September 2003). "combinatorial question on 9x9 (rec.puzzles)". Google Discussiegroepen. Retrieved 20 October 2013.
  12. 1 2 Jarvis, Frazer (2 February 2008). "Sudoku enumeration problems". Frazer Jarvis's home page. University of Sheffield. Retrieved 20 October 2013.
  13. Felgenhauer, Bertram; Jarvis, Frazer (20 June 2005), Enumerating possible Sudoku grids (PDF).
  14. 1 2 Ed Russell and Frazer Jarvis (7 September 2005). "There are 5472730538 essentially different Sudoku grids... and the Sudoku symmetry group". Frazer Jarvis's home page. University of Sheffield. Retrieved 20 October 2013.
  15. Ed Russell, Frazer Jarvis (25 January 2006). "Mathematics of Sudoku II" (PDF).
  16. Adler, Aviv; Adler, Ilan (2008). "Fundamental Transformations of Sudoku Grids" (PDF). Mathematical Spectrum. 41 (1): 2–7.

Further reading