Portland State University. Department of Mathematics and Statistics
Date of Award
Master of Science (M.S.) in Mathematics
Mathematics and Statistics
Graph theory, Sudoku, Combinatorial analysis
A sudoku puzzle is most commonly a 9 × 9 grid of 3 × 3 boxes wherein the puzzle player writes the numbers 1 - 9 with no repetition in any row, column, or box. We generalize the notion of the n2 × n2 sudoku grid for all n ϵ Z ≥2 and codify the empty sudoku board as a graph. In the main section of this paper we prove that sudoku boards and sudoku graphs exist for all such n we prove the equivalence of 's construction using unions and products of graphs to the definition of the sudoku graph; we show that sudoku graphs are Cayley graphs for the direct product group Zn × Zn × Zn ×|Zn; and we find the automorphism group of the sudoku graph. In the subsequent section, we find and prove several graph theoretic properties for this class of graphs, and we offer some conjectures on these and other properties.
Oddson, Kyle, "Counting and Coloring Sudoku Graphs" (2019). Mathematics and Statistics Dissertations, Theses, and Final Project Papers. 1.