N Vezir Problemi

Bir önceki derste kalıp yanlış yanıt verdi ve kâhin doğru yanıtı verdi. Bu ders kâhinin kendisine bakar. N vezir probleminde kâhin, tahtaya bütün vezir yerleşimlerini deneyen kaba kuvvettir; geri izleme ise aynı aramayı çatışan dalları keserek yapar. Ortak tanım bu ikisinin sayılarını çoktan verdi ve bu ders onları tekrar ölçmez, girdi alır.

Problem şudur: n satır ve n sütunluk bir tahtaya n vezir yerleştirilecek, hiçbir ikisi aynı satırı, aynı sütunu ya da aynı çaprazı paylaşmayacak. Yeni soru şudur: tahtanın kendi simetrileri kullanılarak arama alanı küçültülebilir mi, ve küçültülürse bu, budamanın kattığıyla aynı türden bir kazanç mıdır.

• KP30. Ortak tanımın geri izleme sayıları girdidir: n=5’te budamalı 54 düğüm ve budamasız 3906 düğüm, n=6’da 153 ve 55.987, n=7’de 552 ve 960.800, n=8’de budamalı 2057 düğüm ve budamasız 16.777.216 yerleşim. Bu sayılar tekrar ölçülmez.
• KP31. Budamalı gezinti ortak tanımdaki yordamın aynısıdır: her satıra bir vezir konur, çatışma varsa dal orada kesilir. Simetri elemesi bunun üstüne eklenir.
• KP32. Simetri elemesi tek bir kısıtla kurulur: ilk satırdaki vezir yalnız tahtanın ilk yarısına konabilir. Tek sayıda sütunda orta sütun bu yarıya dahildir.
• KP33. Kâhin, kısıtsız budamalı gezintinin ürettiği çözüm kümesidir. Yarım tahtadan çıkan çözümler yansıtılıp bu kümeyle karşılaştırılır; küme eşitliği tam olarak sınanır.
• KP34. Tahtanın simetri grubu sekiz elemanlıdır: dört çeyrek dönüş ve her birinin yansıması. Bir çözümün denklik sınıfı bu sekiz dönüşümün ürettiği ayrı çözümlerden oluşur.
• KP35. Ölçü adımdır ve bir adım, arama ağacında ziyaret edilen bir düğümdür.
• KP36. Tahta boyu 5 ile 9 arasında tutulur; büyük n sayılarak anlatılır, koşturularak değil. Bu dersin girdisi üreteçten gelmez: tek girdi tahta boyudur ve bütün sayılar tam sayımdır. İkinci dağarcık kuralının yerini bu derste tahta boyu süpürmesi alır; her satır bağımsız bir koşumdur ve tohuma bağlı hiçbir değer yoktur.
• KP37. Bütün çözümleri bulmak ile tek çözüm bulmak ayrı ölçülür. İkisi aynı problemin iki farklı sorusudur ve maliyetleri karşılaştırılabilir değildir.
• KP38. Bir adayın doğrulanması ayrı sayılır: bütün vezir çiftleri karşılaştırılır.
• KP39. İkinci kısıt olan ileri bakış, simetri elemesinden bağımsızdır. İkisinin birlikte kattığı, ayrı ayrı kattıklarının çarpımıyla karşılaştırılır; eşitlik varsayılmaz, ölçülür.

Simetri Elemesinin Ölçülmesi

Bir çözüm bulunduğunda onun aynadaki görüntüsü de bir çözümdür. Aynı şey çeyrek dönüşler için de geçerlidir. Bu, aramanın bir bölümünün gereksiz olduğu anlamına gelir: ilk vezir sağ yarıya konarak bulunan her çözüm, sol yarıya konarak bulunmuş bir çözümün yansımasıdır.

Aşağıdaki blok kısıtı ekler, iki gezintinin düğüm sayısını yan yana koyar, yansıtmayla geri kurulan kümeyi kâhinin kümesiyle karşılaştırır ve denklik sınıflarını sayar.

class Sayac:
    def __init__(self):
        self.adim = 0

    def say(self):
        self.adim += 1


def vezir(n, ilk_yari=False):
    """Ortak tanimin budamali geri izlemesi; ilk_yari simetri elemesini ekler."""
    s = Sayac()
    cozum = []

    def gez(satir, yer):
        s.say()
        if satir == n:
            cozum.append(tuple(yer))
            return
        ust = (n + 1) // 2 if (ilk_yari and satir == 0) else n
        for sutun in range(ust):
            if any(sutun == y or abs(sutun - y) == satir - i
                   for i, y in enumerate(yer)):
                continue
            yer.append(sutun)
            gez(satir + 1, yer)
            yer.pop()
    gez(0, [])
    return s.adim, cozum


