N-Vezir Problemi

#Nasıl çalışır?

Geri izleme (backtracking), bir çözümü adım adım kuran ve bir adımın çözüme götürmeyeceği anlaşılınca o adımı geri alıp başka bir seçeneği deneyen bir arama tekniğidir. Tüm olasılıkları körü körüne denemek yerine, umutsuz dalları erkenden budar.

N-Vezir problemi bunun klasik örneğidir: n × n bir satranç tahtasına n vezir, hiçbiri diğerini tehdit etmeyecek şekilde yerleştirilmelidir. Vezir aynı satır, sütun ve çaprazdaki her taşı tehdit eder.

Her satıra tam bir vezir gelmesi gerektiği için satır satır ilerlenir. Bir satırda, yukarıdaki vezirlerin tehdit etmediği ilk sütuna vezir konur ve sonraki satıra geçilir. Bir satırda güvenli sütun kalmazsa önceki satırdaki vezir kaldırılır ve bir sonraki sütunu denenir.

8 × 8 tahtada 92 çözüm vardır. Vezirleri rastgele 64 kareye dağıtmanın 4 milyardan fazla yolu varken geri izleme yalnızca birkaç bin kare dener.

#Kendin dene

#Adım adım

1. 01İlk satırdan başla.
2. 02Satırdaki her sütun için: yukarıdaki bir vezir bu kareyi tehdit ediyorsa atla.
3. 03Güvenliyse vezir koy ve sonraki satıra geç; son satır da dolduysa çözüm bulundu.
4. 04Bir satırda güvenli kare kalmazsa geri dön: önceki satırın vezirini kaldır ve oradaki sonraki sütunu dene.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

def solve(n: int):
    """First solution as a list of columns (one per row), or None."""
    queens = []  # queens[row] = column

    def safe(row: int, col: int) -> bool:
        return all(c != col and abs(c - col) != row - r for r, c in enumerate(queens))

    def place(row: int) -> bool:
        if row == n:
            return True
        for col in range(n):
            if safe(row, col):
                queens.append(col)
                if place(row + 1):
                    return True
                queens.pop()  # dead end: backtrack
        return False

    return queens if place(0) else None


def count(n: int) -> int:
    """All solutions, with sets of used columns and diagonals for O(1) checks."""
    cols, diag1, diag2 = set(), set(), set()

    def place(row: int) -> int:
        if row == n:
            return 1
        total = 0
        for col in range(n):
            if col in cols or row - col in diag1 or row + col in diag2:
                continue
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            total += place(row + 1)
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)
        return total

    return place(0)


print(" ".join(str(c + 1) for c in solve(4)))  # 1-based columns by row
print(count(8))

#Karmaşıklık

Her satıra bir vezir koymak arama alanını nⁿ'den n!'e indirir; tehdit kontrolüyle budama bunu çok daha aşağı çeker. Sütunlar ve iki çapraz yönü için üç boolean dizi tutulursa her kontrol O(1) olur. Bit maskeleriyle n = 15 civarına kadar tüm çözümler hızla sayılabilir.

#Ne zaman kullanılır?

Geri izleme; Sudoku, bulmacalar, labirent çözme, kısıt sağlama problemleri (ders programı, sınav takvimi), graf boyama ve kombinasyon üretme gibi "kısıtları sağlayan bir yerleşim bul" problemlerinin genel çözüm kalıbıdır.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.

#Bundan sonra

Bu dersi bildiğini varsayan dersler:

• Sudoku Çözücü