Backtracking: Permutation, Subset ve Sudoku ile Arama Ağacını Budamak

Sürüm notu: Bu yazıdaki kodlar .NET 10 ve C# 14 ile derlenip xUnit v3 4.0.2 testleriyle doğrulanmıştır.

Önce Tahmin Et

8 × 8'lik bir satranç tahtasına birbirini tehdit etmeyen 8 vezir yerleştirmenin 92 yolu var. Bunları bulan iki program yazdık. İkisi de her satıra bir vezir koyuyor ve satır satır ilerliyor. Biri vezirleri yerleştirirken hiçbir kontrol yapmıyor, 8 vezir tahtaya dizildikten sonra "geçerli mi?" diye bakıyor. Diğeri her vezir konduğu an aynı sütunda ya da çaprazda başka bir vezir varsa o dalı hemen terk ediyor.

foreach (int n in new[] { 4, 6, 8 })
{
    (int solutions, long pruned) = NQueens.Solve(n, prune: true);
    (_, long brute) = NQueens.Solve(n, prune: false);
    Console.WriteLine($"n={n}: solutions={solutions}, nodes with pruning={pruned:N0}, without={brute:N0}");
}

İkisi de 92 buluyor. Ama kaç tane yarım tahta (kısmi yerleşim) ziyaret ediyorlar? İlki için kabaca hesaplayabilirsin: her satırda 8 seçenek, 8 satır. İkincisi için tahminin ne: bunun yarısı mı, onda biri mi, binde biri mi?

Choose, Explore, Unchoose

Backtracking, bir çözümü adım adım kuran ve her adımda bir seçim yapan sistemli bir arama yöntemidir. Bir seçim çıkmaza girerse geri döner (back-track), seçimi geri alır ve bir sonrakini dener. Bütün backtracking algoritmaları aynı üç adımlı iskelete oturur: seç (choose), bu seçimle devam et (explore), seçimi geri al (unchoose). Permutation üretimi en sade örneği:

// choose -> explore -> unchoose; sonuçlar yield return ile tembel üretilir
public static IEnumerable<T[]> Permutations<T>(IReadOnlyList<T> items)
{
    T[] current = new T[items.Count];
    bool[] used = new bool[items.Count];
    return Build(0);

    IEnumerable<T[]> Build(int depth)
    {
        if (depth == items.Count)
        {
            yield return [.. current]; // kopya: current bir sonraki adımda değişecek
            yield break;
        }

        for (int i = 0; i < items.Count; i++)
        {
            if (used[i]) continue;
            used[i] = true;                 // seç
            current[depth] = items[i];
            foreach (T[] p in Build(depth + 1)) yield return p; // devam et
            used[i] = false;                // geri al
        }
    }
}

ABC ACB BAC BCA CAB CBA

Arama, kökü boş seçim olan bir tree gibi düşünülebilir: her seviye bir pozisyon, her dal o pozisyon için bir seçim, her yaprak tam bir permutation. Backtracking bu tree'yi DFS (Depth-First Search) ile gezer, ama tree'yi hiçbir zaman bellekte kurmaz; yalnız kökten bulunduğu node'a giden yolu (current ve used) tutar. Bellek O(n), zaman yaprak sayısıyla orantılı: n! permutation.

used[i] = false satırı, yani "unchoose", iskeletin en kolay unutulan parçası. O satır olmadan ilk dal used'u kirletir ve sonraki dallar hiçbir elemanı seçemez.

Subset ve Combination

Subset'lerde her eleman için iki seçim var: al ya da alma. Tree ikili, yaprak sayısı 2ⁿ:

public static IEnumerable<List<T>> Subsets<T>(IReadOnlyList<T> items)
{
    List<T> current = [];
    return Build(0);

    IEnumerable<List<T>> Build(int index)
    {
        if (index == items.Count)
        {
            yield return [.. current];
            yield break;
        }

        foreach (List<T> s in Build(index + 1)) yield return s; // items[index] olmadan
        current.Add(items[index]);
        foreach (List<T> s in Build(index + 1)) yield return s; // items[index] ile
        current.RemoveAt(current.Count - 1);
    }
}

Combination, yani n elemandan k tanesini sırasız seçmek, subset'in "boyutu tam k olanlar" kısmıdır. Burada ilk budama örneğimiz var: kalan eleman sayısı k'ya ulaşmaya yetmiyorsa o dala hiç girme.

