A Group-theoretic Approach to Human Solving Strategies in Sudoku

Recently there has been a lot of interest in the mathematics of the popular game Sudoku. In a typical Sudoku puzzle, a number of initial clues are given, and the solver uses strategies to fill in the remaining clues to complete the board. A well-known open problem is, “How many initial clues are necessary for the puzzle to have a unique completion?” In this talk, we shift the focus of study from clues to what we call packets. A packet gives information about what entries can NOT be in a cell. Introducing packets gives rise to some interesting questions about Sudoku and its $4 imes4$ counterpart, Shidoku. One such question is ``what is the minimum number of packets needed to describe a puzzle with a unique completion?'' This question parallels the minimum clue question. Packets are also intimately related to the Boolean system of polynomial equations used to describe the constraints of a Sudoku puzzle. They can be used to more efficiently calculate a Gr"obner basis of the ideal generated by this system of equations. Packets are also inherently related to human methods for solving Sudoku puzzles. To emulate human solving strategies we introduce the idea of solving symmetries -- functions which manipulate a puzzle while maintaining the same solutions. We show that these solving symmetries form a group which acts on the set of Sudoku puzzles.