A Graph-Theoretic Solution to NP-Complete Sudoku Puzzles: Malatya Centrality for Large-Scale Optimization

Basit Öğe Kaydı
dc.contributor.authorYakut, Selman
dc.contributor.authorKaragoz, Erkan
dc.date.accessioned2026-04-04T13:33:24Z
dc.date.available2026-04-04T13:33:24Z
dc.date.issued2025
dc.departmentİnönü Üniversitesi
dc.description.abstractThe 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.
dc.description.sponsorshipInonu University Scientific Research Projects Unit [FBA-2025-4172]
dc.description.sponsorshipThis work was supported by the Inonu University Scientific Research Projects Unit under Project FBA-2025-4172.
dc.identifier.doi10.1109/ACCESS.2025.3622191
dc.identifier.endpage182750
dc.identifier.issn2169-3536
dc.identifier.orcid0009-0002-8758-8849
dc.identifier.orcid0000-0002-0649-1993
dc.identifier.scopus2-s2.0-105019621047
dc.identifier.scopusqualityQ1
dc.identifier.startpage182737
dc.identifier.urihttps://doi.org/10.1109/ACCESS.2025.3622191
dc.identifier.urihttps://hdl.handle.net/11616/109133
dc.identifier.volume13
dc.identifier.wosWOS:001605379400006
dc.identifier.wosqualityQ2
dc.indekslendigikaynakWeb of Science
dc.indekslendigikaynakScopus
dc.language.isoen
dc.publisherIeee-Inst Electrical Electronics Engineers Inc
dc.relation.ispartofIEEE Access
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanı
dc.rightsinfo:eu-repo/semantics/openAccess
dc.snmzKA_WOS_20250329
dc.subjectMachine learning algorithms
dc.subjectHeuristic algorithms
dc.subjectBacktracking
dc.subjectOptimization
dc.subjectGenetic algorithms
dc.subjectSearch problems
dc.subjectForce
dc.subjectNP-complete problem
dc.subjectGraph theory
dc.subjectEducation
dc.subjectCentrality-driven heuristics
dc.subjectgraph coloring for sudoku
dc.subjectlarge-scale sudoku optimization
dc.subjectMalatya centrality algorithm
dc.subjectNP-complete problem solving
dc.titleA Graph-Theoretic Solution to NP-Complete Sudoku Puzzles: Malatya Centrality for Large-Scale Optimization
dc.typeArticle

Dosyalar

Koleksiyon

WoS İndeksli Yayınlar Koleksiyonu
Scopus İndeksli Yayınlar Koleksiyonu