Sudoku Çözücü Uygulaması

Şu ana kadarki yazılarımın çoğu kitaplar içerisinde de bulunabilecek konu başlıklarında oluşuyordu. Bu yazımda daha önce öğrendiğimiz eşikleme, bağlantılı bileşen etiketleme gibi teknikleri kullanarak basit bir uygulama yazmaya çalışacağım. Uygulamanın basit olması kesinlikle daha önceki tekniklerimizi kullanmamıza dayanıyor, o yüzden devam etmeden önce özellikle bağlantılı bileşen etiketleme konusunu gözden geçirmenizi tavsiye ederim. Gelelim uygulamamıza, sudoku çözmeye başlamamdan itibaren hep aklıma gelen bir konuydu bu; cep telefonu ile bulmacanın fotoğrafını çekiyorsun ve o da sana çözümleri buluyor.


Harika bir şey olurdu bu! Ama o algoritma mı bu algoritma mı derken zaten bu konuda pek çok uygulamanın yazıldığını farkettim. Mobil uygulama yazmak için her ne kadar geç kalmış olsam da kendimce bir sudoku çözücü yapmaya çalıştım. Yazının ilk serisinde çekilen bir fotoğraf üzerinden sudoku karesinin nasıl tespit edileceğini anlatacağım.

Bildiğiniz gibi sudoku 9 adet 3x3 kareden oluşan ve 3x3 her kare içerisinde 1 den 9 a kadar olan sayıların bir kez kullanılması ve her satir ve sütunda tüm rakamların bulunması gibi 2 kurala dayalı bir oyun. Bizim ilk aşamadaki amacımız 9x9 luk büyük kareyi bularak verilen sudokunun bilgisayarımıza doğru şekilde aktarımını sağlamak olacak.

NOT: Burada başladığım yazı kullandığım CBMP kütüphanesini IMLAB kütüphanesine güncellemem nedeniyle projenin geldiği noktanın oldukça gerisinde kaldı. Eğer bu yazıyı ilk kez okuyacaksanız bu blogda yer alan yazılarımın güncellenmiş versiyonlarını paylaştığım cescript.github.io sayfasında yer alan başlığı ziyaret etmenizi öneririm.

Büyük kareyi tespit etmek için aklıma gelen ilk yol doğru tespiti yapmaktı. Bunun için incelediğim Hough Transformu gayet başarılı sonuçlar vermiş olsa da mobil yazılım için daha basit bir yöntem düşünmeye çalıştım. Özellikle sudoku karesinin koyu renkli olması eşikleme programı ile pek çok gereksiz bileşenden kurtulabileceğim fikrimi verdi. Tabiki eşikleme için kullanılacak değer resimden resime farklılık göstereceğinden Otsu Metodunu kullanarak eşikleme işlemini gerçekleştirdim.

Adaptif eşikleme ile sudoku karesi tespiti

Eşik değerini dinamik olarak değiştirmek sabit bir değer ile eşiklemeye göre bir avantaj sağlasa hala büyük kareyi net bir şekilde ortaya çıkarmış olmak için daha farklı bir eşikleme yöntemi düşünmek mantıklı olacaktır. Otsu metodu ile eşikleme tüm resme bir bütün olarak davrandığından özellikle ışık düşen yerlerde çerçeveyi bulmamız mümkün olmayacaktır. Burada resmi küçük resimler olarak ayırıp küçük parçaları eşikleyen adaptif bir eşikleme yapmamız programımızın homojen olmayan ışık altında da çalışmasını sağlayacaktır. Bunun için basit olarak her bir pikselin değerini 8 komşusunun değerlerine göre belirleyen bir eşikleme yöntemi tasarladım. Program her bir pikseli 8 komşusunun ortalamasına bakarak 0 veya 255 olarak kodlayarak siyah-beyaz bir resim oluşturmaktadır.

BMP esik = yenim_bmp(giren.bminfo.width,giren.bminfo.height);
            
