A Mathematical Hierarchy of Sudoku Puzzles and Its Computation by Boolean Groebner Bases

摘要

Sudoku, which is one of the most popular puzzles in the world, can be considered as a kind of combinatorial problem. Considering a Sudoku puzzle as a singleton set constraint, we define a purely mathematical hierarchy of Sudoku puzzles in terms of a Boolean polynomial ring. We also introduce a sufficiently practical symbolic computation method using Boolean Grobner bases to determine the hierarchy level of a given Sudoku puzzle. According to our experiments through our implementation, there exists a strong positive correlation between our hieraxchy and the levels of difficulty of Sudoku puzzles usually assigned by a heuristic analysis. Our mathematical hierarchy would be a universal tool which ensures the mathematical correctness of the level of a Sudoku puzzle given by a heuristic analysis.