def yansit(c, n):
    return tuple(n - 1 - x for x in c)


def dondur(c, n):
    yeni = [0] * n
    for i, x in enumerate(c):
        yeni[x] = n - 1 - i
    return tuple(yeni)


def sinif(c, n):
    """Bir cozumun sekiz donusum altindaki butun goruntuleri."""
    kume, d = set(), c
    for _ in range(4):
        kume.add(d)
        kume.add(yansit(d, n))
        d = dondur(d, n)
    return kume


print(" n | tam dugum | tam cozum | yarim dugum | yarim cozum | dugum orani"
      " | yansitilinca | temel cozum | en kucuk sinif")
for n in (5, 6, 7, 8, 9):
    d1, c1 = vezir(n)
    d2, c2 = vezir(n, ilk_yari=True)
    geri = set(c2) | {yansit(c, n) for c in c2}
    tam = set(c1)
    temel, gorulen, en_kucuk = 0, set(), 99
    for c in sorted(tam):
        if c in gorulen:
            continue
        k = sinif(c, n)
        gorulen |= k
        temel += 1
        en_kucuk = min(en_kucuk, len(k))
    print(f"{n:2d} | {d1:9d} | {len(c1):9d} | {d2:11d} | {len(c2):11d} |"
          f" {round(d1 / d2, 2):11} | {'ayni' if geri == tam else 'FARKLI':12s}"
          f" | {temel:11d} | {en_kucuk:14d}")

 n | tam dugum | tam cozum | yarim dugum | yarim cozum | dugum orani | yansitilinca | temel cozum | en kucuk sinif
 5 |        54 |        10 |          32 |           6 |        1.69 | ayni         |           2 |              2
 6 |       153 |         4 |          77 |           2 |        1.99 | ayni         |           1 |              4
 7 |       552 |        40 |         316 |          23 |        1.75 | ayni         |           6 |              4
 8 |      2057 |        92 |        1029 |          46 |         2.0 | ayni         |          12 |              4
 9 |      8394 |       352 |        4704 |         203 |        1.78 | ayni         |          46 |              4

Kazancın Büyüklüğü ve Türü

İlk sütun ortak tanımın sayılarını doğruluyor: 54, 153, 552, 2057. Simetri kısıtı eklendiğinde düğüm sayısı sekiz vezirde 2057’den 1029’a iniyor, oran 2,00. Beş vezirde 1,69, altı vezirde 1,99, yedi vezirde 1,75, dokuz vezirde 1,78. Beş satırın hiçbirinde oran 2’yi geçmiyor.

Yansıtma sütunu kâhin karşılaştırmasıdır. Yarım tahtadan çıkan çözümlere yansımaları eklendiğinde elde edilen küme, kısıtsız aramanın çözüm kümesiyle beş tahta boyunun beşinde de aynı. Simetri elemesi bir yaklaşık çözüm değildir: hiçbir çözüm kaybolmuyor, yalnız bulunma yolu değişiyor. Bu, kursta ölçülen ender bir durumdur — kalıp kâhinden hiçbir girdide ayrılmıyor.

Şimdi bu kazanç ortak tanımın budama kazancının yanına konmalıdır.

n	budamasız (ortak tanım)	budamalı	budama oranı	yarım tahta	simetri oranı
5	3.906	54	72,3	32	1,69
6	55.987	153	365,9	77	1,99
7	960.800	552	1740,6	316	1,75
8	16.777.216 yerleşim	2057	8156,2	1029	2,00

İki sütun aynı birimde ama aynı türden değil. Budama oranı 72,3’ten 8156,2’ye çıkıyor, yani n büyüdükçe budamanın kattığı da büyüyor. Simetri oranı 1,69 ile 2,00 arasında kalıyor ve büyümüyor; büyüyemez de, çünkü elenen şey tahtanın sabit sayıda simetrisidir ve o sayı n ile değişmez.

Bu ayrım kursun ölçü okumasının bir parçasıdır. Bir iyileştirmenin sayısı tek başına yeterli değildir; sayının n ile ne yaptığı sorulmalıdır. Sekiz vezirde bin düğüm kazandıran bir kısıt, on altı vezirde de yalnız yarısını kazandırır, ve o yarı hâlâ üsteldir. Ortak tanımın dördüncü okuması bunu budama için söylüyordu: budamanın kazancı ölçekle artar ama sonuç hâlâ üsteldir. Simetri elemesinde ise kazanç ölçekle artmıyor bile.

