Optimizing Sudoku Solvers from Backtracking to CSP Techniques

Abstract

This study compares a basic backtracking Sudoku solver with an optimized solver using constraint satisfaction problem (CSP) techniques. The optimized version combines the Minimum Remaining Values (MRV) heuristic with candidate-domain pruning to guide search and avoid redundant attempts.

Across seven puzzle difficulty levels, the optimized solver achieved speedups ranging from approximately 1.5× to 15× over the baseline. The results also suggest that Sudoku difficulty is not determined solely by the number of given digits; their arrangement matters as well.