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,
· | · | · | · | · | · | · | V |
· | · | · | V | · | · | · | · |
V | · | · | · | · | · | · | · |
· | · | V | · | · | · | · | · |
· | · | · | · | · | V | · | · |
· | V | · | · | · | · | · | · |
· | · | · | · | · | · | V | · |
· | · | · | · | V | · | · | · |
bir çözümdür. Burada
bir veziri,
V
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:
- 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.
- 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:
- 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.
- 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 tamam
dı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:
VEZIRLER | Çözüm sayısı |
---|---|
1 | 1 |
2 | 0 |
3 | 0 |
4 | 2 |
5 | 10 |
6 | 4 |
7 | 40 |
8 | 92 |
9 | 352 |
10 | 724 |
11 | 2.680 |
12 | 14.200 |
13 | 73.712 |
14 | 365.596 |
15 | 2.279.184 |
16 | 14.772.512 |
17 | 95.815.104 |
18 | 666.090.624 |
19 | 4.968.057.848 |
20 | 39.029.188.884 |