for(int j=1;j < giren.bminfo.height-1;j++) { 
     for(int i=1;i < giren.bminfo.width-1;i++) {
            
            unsigned int merkez = giren.pixels[i][j].red;
            
            int k1 = giren.pixels[i][j+1].red;
            int k2 = giren.pixels[i][j-1].red;
            int k3 = giren.pixels[i+1][j].red;
            int k4 = giren.pixels[i-1][j].red;
            
            int k5 = giren.pixels[i+1][j+1].red;
            int k6 = giren.pixels[i+1][j-1].red;
            int k7 = giren.pixels[i-1][j+1].red;
            int k8 = giren.pixels[i-1][j-1].red;
            
                   
            int deger = 0.97*(k1+k2+k3+k4+k5+k6+k7+k8)/8 < merkez ? 0:255;
                  
            esik.pixels[i][j].red   = (byte) (deger);
            esik.pixels[i][j].green = (byte) (deger);
            esik.pixels[i][j].blue  = (byte) (deger); 
      }
}

Programda da görüldüğü üzere merkez pikselin değeri 8 komşusunun ortalamasından büyükse 0, küçükse 255 ile değiştirilerek eşiklenmiş resim oluşturulmaktadır. Eşiklenen resme ait görüntü aşağıda verilmiştir.

Karşılaştırmanın daha kolay olması için Otsu ile eşiklenmiş resmi de (ortadaki) renklerini ters çevirerek tabloya koydum. Görüldüğü üzere adaptif ve yerel eşikleme kullanarak yapılan eşikleme sonucu sudoku karesi belirgin bir şekilde ortada kalmaktadır.

Sıradaki amacımız bu belirgin sudoku karesini tespit etmek. Bunun için bağlantılı bileşen etiketleme hızlı ve güvenilir! bir yol olacaktır. Eşikleme işlemi sonrası geriye kalan en büyük bağlantılı bileşenin sudoku karesi olduğunu kabul edecek olursan sudoku karesi şu kod yardımı ile kolaylıkla tespit edilecektir. 

resim=resim_bbe(esik,&bbsayisi);
int MaxRegion=0,bilesen_no=0;
            
int histogram[bbsayisi+1];
int MaxBilesen = 0;
            
for(int histo=0;histo < bbsayisi+1;histo++) {histogram[histo]=0;}
            
for(int j=0;j < resim.bminfo.height;j++) { 
    for(int i=0;i < resim.bminfo.width;i++) {
                    
             bilesen_no = resim.pixels[i][j].red+256*resim.pixels[i][j].green+65536*resim.pixels[i][j].blue;
                    
             histogram[bilesen_no]++;
                    
             if (histogram[bilesen_no]  >  MaxRegion & bilesen_no != 0) {
               MaxRegion=histogram[bilesen_no];
               MaxBilesen=bilesen_no; 
             }
                    
    }
}

Tespit edilen en büyük bağlantılı bileşeni belirledik. Şimdi bu bileşeni farklı resimler üzerinde gösterelim.

Resimlerde dikkatinizi tüm karelerin ve çizgilerin tam olarak tespit edilmemiş olması çekebilir. Yazımıza başlarken de söylediğim gibi amacımız büyük kareyi tam olarak tespit etmekti. Çünkü üzerinde çalıştığımız şekil kare olduğundan büyük kareyi bularak uygun işlemlerle (büyük kareyi 3x3 lük karelere ayırma) küçük kareleri ve içerisindeki rakamları kolaylıkla tespit edebiliriz. Bunu elde edebilmek için sadece büyük karemizin 4 köşesini bulmamız yeterlidir.

Bu yazımda daha önce öğrendiğimiz metotları nasıl bir uygulama içerisinde kullanacağımızı anlatmaya çalıştım. Sudoku çözücümüz için gereken diğer adımlar

• Perspektif düzeltme
• Rakam tanıma
• Sudoku çözme

daha çok bilgi gerektirecek uygulamalar olduğundan her birini bir yazı şeklinde detaylı olarak yazmayı planlıyorum.