2009/03/09 by Zhe Chen, Chen, Zhe · 1 citation
Engineering · #Artificial Intelligence (cs.AI) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Symbolic Computation (cs.SC) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.0903.1659
openalex publication_date 2009/03/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Sudoku puzzle has achieved worldwide popularity recently, and attracted great attention of the computational intelligence community. Sudoku is always considered as Satisfiability Problem or Constraint Satisfaction Problem. In this paper, we propose to focus on the essential graph structure underlying the Sudoku puzzle. First, we formalize Sudoku as a graph. Then a solving algorithm based on heuristic reasoning on the graph is proposed. The related r-Reduction theorem, inference theorem and their properties are proved, providing the formal basis for developments of Sudoku solving systems. In order to evaluate the difficulty levels of puzzles, a quantitative measurement of the complexity level of Sudoku puzzles based on the graph structure and information theory is proposed. Experimental results show that all the puzzles can be solved fast using the proposed heuristic reasoning, and that the proposed game complexity metrics can discriminate difficulty levels of puzzles perfectly.