A Linear Time Pattern Based Algorithm for N-Queens Problem
Authors : Bergen KARABULUT, Atilla ERGÜZEN, Halil Murat ÜNVER
Pages : 615-622
Doi:10.2339/politeknik.762967
View : 15 | Download : 4
Publication Date : 2022-06-01
Article Type : Research
Abstract :N-vezir problemi, nxn boyutundaki bir satranç tahtasına n adet vezirin herhangi iki vezir birbirine saldırmayacak şekilde yerleştirilmesidir. Bu problem literatürde değinilen VLSI testi, trafik kontrol işi planlama, veri yönlendirme, ölümcül kilitlenme ya da tıkanıklık önleme, dijital görüntü işleme ve paralel bellek depolama şemaları gibi çeşitli kullanım alanlarından dolayı önemlidir. Ayrıca bu problem, yeni yapay zekâ arama tekniklerinin geliştirilmesi için bir referans noktası olarak kullanılmaktadır. Fakat bilindiği üzere bu problemin çözümde sıklıkla kullanılan geri-izleme algoritmaları, katlanarak büyüyen zaman karmaşıklığından dolayı büyük n değerleri için tüm çözümleri üretememektedir. Bu nedenle, her bir n değeri için tüm çözümleri bulmak yerine bir veya daha fazla çözüm üretebilmek için çeşitli yöntemler önerilmiştir. Bu çalışmada, tüm n değerleri (n>3) için en az bir tane eşsiz çözüm üreten bir örüntü tespit edilmiştir. Bu örüntü kullanılarak, çok büyük n değerlerinde bile lineer zamanda en az bir tane eşsiz çözüm üreten yeni bir algoritma geliştirilmiştir. O(n) zaman karmaşıklığı ile geliştirilen algoritma, n-vezir problemine oldukça hızlı çözüm üretmektedir ve hatta bazı değerler için lineer zamanda (n-1)/2 adet eşsiz çözüm üretmektedir.Keywords : N-vezir Problemi, NP-hard, NP-complete, kısıt sağlama problemi, optimizasyon problemi