Computer Science – Artificial Intelligence
Scientific paper
2009-03-09
Computer Science
Artificial Intelligence
6 pages, 2 figures
Scientific paper
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.
No associations
LandOfFree
Heuristic Reasoning on Graph and Game Complexity of Sudoku does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Heuristic Reasoning on Graph and Game Complexity of Sudoku, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Heuristic Reasoning on Graph and Game Complexity of Sudoku will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-186477