A Linear Time Pattern Based Algorithm for N-Queens Problem

Basit Öğe Kaydı
dc.authoridUnver, Halil Murat/0000-0001-9959-8425
dc.authoridERGUZEN, ATILLA/0000-0003-4562-2578
dc.contributor.authorKarabulut, Bergen
dc.contributor.authorErguzen, Atilla
dc.contributor.authorUnver, Halil Murat
dc.date.accessioned2025-01-21T16:33:49Z
dc.date.available2025-01-21T16:33:49Z
dc.date.issued2022
dc.departmentKırıkkale Üniversitesi
dc.description.abstractThe n-queens problem is the placing of n number of queens on an nxn chessboard so that no two queens attack each other. This problem is important due to various usage fields such as VLSI testing, traffic control job scheduling, data routing, dead-lock or blockage prevention, digital image processing and parallel memory storage schemes mentioned in the literature. Besides, this problem has been used as a benchmark for developing new artificial intelligence search techniques. However, it is known that backtracking algorithms, one of the most frequently used algorithms to solve this problem, cannot produce all solutions in large n values due to the exponentially growing time complexity. Therefore, various methods have been proposed for producing one or more solutions, not all solutions for each n value. In this study, a pattern based approach that produces at least one unique solution for all n values (n>3) was detected. By using this pattern, a new algorithm that produces at least one unique solution for even very large n values in linear time was developed. The developed algorithm with.(n) time complexity produces quite faster solution to n-queens problem and even in some values, this algorithm produces (n-1)/2 unique solutions in linear time.
dc.identifier.doi10.2339/politeknik.762967
dc.identifier.endpage622
dc.identifier.issn1302-0900
dc.identifier.issn2147-9429
dc.identifier.issue2
dc.identifier.startpage615
dc.identifier.trdizinid1235270
dc.identifier.urihttps://doi.org/10.2339/politeknik.762967
dc.identifier.urihttps://search.trdizin.gov.tr/tr/yayin/detay1235270
dc.identifier.urihttps://hdl.handle.net/20.500.12587/23864
dc.identifier.volume25
dc.identifier.wosWOS:001001848800016
dc.identifier.wosqualityN/A
dc.indekslendigikaynakWeb of Science
dc.indekslendigikaynakTR-Dizin
dc.language.isoen
dc.publisherGazi Univ
dc.relation.ispartofJournal of Polytechnic-Politeknik Dergisi
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanı
dc.rightsinfo:eu-repo/semantics/openAccess
dc.snmzKA_20241229
dc.subjectN-queens problem; constraint satisfaction problem; NP-hard; NP-complete; optimization problem
dc.titleA Linear Time Pattern Based Algorithm for N-Queens Problem
dc.typeArticle

Dosyalar

Orijinal paket
Listeleniyor 1 - 1 / 1
Küçük Resim
İsim:
Tam Metin/Full Text
Boyut:
541.4 KB
Biçim:
Adobe Portable Document Format
İndir

Koleksiyon

WOS İndeksli Yayınlar Koleksiyonu
Makale Koleksiyonu
TR-Dizin İndeksli Yayınlar Koleksiyonu