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

Rajan Thangamani; Pallavi Regulagedda

doi:10.47852/bonviewJCCE52026137

Authors

Rajan Thangamani School of Computer Science and Engineering, Presidency University, India https://orcid.org/0009-0000-6602-162X
Pallavi Regulagedda School of Computer Science and Engineering, Presidency University, India

DOI:

https://doi.org/10.47852/bonviewJCCE52026137

Keywords:

Sudoku difficulty estimation, Constraint Satisfaction Problem (CSP), computational complexity, CSP-based symbolic modeling, constraint graph, R programming, NP-complete

Abstract

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.