PIMS - UVic Discrete Math Seminar: Kate Nimegeers

If a tricky devil challenged you to complete a Sudoku puzzle of their design, what restrictions could you place on their design to guarantee it was impossible for them to thwart your attempts? More specifically, if you could dictate exactly how many times that devil could use each symbol or pre-fill any one row, column, or box, could you safely bet that their deviously designed puzzle was still completable? This notion of seeking out guaranteed completability conditions for Sudoku drives the discussion as we delve into various graph and matrix representations of the Sudoku, explore relaxed notions of completability such as fractional completability, and use these tools to approach an answer. Due to the ongoing nature of this research, this talk is designed to serve as an introduction to the machinery of the argument being employed but does not conclude with a definitive answer.