Playing Fair at Sudoku

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
PDF
23 pages
0 downs
4 views
Share
Description
Playing Fair at Sudoku. Joshua Cooper USC Department of Mathematics. 1. 3. 7. 8. 9. 7. 4. 8. 5. 9. 2. 8. 1. 6. 6. 8. 7. 1. 2. 8. 4. 7. 1. 8. 1. 3. 7. 5. Rules: Place the numbers 1 through 9 in the 81 boxes, but do not let any number
Transcript
Playing Fair at SudokuJoshua CooperUSC Department of Mathematics1378974859281668712847181375Rules: Place the numbers 1 through 9 in the 81 boxes, but do not let any numberappear twice in any row, column, or 33 “box”.You start with a subset of the cells labeled, and try to finish it.65428326159924761347533129465875394596137223695844296COLUMNSTACK13978BOX74BAND1654397288578326145992816924857613ROW479528136GIVEN6871231294658784CELL6587132947159618437281375237695841BOARDPUZZLE841372965A Sudoku puzzle designer has two main tasks: 1. Come up with a board to use as the solution state. 2. Designate some subset of the board’s squares as the initially exposed numbers (“givens”).For example:We’re going to focus on task #1: How to choose a “fair” Sudoku board?For a Sudoku puzzle, i.e., a set of givens, to be “fair”, it must have two properties: 1. It has a solution. (Solvability) 2. There is only one solution. (Uniqueness)Question: What is the fewest number of givens in a fair puzzle?Possible solution (“Brute Force”): 1. Enumerate all possible sets of givens. 2. Check each one to see if it is solvable. 3. Check the solvable ones to see if they are unique. 4. Count up the number of givens in the smallest uniquely solvable puzzle, and output the minimum such number.Why Brute Force Is Impractical: 1. Enumerate all possible sets of givens.With 81 cells, there are 281 ≈ 2.4 ∙ 1024 sets of cells one could fill in.Actually, the situation is even worse, because we have 9 options for the contents ofeach cell. That means a total numberof possible sets of givens.1 + 9 ∙ 81 + 92 ∙ () + 93 ∙ ()+ … + 980 ∙ () + 981 ∙ ()81818181238180“81 choose 3” = the number of ways to choose 3 objects from a collection of 81Why Brute Force Is Impractical: 1. Enumerate all possible sets of givens.With 81 cells, there are 281 ≈ 2.4 ∙ 1024 sets of cells one could fill in.Actually, the situation is even worse, because we have 9 options for the contents ofeach cell. That means a total numberof possible sets of givens.1 + 9 ∙ 81 + 92 ∙ () + 93 ∙ ()+ … + 980 ∙ () + 981 ∙ ()81818181238180“N choose K” = the number of ways to choose K objects from a collection of NWhy Brute Force Is Impractical: 1. Enumerate all possible sets of givens…With 81 cells, there are 281≈ 2.4 ∙ 1024 sets of cells one could fill in.Actually, the situation is much worse, because we have 9 options for the contents ofeach cell. That means a total numberof possible sets of givens.1 + 9 ∙ 81 + 92 ∙ () + 93 ∙ ()+ … + 980 ∙ () + 981 ∙ ()81818181238180By the Binomial Theorem,which is approximately the number of atoms in the observable universe. Let’s be a little smarter about this… 1. Enumerate all sets of 81 givens, and if a uniquely satisfiable puzzle is found, enumerate all sets of 80 givens, and if a uniquely satisfiable puzzle is found, enumerate all sets of 79 givens…In fact, we can start much lower than 81, since there are many uniquely satisfiablepuzzles known with fewer than 81 givens.Indeed, there are uniquely satisfiable puzzles known which have only 17 givens.14254783193425186Gordon Royle has compiled a list of 49151 (!) inequivalent ones at:http://mapleta.maths.uwa.edu.au/~gordon/sudokumin.php1. Permuting the rows and columns of each band/stack (X 3!6)2. Permuting bands I, II, and III, and and stacks A, B, and C (X 3!2)IIIIIIABCWhat does it mean for two Sudoku boards/puzzles to be equivalent?Two boards are considered equivalent if it is possible to transform one into the otherby a sequence of operations of the form:3. Permuting the numbers/colors (X 9!)This generates a group of 3,359,232different possible operations.So, start with 16 givens: 1. Enumerate all sets of 16 givens…How many such sets are there?81916 ∙ () ≈6.22 ∙ 103116It would be silly to look at all of these, though: 1. We can rule out anything that has two of the same symbol in any column, row, or box. 2. Once we examine one, we don’t have to look at all the ones equivalent to it.By what factor does each of these reduce the number of sets to examine?Effect of #1: This is nearly impossible to compute exactly, so we Poissonize: pretendas if each cell “turns on” with probability 16/81, and then chooses a number 1 through9 uniformly at random. Probability that two cells in the same row get turned on and set to the same number == Pr(exactly 2 cells get turned on and they are set to the same number) + Pr(exactly 3 cells get turned on and at least 2 are set to the same number) + Pr(exactly 9 cells get turned on and at least 2 are set to the same number)= 0.135469925561528…Thanks, SAGE!Probability that no two cells in the same row get turned on and set to the same number:= 1 - 0.135469925561528… = 0.864530074438472…Probability that no two cells in anyrow get turned on and set to the same number:= (0.864530074438472…)9 = 0.269786958… Probability that no two cells in anyrow, column, or box get turned on and set to the same number:≈ 0.269786958…3 = 0.0196364445…Approximate total number of inequivalent configurations of 16 non-conflicting givens:6.22 ∙ 1031 ∙ 0.0196364445 / 3359232 ≈ 3.64 × 1023Still way too big.Even if we could enumerate all of these, and even if we knew how to generate a list ofone representative of each equivalence class (= orbit under the Sudoku group)…}2. Check each one to see if it is solvable.3. Check the solvable ones to see if they are unique.Use backtracking.What about lower bounds?State of the art: At least 8 givens are needed.Proof: Suppose fewer givens are provided. Then at least two numbers do not appearamong the givens. Those two numbers could be switched in any completion of theboard, so the solution is not unique.Theorem (C’ tomorrow?): At least 9 givens are needed.Proof: Suppose only 8 givens are provided. First of all, note that no two of themare the same number, since otherwise there would be at least two numbers notappearing among the givens. Then, in any completion of the board, those twonumbers could be swapped.Next, set up a bipartite graph with the stack numbers and the band numbers as thecolor classes:STACK 1BAND 1Now, put an edge from STACK A to BAND B if the box shared by them has a given in it.STACK 2BAND 2STACK 3BAND 3When is there a perfect matching?Definition. A perfect matching in a bipartite graph is a set of edges that connecteach element of one color class to exactly one element of the other.Theorem (Hall 1935): There is a perfect matching if and only if every subset ofvertices in one color class has at least as many neighbors in the other color classas its size.So, if there isn’t a perfect matching, then there has to be either (a) one band containingno givens, (b) two bands with givens in only one stack, or (c) three bands with givensin only two stacks.(a)(b)(c)Permute the rowsin the bottom band.Permute the columnsin the left-hand band.Not so easy.Case 1Case 2Since all four black boxes contain at leasttwo givens, and there are only 8 givens inall, the gray square is empty as well. Swap these two columns.Case 2Since all four black boxes contain at leasttwo givens, and there are only 8 givens inall, the gray square is empty as well. In fact, each black square has to haveexactly two givens in it. So the picture isnow this.Case 2Since all four black boxes contain at leasttwo givens, and there are only 8 givens inall, the gray square is empty as well. By permuting columns and rows, we caneven assume more. There are only 34 = 81 choices for whereThe remaining four givens go.If there is a perfect matching, then we may permute rows, columns, stacks, and bandsso that the result looks like:Out of the remaining 59 cells, 5 givens must be placed.Each bracket must contain at least one given.At least one of the boxes is empty, and there are essentially two ways to choosewhich one it is.If there is a perfect matching, then we may permute rows, columns, stacks, and bandsso that the result looks like:Out of the remaining 59 cells, 5 givens must be placed.Each bracket must contain at least one given.At least one of the boxes is empty, and there are essentially two ways to choosewhich one it is.How to test if a puzzle is fair?Define a graph Sud on the set of cells with a complete subgraph in eachrow, column, and box.Definition. A graph G is said to be k-colorable if it is possible to assign k colors to thevertices in such a way that no edge has both its vertices colored the same.Definition. The chromatic number χ(G) of a graph G is the smallest integer k sothat G is k-colorable.Definition. A graph G is said to be uniquely colorable if, other than permuting thecolors, there is only one coloring of G with exactly χ(G) colors.Uniquely ColorableNot Uniquely ColorableTheorem. At least 9 givens are required if, for all sets S of 8 givens, the graph obtainedfrom Sud by adding a complete graph on the vertex set corresponding to S is notuniquely colorable.Proof. A coloring of Sud is exactly the same thing as a solution to the puzzle. Whena complete graph is added, we are simply requiring that the 8 givens be assigneddifferent colors. We may assign numbers uniquely to the cells exactly when the graphis uniquely colorable.The gap between 9 and 17 is still huge!Open Problems:1. Close the gap!2. How many fair puzzles are there with k givens, 9 ≤ k ≤ 81?3. What about the “generalized Sudoku board”? For example, 16X16:Thanks!P.S.If you are interested in doing some research, contact me at cooper@math.sc.edu.
Related Search
Similar documents

View more...