public static IEnumerable<List<T>> Combinations<T>(IReadOnlyList<T> items, int k)
{
    List<T> current = [];
    return Build(0);

    IEnumerable<List<T>> Build(int start)
    {
        if (current.Count == k)
        {
            yield return [.. current];
            yield break;
        }

        // Budama: k'ya ulaşmaya yetecek kadar eleman kalmadıysa dur
        for (int i = start; i <= items.Count - (k - current.Count); i++)
        {
            current.Add(items[i]);
            foreach (List<T> c in Build(i + 1)) yield return c;
            current.RemoveAt(current.Count - 1);
        }
    }
}

{} {C} {B} {BC} {A} {AC} {AB} {ABC}
AB AC AD BC BD CD

start parametresi combination'ı permutation'dan ayırır: her eleman yalnız kendinden sonrakilerle eşleşir, böylece AB ve BA ayrı ayrı üretilmez.

yield return ile Lazy Üretim ve Exponential Büyüme

Üretim method'larının hepsi IEnumerable döndürüyor ve sonuçları yield return ile birer birer veriyor (C# Koleksiyonlar serisinin "C# Collection Interface'leri: IEnumerable, ICollection, IList ve yield return" yazısı). Bunun faydası, tüketicinin istediği kadarını alıp durabilmesi:

[Fact]
public void Permutations_IsLazy()
{
    // 12! = 479.001.600 permutation; ilk 3'ünü almak anında dönmeli
    Assert.Equal(3, Backtracking.Permutations([.. Enumerable.Range(1, 12)]).Take(3).Count());
}

Ama lazy olmak ucuz olmak demek değil. Hepsini saydırdığında exponential büyüme kendini gösteriyor:

foreach (int n in new[] { 8, 9, 10, 11 })
{
    Stopwatch sw = Stopwatch.StartNew();
    long count = Backtracking.Permutations([.. Enumerable.Range(1, n)]).LongCount();
    Console.WriteLine($"permutations of {n,2}: {count,12:N0} in {sw.ElapsedMilliseconds,6:N0} ms");
}

permutations of  8:       40,320 in     25 ms
permutations of  9:      362,880 in    188 ms
permutations of 10:    3,628,800 in    345 ms
permutations of 11:   39,916,800 in  4,282 ms

Her ek eleman süreyi kabaca n katına çıkarıyor; bu orana göre 12 eleman yaklaşık bir dakika, 13 eleman on dakikadan fazla sürer (ölçmedim, tahmin). İç içe yield return'ün de bir bedeli var: her sonuç, recursion derinliği kadar iterator katmanından geçerek dışarı çıkıyor, yani eleman başına O(n) ek iş. Lazy üretim okunaklı ve bellek dostu, ama sıcak bir döngüde milyonlarca sonuç gerekiyorsa sonuçları bir callback ile veren ya da tek bir array'i yerinde değiştiren implementasyon belirgin biçimde hızlıdır. Bu büyüme oranlarının dili Big-O ve Complexity serisinin "Big-O Notation Nedir" yazısındaki O(2ⁿ) ve O(n!) sınıfları.

Pruning: N-Queens

Budama (pruning), çözüme götüremeyeceği kesin olan bir dalı açmadan kesmektir. Backtracking'i kaba kuvvetten ayıran şey budur. N-Queens'te her satıra bir vezir koyuyoruz; sütunları ve iki yöndeki çaprazları birer bool[] ile takip ediyoruz, böylece "bu kare tehdit altında mı?" sorusu O(1):

// Çözümleri sayar; nodes = ziyaret edilen kısmi tahta sayısı
public static (int Solutions, long Nodes) Solve(int n, bool prune)
{
    int[] queenCol = new int[n];
    bool[] cols = new bool[n], diag = new bool[2 * n], anti = new bool[2 * n];
    int solutions = 0;
    long nodes = 0;
    Place(0);
    return (solutions, nodes);

    void Place(int row)
    {
        nodes++;
        if (row == n)
        {
            if (prune || IsValid()) solutions++;
            return;
        }

        for (int c = 0; c < n; c++)
        {
            if (prune && (cols[c] || diag[row + c] || anti[row - c + n]))
            {
                continue; // bu dal hiçbir zaman çözüme varamaz
            }

            queenCol[row] = c;
            cols[c] = diag[row + c] = anti[row - c + n] = true;
            Place(row + 1);
            cols[c] = diag[row + c] = anti[row - c + n] = false;
        }
    }

    bool IsValid()
    {
        for (int a = 0; a < n; a++)
            for (int b = a + 1; b < n; b++)
                if (queenCol[a] == queenCol[b] || Math.Abs(queenCol[a] - queenCol[b]) == b - a)
                    return false;
        return true;
    }
}

