Malatya Centrality Algorithm and Graph Colouring Based Effective and Efficient Eight Queen Problem Solution Method
Küçük Resim Yok
Tarih
2025
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Institute of Electrical and Electronics Engineers Inc.
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
The eight queens problem, a classic constraint satisfaction problem in computer science, is a combinatorial problem that has been studied since the 19th century with applications to algorithm development, mathematical thinking and artificial intelligence. Briefly, the problem is to place eight queens on a chessboard in such a way that they do not threaten each other. Until today, the problem has been addressed with heuristic or brute force algorithms and now with artificial intelligence applications. Since the NP-Hard nature of the problem requires a large number of combinations to be tried, it is important to produce efficient algorithms. In this paper, we propose a method that solves the problem based on graph theory and centrality calculus. Firstly, each box on the chessboard is defined as a node. Considering the constraints of the problem, edge connections are established between these nodes and modelled as a graph. On this graph structure, the centrality calculations of the nodes were made with the Malatya Centrality algorithm. Then, starting from the node with the highest centrality value. The queens (colours) were placed in a regular way. As an alternative to classical methods, this method offers a perspective based on graph theory and graph colouring and creates a more systematic approach to queen placement. © 2025 IEEE.
Açıklama
9th International Artificial Intelligence and Data Processing Symposium, IDAP 2025 -- 6 September 2025 through 7 September 2025 -- Malatya -- 215321
Anahtar Kelimeler
Eight queen problem, Graph colouring, Malatya centrality algorithm, NP-Hard problems
Kaynak
9th International Artificial Intelligence and Data Processing Symposium, IDAP 2025
WoS Q Değeri
Scopus Q Değeri
N/A
