Articulo Del Sudoku

Sudoku Squares and Chromatic Polynomials
Agnes M. Herzberg and M. Ram Murty November 27, 2012
The Sudoku puzzle has become a very popular puzzle that many newspapers carry as a daily feature. The puzzle consist of a 9 × 9 grid have a number from 1 to 9. One is then required to complete the grid in such a way that every row, every column, and every one of the nine 3 x 3 sub-grids contain thedigits from 1 to 9 exactly once. the sub-grids are shown in Figure ??. Recall that a latin square of rank n is an n × n aray consting of the numbers such that each row and column has all the numbers from 1 to n. In a particular, every Sudoku square is a latin square for rank 9, but not conversely because of the condition on the nine 3 × 3 sub-grids. Figure ?? (taken from [?])shows one such puzzlewith seventeen entries given.

Figure 1: A Sudoku grid

Figure 2: A Sudoku puzzle with 17 entries.

For anyone trying to slove a Sudoku puzzle, several questions arise naturally. For a given puzzle, does a solution exist? Its the solution exist, is unique? If the solution is not unique, how many solutions are there? Moreover, is there a system atic way of determining all the solutions? How M.Herzberg is professor eneritus of mathematics at Quenn’s University, Canada. Her email address is many puzzles are there with a unique solution? What is the minimum number of entries that can herzberg@post.queensu.ca. M Ram Murty is professor of mathematics at Queen’s Uni- be specified in a single puzzle in order to ensure versity, Canada. His email is address murty@mas.com.ca. a unique solution?For instance, Figure ?? shows Research of both authors is partially supported by Natural Sciences and Engineering Research Council (NSERC) that the minimum is a most 17. (we leave it to grants. the reader that the puzzle in Figure ?? has a 1

using (i, j) with 0 ≤ i, j ≤ n2 − 1. Then, (i, j) and (i , j ) are adjacent if i = i or j = j or [i/n] = [i /n]and[j/n] = [j /n] , where now [·] indicatesthe greatest integer function. That is, [x] means the greatest integer which is less than or equal to x. Recall that a graph is called regular if the degree of every vertex is the same. An easy computation shows that Xn is a regular graph with each vertex having degree 3n22n1 = (3n + 1)(n1). In the case n = 3, X3 is 20-regular and in case n = 2, X2 is 7-regular. The number of ways of coloring agraph of G with colors is well known to be a polynomial in of degree equal to the number of vertices of G. Our first theorem is that given a partial coloring C of G, the number of ways of completing the coloring to obtain a proper coloring using λ colors is also a Chromatic Polynomials polynomial in λ, provided that λ is greater than For the convenience of the reader, we recall the or equal to thenumber of colors used in C. More vertices notion of proper coloring of a graph. A precisely, this is stated as Theorem 1. λ-coloring of a graph G is a map f from the vertex Teorem 1. Let G be a finite graph with v vertices. set of G to 1, 2, ..., λ. Such a map is called proper Let C be a partial proper coloring of t vertices of G coloring if f (x) = f (y) whenever x and y are adjausing d0 colors. LetρG,C (λ) be the number of ways cent in G. the minimal number of colors required to of completing this coloring using colors to obtain a properly color the vertices of a graphic G is called proper coloring of G. Then, ρG,C (λ) is a monic Chromatic number of G and denoted X(G). It is polynomial (inλ ) with integer coefficients of degree then not difficult to see that the Sudoku puzzle is v - t for λ ≥ d0. really a coloring problem. Indeed, we associate a graph with the 9 × 9 Sudoku grid as follows. The We will give two proofs of this theorem. The graph will have 81 vertices with each vertex cor- most direct proof uses the theory of partially orresponding cells in the grid. Two distinct vertices dered sets and M¨bius functions, which we briefly o will be adjacent if a only if the corresponding...