A Computational Complexity-Based Framework for Predicting the Difficulty of Sudoku Puzzles Using CSP-Based Symbolic Modeling and Constraint Metrics

This paper provides a logic-based method for the categorization of the puzzle difficulty levels of Sudoku using deterministic measures of computational complexity. Shifting from heuristic, statistical, or machine-based paradigms, the method presents four symbolic measures: constraint density metric (CDM), logical inference depth (LID), guessing complexity (GC), and constraint graph tightness (CGT). These are derived from the Constraint Satisfaction Problem theory and implemented using R programming without the application of data-driven inference. The new method assesses puzzle complexity based on pre-solving properties yielding consistent outputs that align with theoretical NP-completeness measures. Difficulty levels are grounded on strict numerical criteria, e.g., CDM over 700, LID 14 or higher, GC over 6, and CGT approaching 30, indicative of increased structural complexity. The method is compared with rule-based, backtracking, and solver-based methods using benchmarks and shown to run with linear time and space complexity O(n) compared with traditional methods with time and space complexity O(n²) or exponential growth O(2ⁿ). The method presents a reproducible, scalable method for analytically assessing puzzles and provides a formal, non-heuristic method for evaluating complexity within combinatorial logic systems. Received: 12 May 2025 | Revised: 29 July 2025 | Accepted: 17 August 2025 Conflicts of Interest The authors declare that they have no conflicts of interest to this work. Data Availability Statement The data that support the findings of this study are openly available in Kaggle at https://www.kaggle.com/datasets/bryanpark/sudoku. Author Contribution Statement Rajan Thangamani: Conceptualization, Methodology, Software, Formal analysis, Investigation, Resources, Data curation, Writing – original draft, Visualization, Project administration. Pallavi Regulagedda: Software, Validation, Resources, Writing – original draft, Writing – review & editing, Visualization, Supervision.