Temel çözüm sütunu üçüncü bir sayı veriyor. Sekiz vezirde 92 çözüm, ama denklik sınıflarının sayısı 12. Bu 92’nin 8’e bölümü değildir: 92 bölü 8, 11,5 eder. Fark, en küçük sınıf sütununda görünür. Bazı çözümler bir dönüşüm altında kendilerine eşlenir, bu yüzden sınıfları sekiz değil dört ya da iki elemanlıdır. Beş vezirde en küçük sınıf 2 elemanlıdır. Simetriyle eleme yaparken “sekize böl” demek bu yüzden yanlış olur.

İki İyileştirme Çarpılıyor mu

Simetri elemesi aramanın başlangıcını kısıtlar. Bundan bağımsız ikinci bir kısıt daha eklenebilir: bir vezir yerleştirildikten sonra kalan satırlardan birinde hiç boş sütun kalmadıysa o dal hemen kesilir. Buna ileri bakış denir ve çatışmanın görünmesini beklemez, geleceğe bakıp keser. İki iyileştirme birbirinden bağımsızdır; sorulacak şey, birlikte kullanıldıklarında kazançların çarpılıp çarpılmadığıdır.

class Sayac:
    def __init__(self):
        self.adim = 0

    def say(self):
        self.adim += 1


def catisiyor(sutun, satir, yer):
    return any(sutun == y or abs(sutun - y) == satir - i
               for i, y in enumerate(yer))


def vezir(n, ilk_yari=False, ileri=False):
    """Iki bagimsiz iyilestirme: simetri elemesi ve ileri bakis."""
    s = Sayac()
    sayi = 0

    def gez(satir, yer):
        nonlocal sayi
        s.say()
        if satir == n:
            sayi += 1
            return
        ust = (n + 1) // 2 if (ilk_yari and satir == 0) else n
        for sutun in range(ust):
            if catisiyor(sutun, satir, yer):
                continue
            yer.append(sutun)
            if not ileri or all(any(not catisiyor(c, r, yer) for c in range(n))
                                for r in range(satir + 1, n)):
                gez(satir + 1, yer)
            yer.pop()
    gez(0, [])
    return s.adim, sayi


print(" n | yalin | simetri | ileri bakis | ikisi birden"
      " | ayri ayri carpim | olculen oran")
for n in (6, 7, 8, 9, 10):
    d0, _ = vezir(n)
    d1, _ = vezir(n, ilk_yari=True)
    d2, _ = vezir(n, ileri=True)
    d3, _ = vezir(n, ilk_yari=True, ileri=True)
    carpim = (d0 / d1) * (d0 / d2)
    print(f"{n:2d} | {d0:5d} | {d1:7d} | {d2:11d} | {d3:12d} |"
          f" {round(carpim, 2):16} | {round(d0 / d3, 2)}")

 n | yalin | simetri | ileri bakis | ikisi birden | ayri ayri carpim | olculen oran
 6 |   153 |      77 |          87 |           44 |             3.49 | 3.48
 7 |   552 |     316 |         334 |          187 |             2.89 | 2.95
 8 |  2057 |    1029 |        1165 |          583 |             3.53 | 3.53
 9 |  8394 |    4704 |        4720 |         2658 |             3.17 | 3.16
10 | 35539 |   17770 |       17489 |         8745 |             4.06 | 4.06

Son iki sütun beş satırın beşinde de örtüşüyor: 3,49 ile 3,48, 2,89 ile 2,95, 3,53 ile 3,53, 3,17 ile 3,16, 4,06 ile 4,06. Ayrı ayrı ölçülen kazançların çarpımı, birlikte ölçülen kazanca eşit çıkıyor. İki kısıt aramanın farklı yerlerine dokunduğu için birbirlerinin işini tekrarlamıyorlar.

Bu örtüşme bir kural değildir, ölçülmüş bir sonuçtur; iki kısıt aynı dalları kesiyor olsaydı çarpım ölçülen orandan büyük çıkardı ve fark fazla sayılan kazanç olurdu. Ölçüm tam da bunu sınamak için yapılır.

Yine de birleşik oran 4,06’da kalıyor. Üç iyileştirme üst üste kondu ve arama alanı hâlâ n ile üstel büyüyor; on vezirde 8745 düğüm, on iki vezirde bu sayı yine kat kat artacak. Sabit çarpanlar toplandığında bile büyüme türü değişmez.

Simetrinin Hiçbir Şey Kazandırmadığı Soru

Buraya kadar sorulan soru “bütün çözümler” sorusuydu. Aynı problem başka bir soruyla da sorulabilir: bir tane çözüm bulmak. İki soru aynı tahtaya bakar ama maliyetleri karşılaştırılamaz.

class Sayac:
    def __init__(self):
        self.adim = 0

    def say(self):
        self.adim += 1