Aynı çaprazdaki kareler için row + c (sağ üstten sol alta) ya da row - c (sol üstten sağ alta) sabittir; + n negatif index'i önlüyor. prune: false ile aynı kod hiçbir kontrol yapmadan bütün yerleşimleri dener ve sonda doğrular. Açılıştaki sorunun cevabı:

n=4: solutions=2, nodes with pruning=17, without=341
n=6: solutions=4, nodes with pruning=153, without=55,987
n=8: solutions=92, nodes with pruning=2,057, without=19,173,961

8 vezirde budama 19 milyon node'u 2.057'ye indiriyor: yaklaşık 9.300 kat. Çaprazda iki vezirin olduğu bir yarım tahtanın altındaki bütün subtree'yi (2. satırda bir çakışma varsa 8⁶ = 262.144 yaprak) tek bir continue ile atlıyoruz. 4 vezirlik tahtanın budanmış ağacının tamamı:

Sudoku Solver: En Kısıtlı Hücreden Başla

Sudoku aynı iskelete oturur: boş bir hücre seç, oraya konabilecek bir rakam dene, devam et, çıkmaza girersen geri al. Burada ikinci bir budama tekniği devreye giriyor: hangi hücreyi seçtiğin. İlk boş hücreyi seçmek yerine en az aday rakamı olan hücreyi seçersek (most constrained first), tek adaylı hücreler tahmin yapmadan dolar ve sıfır adaylı bir hücre çıkmazı hemen haber verir:

// grid: 81 rakam, 0 = boş. Yerinde çözer; guesses denenen yerleştirme sayısı
public static bool Solve(int[] grid, out long guesses, bool mostConstrainedFirst = true)
{
    long count = 0;
    // Çakışan ipuçlarını baştan reddet; arama bunu ancak uzun bir yürüyüşten sonra fark eder
    for (int i = 0; i < 81; i++)
    {
        int given = grid[i];
        if (given == 0) continue;
        grid[i] = 0;
        bool ok = CanPlace(i, given);
        grid[i] = given;
        if (!ok)
        {
            guesses = 0;
            return false;
        }
    }

    bool solved = Fill();
    guesses = count;
    return solved;

    bool Fill()
    {
        // En az adaylı boş hücreyi (en kısıtlı) ya da düz ilk boş hücreyi seç
        int best = -1, bestCount = 10;
        for (int i = 0; i < 81 && bestCount > 1; i++)
        {
            if (grid[i] != 0) continue;
            int candidates = 0;
            for (int d = 1; d <= 9; d++) if (CanPlace(i, d)) candidates++;
            if (candidates < bestCount) (best, bestCount) = (i, candidates);
            if (!mostConstrainedFirst) break;
        }

        if (best == -1) return true;      // boş hücre kalmadı
        if (bestCount == 0) return false; // çıkmaz: buda

        for (int d = 1; d <= 9; d++)
        {
            if (!CanPlace(best, d)) continue;
            grid[best] = d;
            count++;
            if (Fill()) return true;
            grid[best] = 0;                // geri al
        }

        return false;
    }

    bool CanPlace(int index, int digit)
    {
        int row = index / 9, col = index % 9;
        int boxRow = row / 3 * 3, boxCol = col / 3 * 3;
        for (int k = 0; k < 9; k++)
        {
            if (grid[row * 9 + k] == digit || grid[k * 9 + col] == digit) return false;
            if (grid[(boxRow + k / 3) * 9 + boxCol + k % 3] == digit) return false;
        }

        return true;
    }
}

Wikipedia'nın Sudoku maddesindeki örnek bulmacayla (51 boş hücre):

first empty cell: placements tried=4208
sudoku solved=True, placements tried=51
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9

