Exploring the Uniqueness of Sudoku Puzzles Through Vertex Coloring by Katherine Blake ’19, Wednesday, February 13, 1 – 1:45 pm, Stetson Court Classroom 101, Mathematics Colloquium
Abstract: Originally called Number Place, Sudoku has taken the world by storm, appearing in popular newspapers such as the New York Times, video games and TV game shows, it has even inspiring its own World Championship. However, this beloved puzzle game contains hidden mathematical problems. In this talk, we will explore how this logic based, combinatorial placement puzzle can be turned into a vertex coloring problem in graph theory along with other implications that arise from this understanding.
First, we will think about the number of ways of completing a partially constructed Sudoku puzzle, which can be seen as a partial proper coloring of a graph.
Second, we will conclude with analyzing the uniqueness of Sudoku puzzles. Specifically those consisting of a Latin square of rank n with an additional constraint that no number can appear more than once in the 3×3 subregions of the puzzle, while also finding an upper bound for Sudoku puzzles of rank n.