Standart C Programlama Dili

4.7. Bir Örnek—8 Vezir Problemi

Bu kısımda, fonksiyonlar, bitsel işleçler, küresel değişkenler, register bellek sınıfı ve özçağrı gibi kavramları kullanan örnek bir program vereceğiz.

Bu program bize klasikleşmiş bir problemin çözümlerini bulacaktır: 8 çarpı 8’lik bir satranç tahtasına birbirini almayacak şekilde sekiz vezirin yerleştirilmesi. İki vezir aynı sıra, sütun veya çaprazda olduğunda birbirini alabilir. Yani bir çözümde aynı sıra, sütun veya çapraz hatta iki vezir bulunmamalıdır. Örneğin,

bir çözümdür. Burada V bir veziri, · ise boş bir kareyi gösterir.

Bu problemi çözmede ilk yaklaşım sistemli bir şekilde tüm yerleştirmeleri inceleyip sadece geçerli olanları listelemektir. Bir bilgisayarımız olduğuna göre, bunu çabuk bir şekilde yapabiliriz. Aslında, o kadar da değil! Olası tüm değişik yerleştirmelerin sayısı (8 × 8)! (8 × 8 - 8)! × 8! = 4.426.165.368’dir.

Her yerleştirme için bir milisaniye harcasak bile, hepsini teker teker denemek elli günden daha uzun bir süre alacaktır. Araştırma bölgemizi daraltmamız gerekir. Aşağıdaki gözlemler yararlı olacaktır:

1. Eğer iki veziri yerleştirdiğimizde bunların birbirini aldığını görürsek, diğerlerini de dikkate alan bütün olası yerleştirmeleri denememize gerek yoktur. Bu, bütün vezirleri satranç tahtasına yerleştirdikten sonra değil, bir vezir yerleştirir yerleştirmez uyuşmazlıkları kontrol etmemiz gerektiği anlamına gelir.
2. Aynı sıraya iki vezir yerleştirmeye çalışmamalıyız. Her veziri bir sıraya atayarak; bunu gerçekleştirebiliriz. Her vezir sadece kendi sırasındaki 8 kareden birisine yerleştirilecektir.

Bu iki gözlem araştırma bölgemizi çok daraltacaktır. Algoritma şöyledir:

• En üst sıradan başlayarak, her veziri kendi sırasına, en sağdaki sütundan itibaren, yerleştirin.
• Bir vezir yerleştirdiğinizde, daha önce yerleştirilmiş vezirlerle bir uyuşmazlığın olup olmadığını kontrol edin. Eğer varsa, veziri bir sonraki (yani hemen solundaki) kareye kaydırın; eğer yoksa, bir sonraki (yani hemen altındaki) sırayı değerlendirin. Eğer son vezir de başarılı bir şekilde yerleştirilirse, bu bir çözümdür.
• Eğer bir vezir, sırasındaki sekizinci sütunu da geçerse, o zaman veziri satranç tahtasından alın, bir önceki sıraya geriye dönüş yapın ve bu sıradaki veziri bir sonraki (yani hemen solundaki) kareye kaydırın.
• İlk sıradaki vezir son sütundaki kareden dışarı çıkıncaya kadar buna devam edin.

Algoritmayı belirledikten sonra, bu sefer işlenecek bilgiyi saklayacak veri yapısı için karar vermemiz gerekecektir. Verimlilik en önemli tasamız olmalıdır. Veri yapısı fazla miktarda bilgisayar belleği harcamamalı ve kolay, hızlı erişim sağlamalıdır.

Satranç tahtasını nasıl göstermemiz gerekir? En azından iki seçenek söz konusudur:

1. Her kare bir bitle gösterilebilir. Eğer bit 1 ise bu karede bir vezir var, 0 ise, boş demektir. Böylece, mantıksal olarak 8’e 8’lik bir kare şeklinde düzenlenmiş 64 bite gereksinimimiz vardır.
2. Her sırada en fazla bir vezir olduğuna göre; her elemanında o sıradaki vezir tarafından işgal edilen sütun sayısının saklandığı doğrusal bir dizi tutabiliriz.

Bu örnekte ilk seçeneği kullanacağız. Her sıra 8 bite gereksinim duyar. Birçok bilgisayarda, bir int değişken en az 16 bittir. Böylece iki sıra tek bir int değişkenin içinde saklanabilir. Ama, her sıra için bir tamsayı ayırıp sadece sağdaki (düşük) bitlerin kullanılması daha kolay olacaktır. Soldaki bitler ise kullanılmayabilir. Ayrıca, programı daha genel bir problem (yani n çarpı n’lik bir satranç tahtasına n adet vezirin yerleştirilmesi) için tasarlarsak, aynı programı kullanarak, örneğin, 15 vezir problemini de çözebiliriz.

Programda kullanılan veri yapısı (aşağıdaki program listesine bakın) şöyledir:

int tahta[8];

