AlgoPit

N-Queens Problemi (Geri İzleme Algoritması)

N-Queens problemi, n×n boyutundaki bir satranç tahtasına n adet veziri, hiçbirinin birbirini tehdit etmeyecek şekilde yerleştirme sorunudur. Vezirler, yatay, dikey ve çapraz yönlerde hareket edebildiği için, aynı satır, sütun veya çaprazda başka bir vezir olmamalıdır. Bu problem, geri izleme (backtracking) algoritmasının klasik bir uygulamasıdır.

Avantajlar

  • Her boyuttaki satranç tahtasındaki tüm olası çözümleri bulabilir
  • Çözümü olmayan durumları etkili bir şekilde tespit eder
  • Geri izleme yaklaşımı sayesinde, geçersiz dal keşfedildiği an bu daldan vazgeçer
  • Çözüm alanını sistematik olarak araştırır

Dezavantajlar

  • Üstel zaman karmaşıklığına sahiptir (O(n!)), bu da büyük n değerleri için işlemleri yavaşlatır
  • Tahta boyutu arttıkça çözüm sayısı hızla artar, bu da hesaplama süresini uzatır
  • Tüm çözümleri bulmak gerekliyse, bu faktöriyel karmaşıklık kaçınılmazdır
  • Büyük değerler için bellek kısıtlamaları olabilir

İnteraktif Demo

N-Queens probleminin çözümünü görmek için satranç tahtası boyutunu ayarlayın. Düşük değerler için çözümü hızlıca görebilirsiniz. (Not: n ≥ 9 için hesaplama zaman alabilir.)

n = 1 için 1 çözüm, n = 4 için 2 çözüm, n = 8 için 92 çözüm vardır. n = 2 ve n = 3 için çözüm yoktur.

Bulunan Çözüm Sayısı: 0
Çözüm bulunamadı

Bu boyut için çözüm bulunamadı.

Kod Örnekleri

N-Queens problemi için geri izleme algoritmasının farklı programlama dillerindeki implementasyonları.

N-Queens Problemi - TypeScript
1function solveNQueens(n: number): number[][] {
2  // Tüm çözümleri saklayan dizi
3  const solutions: number[][] = [];
4  
5  // Satranç tahtasını temsil eden dizi (her satırdaki vezirin sütun pozisyonu)
6  const board: number[] = Array(n).fill(-1);
7  
8  // Vezir yerleştirmenin güvenli olup olmadığını kontrol eden yardımcı fonksiyon
9  function isSafe(row: number, col: number): boolean {
10    // Daha önceki satırlardaki vezirleri kontrol et
11    for (let i = 0; i < row; i++) {
12      // Aynı sütunda başka bir vezir var mı?
13      if (board[i] === col) {
14        return false;
15      }
16      
17      // Aynı çaprazda başka bir vezir var mı?
18      if (Math.abs(i - row) === Math.abs(board[i] - col)) {
19        return false;
20      }
21    }
22    
23    return true;
24  }
25  
26  // Geri izleme (backtracking) fonksiyonu
27  function backtrack(row: number): void {
28    // Tüm satırlar dolduruldu, bir çözüm bulundu
29    if (row === n) {
30      // Bulunan çözümü kaydet
31      solutions.push([...board]);
32      return;
33    }
34    
35    // Mevcut satır için tüm olası sütunları dene
36    for (let col = 0; col < n; col++) {
37      // Eğer bu pozisyona vezir yerleştirmek güvenliyse
38      if (isSafe(row, col)) {
39        // Veziri yerleştir
40        board[row] = col;
41        
42        // Sonraki satır için recursion
43        backtrack(row + 1);
44        
45        // Geri al (backtrack) - vazgeçme adımı
46        board[row] = -1;
47      }
48    }
49  }
50  
51  // 0. satırdan itibaren geri izleme algoritmasını başlat
52  backtrack(0);
53  
54  return solutions;
55}

Algoritma Nasıl Çalışır?

N-Queens problemi, geri izleme (backtracking) algoritması kullanarak çözülür. Geri izleme, bir çözüm arama yöntemidir ve özellikle kısıtlama tabanlı problemlerde kullanılır.

Algoritmanın Çalışma Mantığı

  1. Adım Adım İlerleme: Algoritma ilk satırdan başlayarak, her satıra bir vezir yerleştirir.
  2. Güvenlik Kontrolü: Her yerleştirme adımında, yeni vezirin diğer vezirleri tehdit edip etmediği kontrol edilir.
  3. Derinleştirme: Eğer yerleştirme güvenliyse, algoritma bir sonraki satıra geçer.
  4. Geri Adım: Eğer mevcut konfigürasyon bir çözüme götürmüyorsa (yani sonraki satırlara güvenli yerleştirme yapılamıyorsa), algoritma bir önceki adıma döner ve farklı bir yerleştirme dener.
  5. Çözüm Bulma: Tüm vezirler yerleştirildiğinde (yani son satıra da vezir yerleştirildiğinde), bir çözüm bulunmuş demektir.

Güvenlik Kontrolü Mantığı

N-Queens probleminde bir yerleştirmenin güvenli olması için üç koşul sağlanmalıdır:

  • Satır Kontrolü: Her satıra tam olarak bir vezir yerleştirildiğinden, aynı satırda iki vezir olamaz.
  • Sütun Kontrolü: Aynı sütunda birden fazla vezir olmamalıdır.
  • Çapraz Kontrol: Vezirlerin birbirlerini çapraz olarak tehdit etmemeleri için, çaprazlarda başka vezir olmamalıdır.

Optimizasyon Teknikleri

N-Queens problemi için daha verimli çözümler elde etmek için kullanılabilecek bazı teknikler:

  • Simetri Kullanma: Satranç tahtasının simetrik özelliklerinden faydalanarak arama uzayını küçültme.
  • Bit Manipülasyonu: Vezir yerleşimlerini ve çatışma kontrollerini bit işlemleriyle hızlandırma.
  • Kısıt Programlama: Problemi kısıt programlama yaklaşımı ile formüle etme ve çözme.
  • Paralel Hesaplama: Büyük n değerleri için farklı arama dallarını paralel olarak işleme.

İlginç Özellikler

N-Queens problemi şu ilginç özelliklere sahiptir:

  • n = 1 için 1 çözüm vardır (1x1 tahtada 1 vezir).
  • n = 2 ve n = 3 için hiçbir çözüm yoktur (iki veya üç veziri tehdit etmeden yerleştirmek imkansızdır).
  • n ≥ 4 için ise en az bir çözüm her zaman vardır.
  • n = 8 için 92 farklı çözüm vardır.
  • n = 9 için 352 çözüm, n = 10 için 724 çözüm vardır.
  • Çözüm sayısı n değeri arttıkça hızla artmaktadır.