def gezinti(n, ilk_yari=False, dur=False):
    """Budamali geri izleme. dur=True ise ilk cozumde durur."""
    s = Sayac()
    bulunan = []

    def gez(satir, yer):
        s.say()
        if dur and bulunan:
            return
        if satir == n:
            bulunan.append(tuple(yer))
            return
        ust = (n + 1) // 2 if (ilk_yari and satir == 0) else n
        for sutun in range(ust):
            if dur and bulunan:
                return
            if any(sutun == y or abs(sutun - y) == satir - i
                   for i, y in enumerate(yer)):
                continue
            yer.append(sutun)
            gez(satir + 1, yer)
            yer.pop()
    gez(0, [])
    return s.adim, bulunan


def dogrula(c, n):
    """Aday cozum butun vezir ciftleri karsilastirilarak sinanir."""
    adim = 0
    for i in range(n):
        for j in range(i + 1, n):
            adim += 1
            if c[i] == c[j] or abs(c[i] - c[j]) == j - i:
                return False, adim
    return True, adim


print(" n | ilk cozum | ilk cozum yarim | butun cozumler | oran | dogrulama")
for n in (5, 6, 7, 8, 9, 10):
    d1, b1 = gezinti(n, dur=True)
    d2, _ = gezinti(n, ilk_yari=True, dur=True)
    d3, hepsi = gezinti(n)
    ok, adim = dogrula(b1[0], n)
    print(f"{n:2d} | {d1:9d} | {d2:15d} | {d3:14d} | {d3 // d1:4d} |"
          f" {adim:3d} adim, dogru mu {ok}")

 n | ilk cozum | ilk cozum yarim | butun cozumler | oran | dogrulama
 5 |         6 |               6 |             54 |    9 |  10 adim, dogru mu True
 6 |        32 |              32 |            153 |    4 |  15 adim, dogru mu True
 7 |        10 |              10 |            552 |   55 |  21 adim, dogru mu True
 8 |       114 |             114 |           2057 |   18 |  28 adim, dogru mu True
 9 |        42 |              42 |           8394 |  199 |  36 adim, dogru mu True
10 |       103 |             103 |          35539 |  345 |  45 adim, dogru mu True

İkinci ve üçüncü sütun altı satırın altısında da aynı. Simetri elemesi ilk çözümü bulmakta hiçbir şey kazandırmıyor, çünkü aramanın bulduğu ilk çözümde birinci vezir zaten sıfırıncı sütundadır ve o sütun kısıtın içindedir. Kısıt, hiç girilmeyecek bir bölgeyi kapatıyor.

Bu, iyileştirmelerin soruya bağlı olduğunun ölçülmüş halidir. Aynı kısıt bütün çözümler sorulduğunda düğümü tam yarıya indiriyor, tek çözüm sorulduğunda sıfır kazandırıyor. Bir iyileştirmenin değeri yordamdan değil, sorulan sorudan gelir.

Son iki sütun daha keskin bir farkı gösteriyor. On vezirde bütün çözümleri bulmak 35.539 düğüm, tek çözüm bulmak 103 düğüm, oran 345. Bulunmuş bir adayın doğru olduğunu sınamak ise yalnız 45 adım: bütün vezir çiftlerinin karşılaştırılması. Aramak, bulmak ve doğrulamak üç ayrı maliyettir ve aralarındaki fark tahta boyuyla açılır.

Özet

• Simetri elemesi düğüm sayısını sekiz vezirde 2057’den 1029’a indiriyor; oran beş tahta boyunda 1,69 ile 2,00 arasında kalıyor.
• Yansıtmayla geri kurulan çözüm kümesi kâhinin kümesiyle beş boyun beşinde de aynı; hiçbir çözüm kaybolmuyor.
• Budamanın oranı 72,3’ten 8156,2’ye çıkıyor, simetrinin oranı 2’de duruyor: biri n ile büyüyen, öteki sabit çarpanlı bir kazançtır.
• Temel çözüm sayısı sekiz vezirde 12; 92’yi sekize bölmek yanlış olur, çünkü bazı çözümler kendi görüntülerine eşlenir ve en küçük denklik sınıfı 4 elemanlıdır.
• Simetri elemesi tek çözüm arandığında hiçbir şey kazandırmıyor; aynı kısıt bir soruda yarı yarıya kazandırıp ötekinde sıfır kazandırıyor.

Sonraki Adım

N vezirde arama alanı tahtanın kendisinden okunuyordu: her satıra bir vezir, her vezire n seçenek. Sonraki ders arama alanının verili olmadığı problemlere geçer. At turu ve labirent aynı ızgarada tanımlanır, ama nasıl modellendiklerine göre taranacak nesne sayısı binlerce kat değişir. Sorulacak soru şudur: arama alanı problemin bir özelliği midir, yoksa modelin mi.