Using Graphs to Derive CSP Heuristics and its Application to Sudoku

This paper presents a general purpose methodology to derive new heuristics for constraint satisfaction problems using the information contained in an auxiliary graph. The method is then applied to implement a powerful heuristic for Sudoku which is `almost perfect´ in the sense that a depth first search procedure needs very few backtracks to solve the 16×16 puzzle. The heuristic uses a least-constraining tie break for variable ordering, something very unusual in CSP domains. The paper also presents a minimal set of logical rules which the authors conjecture to solve all 9×9 Sudoku grids with unique solution with just one level of recursion at most.