Yakut, SelmanKaragoz, Erkan2026-04-042026-04-0420252169-3536https://doi.org/10.1109/ACCESS.2025.3622191https://hdl.handle.net/11616/109133The sudoku puzzle, an NP-complete problem, presents significant computational challenges due to its constrained structure and vast solution space. While widely studied in artificial intelligence and optimization, existing methods often struggle with scalability and varying difficulty levels. This study introduces a novel, graph coloring-based approach leveraging the Malatya centrality algorithm to efficiently solve sudoku puzzles. By transforming the sudoku board into a graph, we compute node centrality values to guide the coloring process, where distinct color clusters correspond to numerical solutions. Our method was rigorously evaluated on datasets consisting of up to 1,000,000 puzzles and achieved 100% accuracy. It has achieved successful results when compared to other methods across various difficulty levels (easy, medium, and hard). This represents a significant advancement over traditional techniques (e.g., genetic algorithms, constraint propagation) and classical graph colouring methods (Brute Force, DSatur, Welsh Powell, etc.).The Malatya centrality algorithm's robust-ness stems from its centrality-driven prioritization, enabling optimal resource allocation during search. Furthermore, we demonstrate its potential for broader applications, including complex network analysis and combinatorial optimization. This work not only advances sudoku-solving methodologies but also provides a framework for integrating graph-theoretic centrality measures into NP-complete problem domains. Future directions include adaptations to real-world problems such as scheduling, bioinformatics, and social network analysis.eninfo:eu-repo/semantics/openAccessMachine learning algorithmsHeuristic algorithmsBacktrackingOptimizationGenetic algorithmsSearch problemsForceNP-complete problemGraph theoryEducationCentrality-driven heuristicsgraph coloring for sudokularge-scale sudoku optimizationMalatya centrality algorithmNP-complete problem solvingArticle1318273718275010.1109/ACCESS.2025.36221912-s2.0-105019621047Q1WOS:001605379400006Q20009-0002-8758-88490000-0002-0649-1993