Bir labirentte kaybolduğunuzda ne yaparsınız? Bir yola girer, ilerler, eğer karşınıza çıkmaz bir sokak (duvar) çıkarsa geri adım atar ve başka bir alternatifi denersiniz. İnsan aklının bu sezgisel problem çözme tekniği, bilgisayar bilimlerinde **Geri İzleme (Backtracking)** olarak adlandırılan son derece güçlü bir arama algoritmasının temelini oluşturur. Yapay zekalı mikro farelerin (Micromouse) labirent şampiyonalarından Sudoku bulmaca çözücülerine ve satrançta N-Vezir problemine kadar uzanan bu rehberde, 2 boyutlu bir matris üzerinde labirent çözme algoritmasının tüm aşamalarını adım adım kodlayacağız.
---
1. Backtracking (Geri İzleme) Nedir?
Geri izleme; tüm olası çözüm yollarını sistematik olarak araştıran, ancak bir yolun hedefe ulaşamayacağı anlaşıldığı anda **o yolu terk edip bir önceki karar noktasına geri dönen (Pruning / Budama)** özyinelemeli bir optimizasyon tekniğidir.
Brute Force (Kaba Kuvvet) ile Farkı:
Kaba kuvvet her yolu körü körüne sonuna kadar dener. Backtracking ise "Bu adım duvara çarpıyor, o halde bu yönde daha fazla ilerlememe gerek yok" diyerek milyonlarca gereksiz hesaplamayı tek bir satırda budar!
---
2. Labirentin 2 Boyutlu Matris Olarak Temsili
Bilgisayarda bir labirenti temsil etmek için $N imes N$ boyutunda 2 boyutlu bir tamsayı dizisi (Matrix) kullanılır:
Giriş (0,0) ──> [ 0, 1, 0, 0 ]
[ 0, 0, 0, 1 ]
[ 1, 0, 1, 0 ]
[ 0, 0, 0, 9 ] <── Çıkış (3,3)---
3. Güvenli Adım Kontrolü (isSafe Fonksiyonu)
Robotun bir $(x, y)$ koordinatına adım atabilmesi için 3 şartın aynı anda sağlanması gerekir:
1. $x$ ve $y$ koordinatları matris sınırları içinde olmalıdır ($0 \le x < N$ ve $0 \le y < N$).
2. Hedef hücre duvar olmamalıdır (`Labirent[x][y] != 1`).
3. Hedef hücre daha önce ziyaret edilmemiş olmalıdır (`Labirent[x][y] != 2`).
---
4. Tam ve Çalışan Python Kodu
def is_safe(maze, x, y, n):
# Matris sınırları içinde mi ve duvar değil mi?
return 0 <= x < n and 0 <= y < n and maze[x][y] == 0
def solve_maze_util(maze, x, y, n, sol):
# Taban Durumu: Sağ alt köşedeki hedefe ulaşıldı mı?
if x == n - 1 and y == n - 1 and maze[x][y] == 0:
sol[x][y] = 1
return True
# Geçerli bir hücrede miyiz?
if is_safe(maze, x, y, n):
# Hücreyi çözüm yolunun parçası olarak işaretle
sol[x][y] = 1
# 1. Aşağıya gitmeyi dene (x + 1)
if solve_maze_util(maze, x + 1, y, n, sol):
return True
# 2. Sağa gitmeyi dene (y + 1)
if solve_maze_util(maze, x, y + 1, n, sol):
return True
# Çıkmaz sokak! Geri adım at (BACKTRACKING)
sol[x][y] = 0
return False
return False
def solve_maze(maze):
n = len(maze)
sol = [[0 for _ in range(n)] for _ in range(n)]
if not solve_maze_util(maze, 0, 0, n, sol):
print("Labirentin çıkış yolu YOKTUR!")
return False
print("--- BAŞARILI ÇIKIŞ ROTASI (1'ler Rota) ---")
for row in sol:
print(row)
return True
# Test Labirenti (0: Yol, 1: Duvar)
labirent = [
[0, 1, 0, 0],
[0, 0, 0, 1],
[1, 0, 1, 0],
[1, 0, 0, 0]
]
solve_maze(labirent)---
5. Robotik Dünyasındaki Yeri: Micromouse Yarışmaları
Tüm dünyada düzenlenen **Micromouse** yarışmalarında, otonom küçük fare robotlar $16 imes 16$'lık devasa ahşap bir labirentin içine bırakılır. Robotlar önce sağ el kuralı veya DFS ile labirenti keşfeder, ardından Backtracking ve Flood-Fill (Su Doldurma) algoritmalarıyla çıkmaz sokakları hafızasından silerek en hızlı rotayı hesaplar ve rekor sürelerde labirenti tamamlar.
---
6. Kendini Geliştirme Görevi (Challenge)
**Sudoku Çözücü:** 9x9'luk boş hücreleri olan bir Sudoku bulmacasını Backtracking tekniğiyle çözen bir fonksiyon yazın. Satır, sütun ve 3x3'lük blok kurallarını `is_safe` kontrolüyle birleştirin!
---
---
7. N-Vezir (N-Queens) Problemi ile Backtracking Mantığının Zirvesi
Backtracking mantığının satranç tahtasındaki en meşhur uygulaması **N-Vezir Problemi**dir:
1. 1. satıra bir vezir koyulur.
2. 2. satırda tehdit altında olmayan ilk güvenli kareye ikinci vezir koyulur.
3. Eğer bir satırda hiçbir kareye vezir koyulamıyorsa (çıkmaz sokak!), bir önceki satırdaki vezir bir sonraki sütuna kaydırılır (Geri Adım - Backtrack).
4. 8x8'lik standart tahtada bu budama yöntemi sayesinde $4.4$ milyar olası kombinasyon yerine sadece birkaç bin kontrolle tüm 92 geçerli çözüm saniyeler içinde bulunur.
---
Sonuç
Geri izleme (Backtracking), karmaşık karar ağaçlarını budayarak çözüme ulaşmanın en akılcı yoludur. Hata yapıldığında geri dönüp alternatifleri deneme refleksi, algoritmik düşüncenin en büyük kazanımıdır. Diğer projelerimizi [Arduino Projeleri](/projeler) sayfamızda bulabilirsiniz!