Malatya merkezilik tabanlı graf renklendirme yönteminin sudoku ve 8 vezir kısıt tatmin problemlerine uygulanması

Kısıt tatmin problemleri, bir takım kısıtlar altında değişkenlere uygun olan değerlerin atanmasının amaçlandığı ve çözüm uzaylarının karmaşıklığı ve büyüklüğünden dolayı ciddi hesaplama zorlukları barındıran problemlerdir. Sudoku ve Sekiz-Vezir problemleri, içerdikleri kısıtlar ve kombinatoryal yapı nedeniyle bu problem sınıfının en bilinen ve çok incelenen önemli örnekleri arasında yer almaktadır. Bu problemlerin çözüm çalışmalarında geri izleme, kısıt yayılımı, sezgisel arama ve optimizasyon temelli oldukça fazla yöntem tasarlanmış ve geliştirilmiş olmasına karşın, özellikle problemin boyutundaki büyümeler ile çözüm adımlarının etkili bir biçimde yönetilmesi güncelliğini koruyan bir araştırma alanı olarak önemini sürdürmektedir. Bu tezde, Önemli Kısıt tatmin problemlerinden olan Sudoku ve Sekiz-Vezir problemlerinin çözümünde Malatya Merkezilik Algoritması ile graf teorisine dayalı ve kontrollü graf renklendirme içeren bir yöntem geliştirilmiştir. Önerilen yöntemde problemler birer graf yapısı olarak modellenmiş, problemde yer alan kutucuklar birer düğüm ve bu düğümler arasında yer alan kısıtlar gözetilerek kenar bağlantıları tanımlanmıştır. Üretilen graf yapılarının üzerinde Malatya Merkezilik Algoritması uygulanarak düğümlerin merkezilik değerleri hesaplanmış ve bu değerler düğümlerin önceliklerinin belirlenmesinde kullanılmıştır. Ardından düğümler elde edilen merkezilik değerleri gözetilerek sıralanmış ve kontrollü bir biçimde renklendirme süreci yürütülmüş problem çözümleri elde edilmiştir. Önerilen yaklaşım, 1.000.000 adet Sudoku bulmacasına kadar ve farklı zorluk seviyelerinde diğer graf renklendirme algoritmaları ile karşılaştırılmış, diğer bir çalışmada ise yaklaşım 64x64 boyutunda kadar büyütülen Sekiz-Vezir problemleri ele alınarak güncel graf renklendirme algoritmaları ile karşılaştırılmış ve incelenmiştir. Sonuçlar göz önüne alındığında, Malatya Merkezilik algoritması düğüm merkezilik hesabına dayalı önceliklendirme mekanizmasının graf renklendirme sürecinin yönlendirilmesinde etkili sonuçlar ürettiğini ve kısıt tatmin problemlerinin çözümüne yönelik uygulanabilir etkili bir yaklaşım sunduğunu göstermektedir. Anahtar Kelimeler: Grafik renklendirme, Grafik teorisi, Kısıt tatmin problemleri, Malatya Merkezlilik Algoritması, Sekiz-vezir problemi, Sudoku