Sudoku bulmacasının kuyruk liste veri yapısı tabanlı paralel önce-derine arama yöntemiyle çözülmesi

Abstract

NP-Complete bir oyun olan sudoku bulmacası dünya genelinde oldukça ilgi gören bir bulmaca çeşididir. Sudokuya olan ilginin yoğunluğu ilk kez 2006’da şampiyona düzenlenmesine neden olmuştur. Sayıların dizilim ve kullanılan sayı miktarına bağlı olarak farklı zorluk seviyelerinde oluşturulabilen sudokunun kolay seviyeleri klasik kağıt kalem ile basitçe çözülebilirken, zor seviyesindeki sudoku bulmacaları için çeşitli deneme yanılma yöntemleri geliştirilmiştir. Bu tez çalışmasında sudoku bulmacasının kuyruk liste veri yapısı tabanlı paralel önce derine arama yöntemi ile çözülmesi amaçlanmıştır. Paralelleştirme yapılırken farklı sayıda thread’ler ve parametreler denenmiş ve bunların optimum değerleri bulunmaya çalışılmıştır. Kuyruk listesi veri yapısı tabanlı paralel önce derine arama yöntemi ile geleneksel önce derine arama algoritması karşılaştırılmıştır. Bu çalışmada iki farklı zorluk seviyesinden 2’şer adet sudoku bulmacası kullanılmıştır. Her bir sudoku bulmacası 10’ar kez çözülerek çözüm süresinin ortalamaları alınarak incelemeler yapılmıştır. Denemeler sonucunda kuyruk listesi veri yapısı tabanlı paralel önce derine arama yönteminin, belirli thread sayısı ve parametreler ile geleneksel önce derine arama algoritmasından daha hızlı çözdüğü görülmüştür.