(Bu arada, int unsigned olarak #define edilmiştir, böylece sağa kaydırma işlemlerinin aritmetik, yani işaret doldurma, değil de mantıksal, yani sıfır doldurma, olması temin edilmiştir.) tahta ve sayi küresel değişkenler olarak tanımlanmışlardır, böylece bütün fonksiyonlar bunlara erişebilir. tahta[0] satranç tahtasının en üstteki sırasını, tahta[7] ise en alttaki sırayı gösterir. Bir dizi elemanının en düşük (yani sağdaki) biti sıranın en sağdaki sütununu gösterir. Altıncı sıranın en sağındaki sütununa bir vezir koymak istediğimizde

tahta[5] = 1;

atama deyimini; bu veziri bir sola kaydırmak istediğimizde

tahta[5] <<= 1;

atama deyimini; en soldaki sütundan ileriye bir vezir geçip geçmediğini anlamak için

tahta[sira] >= 1<<8

testini; iki farklı sıradaki iki vezirin aynı sütunda olup olmadığını anlamak için

tahta[sira2] == tahta[sira1]

testini; aynı çapraz hatta olup olmadığını anlamak için

tahta[sira2] == tahta[sira1]<<sira1-sira2 ||
  tahta[sira2] == tahta[sira1]>>sira1-sira2

testini kullanabiliriz. Yukarıdaki testleri kullanarak, tahtaTamam fonksiyonunu tasarlayabiliriz. Bu fonksiyon, sira’ya yeni bir vezir yerleştirildiğinde tahtanın tamam olup olmadığını kontrol eder. Bunu yapmak için 0’dan sira’ya kadar (sira hariç) olan bütün sıralarla sira arasındaki uyuşmazlıkları kontrol eder. Eğer sira 0 ise o zaman for döngüsüne hiç girilmeyecek tahtaTamam fonksiyonu hemen 1 (doğru) döndürecektir: İlk sıra için satranç tahtası her zaman tamamdır.

Bir çözüm bulunduğunda cozumyaz fonksiyonu çağrılır. sayi (çözüm sayısı) değişkeni bir artırılır ve tahta’daki çözüm yazılır. Dış döngü sıralar, iç döngü de sütunlar içindir.

Programın kalbi yerlestir fonksiyonudur. Algoritmadan da tahmin edebileceğiniz gibi, bu özçağrılı bir fonksiyon olarak tanımlanabilir. Bu fonksiyon, başta 0 (ilk sıra) argümanıyla ana programdan çağrılır. for döngüsü belirtilen sira’nın her sütununa veziri yerleştirir. Her yerleştirmeden sonra tahta kontrol edilir; eğer tamamsa, bu sira için yerleştirme işlemi geçici olarak bekletilir ve bir sonraki sira denenir. Bir sonraki sira’yı kim deneyecektir? Tabii ki, aynı fonksiyon! Sonsuz özçağrılara engel olmak için fonksiyonun başında bir test yapılır. Eğer yerlestir 8 argümanıyla çağrılmışsa, bu, satranç tahtasına (başarılı bir şekilde) 8 vezirin yerleştirildiği anlamına gelir. Bu durumda yerlestir fonksiyonu çözümü yazdırır ve hemen döner. yerlestir fonksiyonunun her yeni çağrısında sira adı verilen yeni bir (yerel) değişken yaratılır. Bir önceki çağrıya geri döndüğümüzde bir önceki sira değişkeni tekrar geri gelir; değeri ise bir eksiği olur.

#include <stdio.h>
#define VEZIRLER 8          /* vezir sayısı ve tahta boyu */
#define int unsigned        /* işaretsiz tamsayı kullan */

int sayi = 0;               /* çözüm sayısı */
int tahta [VEZIRLER];       /* her eleman bir sırayı gösterir */

int tahtaTamam              /* tahtanın geçerliliğini kontrol et */
    (register int sira)
{
  register int r;

  for (r = 0; r < sira; r++) /* önceki tüm sıraları  kontrol et */
    if (tahta[sira] == tahta[r] ||
        tahta[sira] == tahta[r] << sira-r ||
        tahta[sira] == tahta[r] >> sira-r)
      return 0;             /* uyuşmazlık varsa */
  return 1;                 /* uyuşmazlık yoksa */
}

void cozumyaz (void)        /* çözümü göster; sayıyı artır */
{
  register int t, r;

  printf("\n\n\tCOZUM %u\n\n", ++sayi);
  for (r = 0; r < VEZIRLER; r++) { /* sira */
    for (t = 1<<VEZIRLER-1; t > 0; t >>= 1)
      printf(" %c", tahta[r] == t ? 'V' :  '.');
    printf("\n");
  }
}

void yerlestir (int sira)   /* bir sonraki sıraya yerleştir */
{
  if (sira == VEZIRLER)     /* tüm sıralar dolu ve kontrol edilmiş */
    cozumyaz();
  else
    for (tahta[sira]=1; tahta[sira]<1<<VEZIRLER;  tahta[sira]<<=1)
      if (tahtaTamam(sira))
        yerlestir(sira+1);  /* bir sonraki sırayı dene */
}

signed main (void)
{
  yerlestir(0);             /* ilk sıradan başla */
  printf("\n\n%d vezir probleminin %u cozumu vardir.\n",
    VEZIRLER, sayi);
  return 0;
}

Bu örnekte, özçağrı adımı yerine bir döngü ve sira değişkeninin uygun şekilde artırılıp azaltılması kullanılabilir.

Aşağıda VEZIRLER değişmezine değişik değerler verildiğinde yukarıdaki programla elde edilen sonuçları görüyorsunuz: