Kate Nimegeers

Topic

Pseudoku: A Sudoku Adjacency Algebra and Fractional Completion Threshold

Department of Mathematics and Statistics

Date & location

• Monday, February 26, 2024
• 10:30 A.M.
• David Strong Building, Room C124

Examining Committee

Supervisory Committee

• Dr. Peter Dukes, Department of Mathematics and Statistics, University of Victoria (Supervisor)
• Dr. Natasha Morrison, Department of Mathematics and Statistics, UVic (Member)

External Examiner

• Dr. Karen Meagher, Department of Mathematics and Statistics, University of Regina

Chair of Oral Examination

• Prof. Martin Segger, Department of Art History and Visual Studies, UVic

Abstract

The standard Sudoku puzzle is an 9 × 9 grid partitioned into 3 × 3 square boxes and partially filled with symbols from the set {1, 2, ..., 9}, with the goal of the puzzle being to complete the grid so that each symbol appears once and only once in each row, column, and box. We study generalized Sudoku puzzles, set on an n × n grid with cells partitioned into n boxes (sometimes called cages) of height h and width w such that hw = n. Throughout this work, these generalized Sudoku are referred to as (h,w)-Sudoku when h and w are significant, but as simply Sudoku otherwise. The goal of solving a partially filled (h,w)-Sudoku puzzle remains the same; complete the Sudoku by assigning placements in the grid to each symbol from {1, 2, ..., hw} so that each symbol appears once and only once in each row, column, and box.

This thesis is specifically concerned with establishing conditions which guarantee a fractional Sudoku completion. A fractional Sudoku completion is an assignment of a set of weights to each symbol-cell incidence, representing the proportion of the symbol for that specific cell. The total weight of symbols for each cell must sum to one, and the sum of the weights for each symbol must be exactly one across the cells from each row, column, and box. These conditions still require a balanced distribution of symbols throughout the grid, but with considerably more flexibility than the typical Sudoku conditions.

In order to apply graph theoretic techniques to the problem, we develop a 4-partite graph representation, G_P, for a partial Sudoku, P. The 4 parts correspond to the rows, columns, symbols, and boxes of P, and the edges of G_P indicate the conditions for a completed Sudoku that remain unsatisfied in P. We then introduce the concept of a tile: a 4-vertex subgraph of G_P, which represents a valid symbol placement in P. Completing P is equivalent to decomposing the edges of G_P into these tiles. We then use an edge-tile inclusion matrix to relate the existence of such a decomposition to the existence of an solution vector with {0, 1} entries for a specific linear system. It is here that we move to the fractional setting through a relaxation of what constitutes an acceptable solution to the linear system - specifically, we are satisfied with solution vectors for which all entries are non-negative.

To find conditions that guarantee such a solution exists we study the Gram matrix of the edge-tile inclusion matrix for the empty (h,w)-Sudoku, denoted M. We show that M is symmetric and is indexed by edges which represent all of the conditions for any (h,w)-Sudoku, later leveraging the inherent symmetry of equivalence relations in these conditions to establish a Sudoku adjacency algebra which contains M. This allows us to explicitly construct a generalized inverse for M. This generalized inverse, along with some applied perturbation theory, is used to show that given large enough h and w, the linear system for any sufficiently sparse partial (h,w)-Sudoku is a minor perturbation of the linear system for the empty (h,w)-Sudoku, and therefore allows a fractional completion.

After presenting this main result, we take a brief detour to consider the unique case of Sudoku puzzles with thin boxes, examining how fixing the box width variable w while allowing height h to grow asymptotically influences the density conditions necessary for fractional completion. We also give an overview of our exploratory use of the Schur complement for matrix decomposition. Although this method didn’t directly feed into our primary results, it was instrumental in the discovery of the equivalence relations we used to construct our Sudoku adjacency algebra. Finally, we explore the potential applicability of our methodologies to certain Sudoku variants and acknowledge the limitations inherent in our approach.

In the appendices, we provide additional resources that complement the main body of our work. Appendix A presents a series of interactive and educational activities designed to introduce students to the basic principles of Latin squares in a fun spy-themed setting. In Appendix B, we give a factorization of the Sudoku matrix M and its eigenvectors as Kronecker products for readers who wish to more directly compare our methodology to algebraic graph theory work done on Sudoku by other researchers.