Application of the Malatya centre-based graph colouring method to sudoku and the 8-queen constraint satisfaction problems

Constraint satisfaction problems involve assigning appropriate values to variables under a set of constraints and pose significant computational challenges due to their large solution spaces. Sudoku and the Eight-Queens problem are among the most widely studied examples of this problem class because of their combinatorial structures and constraint-based nature. Although numerous approaches based on backtracking, constraint propagation, heuristic search, and optimization techniques have been developed, effectively managing the solution process, particularly as problem size increases, remains an active research topic. This thesis proposes a graph-based method that combines the Malatya Centrality Algorithm with a controlled graph coloring approach for solving Sudoku and Eight -Queens problems. In the proposed method, each problem is transformed into a graph structure in which cells are represented as nodes and constraint relationships are represented as edges. The centrality values of the nodes are calculated using the Malatya Centrality Algorithm and are subsequently employed to determine node priorities. The nodes are then ordered according to their centrality values, and solutions are obtained through a controlled graph coloring process. The proposed approach was evaluated on Sudoku problems with different difficulty levels and on Eight-Queens problems of various sizes. In addition, its performance was compared with several contemporary graph coloring algorithms. The experimental findings demonstrate that the centrality-based node prioritization mechanism effectively guides the graph coloring process and provides a practical approach for solving constraint satisfaction problems. Keywords : Constraint satisfaction problems, Malatya Centrality Algorithm, graph coloring, Sudoku, Eight-Queens problem, graph theory