  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.