İlk boş hücreden giden versiyon 4.208 yerleştirme deniyor. En kısıtlı hücreyi seçen versiyon 51 boş hücreyi tam 51 yerleştirmeyle dolduruyor: bu bulmacada her adımda tek adaylı bir hücre var ve arama hiç geri dönmüyor. Her adımda en kısıtlı hücreyi bulmak için 81 hücreyi taramak pahalı görünür, ama ağacı küçültmenin getirisi bu maliyeti fazlasıyla karşılıyor. Başta çakışan ipuçlarını reddetmemiz de bir budama: testteki, ilk satırına iki tane 1 yazılmış tahta bu kontrol olmadan iki dakikada bitmedi ve test koşusunu durdurmak zorunda kaldım.

Gerçek Senaryo: Ürün Konfigüratörü

Bookstore, kitapları seçenekli satıyor: baskı türü (ciltli, karton kapak, e-kitap), dil (EN, TR), hediye paketi ve imza. Seçeneklerin birbiriyle kuralları var ve müşterinin bir bütçesi var. Satış sayfası "bu bütçeyle alınabilecek geçerli paketler"i listelemek istiyor:

public sealed record BundleOption(string Slot, string Value, decimal Price);

public static class BundleConfigurator
{
    // Her slot'tan bir seçenek; kurallar kısmi paketi mümkün olan en erken anda reddeder
    public static IEnumerable<BundleOption[]> Valid(
        IReadOnlyList<BundleOption[]> slots,
        Func<IReadOnlyList<BundleOption>, bool> isAllowed,
        decimal budget)
    {
        List<BundleOption> chosen = [];
        return Build(0, 0m);

        IEnumerable<BundleOption[]> Build(int slot, decimal total)
        {
            if (slot == slots.Count)
            {
                yield return [.. chosen];
                yield break;
            }

            foreach (BundleOption option in slots[slot])
            {
                if (total + option.Price > budget) continue; // buda: bütçe aşıldı
                chosen.Add(option);
                if (isAllowed(chosen))                       // buda: kural ihlali
                {
                    foreach (BundleOption[] bundle in Build(slot + 1, total + option.Price))
                    {
                        yield return bundle;
                    }
                }

                chosen.RemoveAt(chosen.Count - 1);
            }
        }
    }
}

BundleOption[][] slots =
[
    [new("Format", "Hardcover", 450m), new("Format", "Paperback", 280m), new("Format", "Ebook", 190m)],
    [new("Language", "EN", 0m), new("Language", "TR", 0m)],
    [new("Wrap", "GiftWrap", 40m), new("Wrap", "NoWrap", 0m)],
    [new("Signature", "Signed", 120m), new("Signature", "Unsigned", 0m)],
];

bool Allowed(IReadOnlyList<BundleOption> c)
{
    bool Has(string v) => c.Any(o => o.Value == v);
    if (Has("Ebook") && (Has("GiftWrap") || Has("Signed"))) return false;   // e-kitaba fiziksel ek olmaz
    if (Has("TR") && Has("Hardcover")) return false;                       // TR baskının ciltlisi yok
    if (Has("Signed") && !Has("Hardcover")) return false;                  // imzalı kopyalar yalnız ciltli
    return true;
}

List<BundleOption[]> bundles = [.. BundleConfigurator.Valid(slots, Allowed, budget: 600m)];

Hardcover + EN + GiftWrap + Unsigned        490
Hardcover + EN + NoWrap + Signed            570
Hardcover + EN + NoWrap + Unsigned          450
Paperback + EN + GiftWrap + Unsigned        320
Paperback + EN + NoWrap + Unsigned          280
Paperback + TR + GiftWrap + Unsigned        320
Paperback + TR + NoWrap + Unsigned          280
Ebook + EN + NoWrap + Unsigned              190
Ebook + TR + NoWrap + Unsigned              190
valid bundles=9 of 24 combinations

24 kombinasyondan 9'u geçerli. Önemli olan kuralın kısmi paket üzerinde çalışması: Hardcover + TR ikinci slot'ta reddedildiği için altındaki 4 kombinasyon hiç üretilmiyor; ciltli, imzalı ve hediye paketli bir paket 610 ile bütçeyi aştığı an kesiliyor. Bu yüzden kurallar "henüz seçilmemiş slot'lar hakkında bir şey varsayma" disipliniyle yazılmalı: Has("Signed") && !Has("Hardcover") kuralı, sıralama sayesinde (format her zaman ilk slot) kısmi pakette de doğru çalışıyor; slot sırası değişirse kural erken ve yanlış reddedebilir. Backtracking'in testleri:

