Problem 96 - Su Doku

Soru

Japonca anlamı sayı yerleştirme olan Sudoku problemiyle karşı karşıyayız. Her bir satırı ve sütunu 1-9 arası sayıların tamamını birer kere içeren, 9x9'luk karelerden oluşuyor. Aynı zamanda 9 parçaya ayrılmış 3x3'lük kareleri de 1-9'a kadar olan sayıların hepsini barındırmalı.

Soruda istenilen, .txt dosyası ile verilen 50 adet Sudoku'nun çözülmesi ve her Sudoku'nun ilk üç karesinin toplamlarının bulunması. Bu sayı örnekte 483.

http://projecteuler.net/problem=96
http://projecteuler.net/project/sudoku.txt


Çözüm

Elbette her Sudoku'yu tek tek çözmeyeceğiz. Bunun için Sudoku çözen bir program yapmamız lazım. Bunun için öncelikle kuralları iyi belirlemeliyiz.

1) Her satırda 1-9 arası tüm sayılar bulunmalı
2) Her sütunda 1-9 arası tüm sayılar bulunmalı
3) Her üçlüde  1-9 arası tüm sayılar bulunmalı

Çeşitli yollarla çözmek mümkün. Ben iki boyutlu tek bir bool dizi kullanarak çözme yolunu tercih ettim.

Her bir sayı için matriste dolaşıp o sayıyı bulunduğunda, mevcut olduğu satır ve sütunları eleyen bir dizi. Çünkü her sayı bir satır, sütun ve üçlüde yalnızca bir kere bulunabilir. Öyleyse sayının bulunduğu satır, sütun ve üçlüleri elersek geriye kalan kareler bize sayının olası konumlarını verir.

Bunu muhakkak bir kağıda çizerek denemelisiniz, zaten bu elemeleri yaptığınızda sistemin nasıl işlediği kolayca belli oluyor.

Bundan sonra o satır, sütun ve üçlülerin özel olup olmadığını test edeceğiz. Buradan özelden kastım, o sayı mecburen orada mı olmalıdır, yani başka koyulacak bir yer yok mudur sorusunun cevabıdır.

Fakat tüm bunlar yine yetersiz kalabilir ve başka bir yola başvurmak zorunda kalabiliriz. O durumda da mevcut olasılıkları deneyerek sonucun doğru çıktığı yolu bulmaya çalışacağız. Bu işin zor kısmı, ne de olsa zor sudokular için.


Kodlama

İlk başta basit kısmı ele alalım. Programın tüm işini yürüten parça bu kod. 

İşaretleme kısmı

static void CheckingProcess(char Number)
{
   for (int a = 0; a < 9; a++) // Checking all true(possible)
      for (int b = 0; b < 9; b++)
         if(Board[a,b] == '0')
            PossibleSquares[a, b] = true;

   for (int i = 0; i < 9; i++)
      for (int j = 0; j < 9; j++)
         if (Board[i, j] == Number)
            EliminateSquares(i, j);

   ListingProcess(Number);

}

Üstteki kodun ilk iki for döngüsü tüm kareleri true değerle işaretliyor. Sonrasındaki iki for döngüsü ise, EliminateSquares(KareleriEle) metotunu kullanarak belirlenen bir sayının matristeki i ve j konumunu göndererek o konumdaki üçlüyü, satır ve sütunu false olarak işaretliyor. Son olarak da ListingProcess(Listelemeİşlemi) yeni listeyi oluşturuyor.

Eleme İşlemi

static void EliminateSquares(int i, int j)
{
   for (int a = 0; a < 9; a++) // Eliminate row
      PossibleSquares[i, a] = false;
   for (int a = 0; a < 9; a++) // Eliminate column
      PossibleSquares[a, j] = false;

   EliminateTriad(i, j);

}

Burada EliminateTriad(ÜçlüyüEle) fonksiyonunu ayrıca yazıp çağırdım. İlk for döngüsü satırı ikincisi ise sütunu karalıyor(false yapıyor).

Satır Özel mi?

static bool isRowUnique(int i, int j)
{
   byte count = 0;

   for (int a = 0; a < 9; a++)
      if (PossibleSquares[i, a] == true)
         count++;

      if (count > 1)
         return false;

   return true;

}

Yukarıdaki kod ise, o satırda eğer sadece bir kareye bu sayı yerleştirilebiliyorsa true, eğer başka kareye de gelme olasılığı varsa false değerini döndürüyor. Eğer true dönerse, o sayı mecbur o kareye gelecektir ve biz de onu tahmine gerek kalmaksızın oraya koyabiliriz.

Sayıyı kareye yerleştirme

if (PossibleSquares[i, j] == true && (isRowUnique(i,j) || isColumnUnique(i,j) || isTriadUnique(i,j) ))

   Board[i, j] = Number;


Üstteki kodda dikkat edilmesi gereken paranteze alınmış "veya" - "||" işlemleri. Sayının muhtemelen o kareye gelme ihtimalinin doğru olması ve o üç kuraldan sadece birinin geçerli olması oraya yerleştirmemiz için yeterli koşulu sağlıyor.

Bu haliyle işleme aldığınızda 50 Sudoku'dan alınan sonuç aşağıdaki gibi oluyor. Dolayısıyla zor Sudoku'ları çözmek için tahmin yoluna da gideceğiz. Bunu da sonra ekleyeceğim.