Test run summary: Passed!
  total: 12
  failed: 0
  succeeded: 12
  skipped: 0
  duration: 300ms

Üretimde Dikkat

Sınır koy. Kullanıcı girdisine bağlı bir backtracking (konfigüratördeki slot ve seçenek sayısı admin panelinden artırılabiliyorsa) bir gün exponential duvara çarpar. Sonuç sayısına bir üst sınır (Take(100)), aramaya bir CancellationToken ya da süre sınırı ekle; endpoint'in 30 saniye boyunca bir CPU (Central Processing Unit) çekirdeğini kilitlemesi bir hizmet aksamasıdır.

Ölçeği test verisinden değil gerçek veriden tahmin et. 4 slot ve 2-3 seçenekle her şey anında çalışır; 15 slot ve 5 seçenek 5¹⁵ ≈ 30 milyar kombinasyon demektir. Budamanın ne kadar keseceğini bilmek için node sayacını (N-Queens'teki nodes gibi) production log'una koymak ucuz ve öğreticidir.

Backtracking'in yetmediği yer. Kısıtlar çok ve karmaşıksa (ders programı, vardiya planlama, depo yerleşimi), kendi backtracking'ini yazmak yerine bir constraint solver ya da tamsayı programlama aracı kullanmak çoğu zaman doğru karardır. Bu araçlar da içeride budamalı arama yapar, ama kısıt yayılımı (constraint propagation) gibi çok daha güçlü tekniklerle.

Paylaşılan state ve thread'ler. current, used ve chosen paylaşılan mutable state; iterator'ı iki thread'den aynı anda tüketmek ya da sonuçları kopyalamadan saklamak sonuçları bozar. Her yield return [.. current] bu yüzden bir kopya döndürüyor.

Sık Düşülen Tuzaklar

Exponential maliyeti küçük test input'unda fark etmemek. 8 elemanın permutation'ları 25 ms sürer ve test yeşildir; 11 eleman 4 saniye sürdü, 13 eleman tahminen on dakikayı aşar. Testlerde büyüme hızını görmek için birkaç farklı boyutla ölçüm yap.

State'i geri almayı unutmak. used[i] = false ya da chosen.RemoveAt(...) eksikse ilk dal sonraki dalları zehirler; sonuç eksik çıkar ve hata exception vermez. Sudoku'da grid[best] = 0 satırını silmek, çözümü olan bir bulmacayı "çözümsüz" ilan ettirir.

Sonucu kopyalamadan döndürmek. yield return current; yazarsan tüketici her seferinde aynı array referansını alır; ToList() ile toplanan bütün permutation'lar son değeri gösterir.

Budamayı yanlış yerde yapmak. Kısıt kontrolü yaprağa (tam çözüme) kadar ertelenirse kod doğru ama kaba kuvvetle aynı hızdadır; N-Queens'teki 19 milyona karşı 2.057 farkı tamamen kontrolün yerinden geliyor. Kontrolü seçimin yapıldığı an yap.

Küçük Bir Deneme

★☆☆ Combinations'ı kullanarak Bookstore'un 6 kitaplık bir listesinden toplam fiyatı tam 100 olan 3'lü setleri bul. Sonra aynı işi toplam fiyatı aşan dalları budayarak yap ve ziyaret edilen node sayılarını karşılaştır.

★★☆ Permutations'ı yield return yerine bir Action<T[]> callback'i alacak şekilde yeniden yaz ve 10 elemanla iki versiyonun süresini ölç. Fark nereden geliyor?

★★★ N-Queens'te sütun ve çapraz takibini bool[] yerine üç int bit mask ile yap (boş sütunlar ~(cols | diag | anti)). n = 12 için çözüm sayısını (14.200) ve süreyi iki versiyonla karşılaştır.

Backtracking bütün seçenekleri dener ve umutsuz olanları budar. Bir sonraki yazıda tam tersi bir strateji var: her adımda o an en iyi görünen seçimi yap, bir daha asla geri dönme. Greedy algoritmalar bazen şaşırtıcı derecede iyi çalışır, bazen de sessizce yanlış cevap verir; ikisini nasıl ayırt edeceğimize bakacağız.