OYUN GEOMETRİSİ VE FİZİĞİ · G8
Geri İzleme: Envanter ve Bulmacalar
Seç, dene, olmadıysa geri al — çanta düzenleme, sudoku, Sokoban ve “bu bulmacanın çözümü var mı?”
PRESS ▶ TO START
Bu derste oyunun haritası 🗺️
- Geri izleme kalıbı — seç → dene → geri al; N vezir ile dört satırlık iskelet
- Çanta: eşyalar sığar mı? — ızgara envanter ve “otomatik düzenle” düğmesi; sıra neden her şeyi değiştirir
- Kısıt bulmacaları — sudoku: hangi hücreyle başlamalı? Bulmaca üretmek ve “tek çözümlü mü?”
- Durum uzayında arama — Sokoban: oyuncunun “geri al” tuşu, makinenin çözücüsü; çıkmazları erken görmek
- En değerli yük — taşıma kapasitesi altında en iyi ganimet: al / alma ağacı ve sınırla budama
- Her adımda — elle izleme → canlı demo → kod (JavaScript / Python / C#) → gerçek oyun kaynak kodu
🎮 Bu dersin sonunda…
geri izleme iskeletini ezbere yazabilecek; bir ızgara envanter için “sığar mı / otomatik yerleştir” fonksiyonunu, bir bulmaca için çözücü ve “çözülebilir mi, tek çözümlü mü” denetimini kurabilecek; aramayı budama ve sıralamayla binlerce kat hızlandırmanın yollarını açıklayabileceksiniz.
🤔 ISINMA: ÇANTA TETRİSİ
Resident Evil 4’te (2005) oyuncular saatlerini silah çantasını düzenleyerek geçirdi: tüfeği yatır, pompalıyı döndür, otları köşeye sıkıştır… Oyunun 2023’teki yeni sürümüne tek tuşla “otomatik düzenle” eklendi. O tuşa basınca bilgisayar ne yapıyor?
- Sizin yaptığınızın aynısını: bir eşyayı bir yere koyuyor, sıradakini deniyor; sığmayan çıkınca bir öncekini kaldırıp başka yere koyuyor.
- Buna geri izleme (backtracking) denir. Bilgisayar bilimindeki en genel “bulmaca çözme” yöntemidir.
- Aynı dört satır şunları da çözer: sudoku, Sokoban, bulmaca seviyesinin çözülebilir olup olmadığı, rastgele üretilen zindanda anahtarların kapılardan önce bulunup bulunamayacağı, hangi ganimetin taşınacağı.
- Asıl hüner denemekte değil, denememeyi bilmekte: iyi bir budama ve doğru sıra, bir milyon denemeyi ona indirir. Bu sunumda ikisini de ölçeceğiz.
🎯 Bu konu için bilmeniz gerekenler
Yeşil = gerekli · kesikli = faydalı ama şart değil. Tıklayınca ilgili sunuma gider.
Yığınlar ve Kuyruklar (yığın: son giren ilk çıkar)Yönsüz Graflar (DFS, BFS)Algoritma Analizi (üstel büyüme)
Hash Tabloları (görülen durumlar kümesi)Y15 · Prosedürel Üretim (dalga fonksiyonu çöküşü)Y6 · GOAP (durum uzayında plan arama)
Neden?Derinlik öncelikli arama (DFS) bir labirentte “git, çıkmazsa dön” diyordu. Geri izleme aynı fikirdir; ama labirent önceden çizilmiş değildir: düğümler, yaptığınız seçimlerle ortaya çıkar.
🧰 Kodlamadan korkuyorsanızÖzyineleme (kendini çağıran fonksiyon) bu sunumun tek zor yeri. Her fonksiyon aynı üç satırdan oluşur: seç, dene, geri al. İlk örnekte (4 vezir) çağrıları tahtada tek tek izleyeceğiz; ondan sonrası aynı kalıbın tekrarıdır.
Mini sözlük
| backtracking | geri izleme | Adım adım seçim yap; çıkmaza girince son seçimi geri alıp bir sonrakini dene |
| search tree · state space | arama ağacı · durum uzayı | Olası seçim dizilerinin ağacı · ulaşılabilen bütün durumların kümesi |
| pruning | budama | İşe yaramayacağı belli olan dalı hiç açmamak |
| constraint satisfaction (CSP) | kısıt sağlama problemi | Değişkenlere, bütün kuralları sağlayan değerler atama (sudoku, vezirler, yerleştirme) |
| most constrained variable (MRV) | en kısıtlı değişken | Sıradaki seçim için en az seçeneği kalan yeri alma kuralı |
| grid inventory | ızgara envanter | Eşyaların biçimleriyle yer kapladığı çanta (“envanter tetrisi”) |
| undo · softlock | geri al · kilitlenme | Son hamleyi iptal etme · oyunun bitirilemez duruma düşmesi |
| deadlock | çıkmaz durum | Hiçbir hamle dizisiyle çözüme varılamayan durum (köşeye sıkışmış kutu) |
| knapsack · branch and bound | sırt çantası problemi · dal-sınır | Kapasite altında en değerli seçim · “en iyimser tahmin bile yetmiyorsa” dalı kesme |
LEVEL 0
Geri izleme kalıbı
seç, dene, geri al
Problem: 8 vezir
♛ Bulmacaların “merhaba dünya”sı
- 8 × 8 satranç tahtasına 8 vezir koyun; hiçbiri öbürünü tehdit etmesin (aynı satır, sütun ya da çaprazda iki vezir olmasın).
- 1848’de bir satranç dergisinde soruldu; Gauss da uğraştı. 92 çözümü var.
- Oyunlarda aynı yapıda sorular: “bu parçaları, birbirini ezmeden yerleştir”, “bu kurallara uyan bir düzen bul”.
- Bulmaca oyunlarında doğrudan karşımıza çıkar: The 7th Guest (1993) ve Professor Layton serisinde vezir bulmacaları var.
Kaba kuvvet: hepsini dene
- Her satıra bir vezir koyacağımızı biliyoruz. Her satır için 8 sütun seçeneği: 8⁸ = 16.777.216 tahta.
- Her tahtayı kur, 28 vezir çiftini sına. Bilgisayar için yapılabilir; ama…
- 10 vezir: 10¹⁰ = 10 milyar. 20 vezir: 10²⁶. Evrenin yaşı yetmez.
- İsraf nerede? İlk iki veziri aynı sütuna koyan 2 milyon tahtanın hepsi daha ikinci vezirde ölüydü; yine de 8 vezirin tamamını dizip öyle sınadık.
Fikir: tahtayı baştan sona kurup sonra sınama. Vezirleri birer birer koy; kural bozulduğu an dur, o dalın altındaki her şeyi hiç kurmadan at.
Çizimle: 4 vezir, yedi adımda
Elle izleme tablosunun resmi. Her tahta bir adımın sonu: vezirler yukarıdan aşağı satır satır konuyor; kırmızı kareler üstteki vezirlerin tehdit ettiği yerler. 3. adımda satır 3’ün dört karesi de kırmızı: çıkmaz; son konan vezir (satır 2) kaldırılıp bir sağa kaydırılıyor. 6. adımda satır 4 çıkmaza girince geri alma zinciri ta satır 1’e kadar gidiyor; 7. adım çözüm: 2, 4, 1, 3.
Fikir: seç → dene → geri al
- Satır satır in. Bulunduğun satırda soldan sağa sütunları dene.
- Güvenli bir sütun bulursan: veziri koy (seç) ve bir alt satır için aynı işi yap (dene).
- Alt satırlar çözüme ulaştıysa: bitti.
- Ulaşamadıysa: az önce koyduğun veziri kaldır (geri al) ve bu satırda bir sonraki sütuna geç.
- Bu satırda hiçbir sütun olmadıysa: “buradan çözüm yok” diye üst satıra haber ver; o da kendi vezirini geri alacak.
Geri alınan vezirlerin durduğu yer bir yığındır (son konan ilk kalkar). Özyinelemede bu yığını programlama dili kendisi tutar: her fonksiyon çağrısı bir satırı “hatırlar”.
Elle izleme: 4 vezir (satır, sütun 1’den sayılıyor)
| adım | olay | tahta (satır → sütun) |
|---|---|---|
| 1 | satır 1: sütun 1 güvenli → koy | 1 |
| 2 | satır 2: 1 ✗, 2 ✗, 3 ✓ → koy | 1, 3 |
| 3 | satır 3: 1 ✗ 2 ✗ 3 ✗ 4 ✗ → çıkmaz | 1, 3 |
| 4 | geri al (satır 2); sütun 4 ✓ → koy | 1, 4 |
| 5 | satır 3: 1 ✗, 2 ✓ → koy | 1, 4, 2 |
| 6 | satır 4: hepsi ✗ → çıkmaz; geri al; satır 3: 3 ✗ 4 ✗; geri al; satır 2 bitti; geri al (satır 1) | — |
| 7 | satır 1: sütun 2 → koy; satır 2: 4 ✓; satır 3: 1 ✓; satır 4: 3 ✓ | 2, 4, 1, 3 ✔ |
Toplam 26 kare sınandı, 8 vezir kondu, 4’ü geri alındı. Kaba kuvvet: 4⁴ = 256 tahta.
Canlı: vezirler satır satır ♛
- Ekranı okuyun: solda tahta; mavi daireler konmuş vezirler; pembe kareler onların tehdit ettiği yerler. Kırmızı çarpı: az önce sınanıp tehdit altında bulunan kare. Sarı çerçeve: geri alınan vezirin yeri. Sağda o anki adımın açıklaması ve sayaçlar.
- N = 4, hızı en düşüğe alın ve “⏭ tek adım” ile ilerleyin: önceki slayttaki tabloyu satır satır izleyin. Sayaçlar 26 / 8 / 4’te durmalı.
- N = 6: ilk vezir sütun 1’deyken algoritma 25 kez geri alır. İlk veziri taşımadan çözüm yoktur; algoritma bunu ancak altındaki bütün dalları tüketince “anlar”.
- N = 8, hızı artırın: 876 kare sınanır, 113 vezir konur, 105’i geri alınır. Kaba kuvvetin 16,7 milyon tahtasına karşı.
- Soru: pembe karelere hiç vezir konmuyor. Bu “budama”yı kodda hangi satır yapıyor? (Bir sonraki slayt:
guvenliMi.)
🔎 DEMODA DENEYİN
- Ekranı okuyun: solda tahta; mavi daireler konmuş vezirler; pembe kareler onların tehdit ettiği yerler. Kırmızı çarpı: az önce sınanıp tehdit altında bulunan kare. Sarı çerçeve: geri alınan vezirin yeri. Sağda o anki adımın açıklaması ve sayaçlar.
- N = 4, hızı en düşüğe alın ve “⏭ tek adım” ile ilerleyin: önceki slayttaki tabloyu satır satır izleyin. Sayaçlar 26 / 8 / 4’te durmalı.
- N = 6: ilk vezir sütun 1’deyken algoritma 25 kez geri alır. İlk veziri taşımadan çözüm yoktur; algoritma bunu ancak altındaki bütün dalları tüketince “anlar”.
- N = 8, hızı artırın: 876 kare sınanır, 113 vezir konur, 105’i geri alınır. Kaba kuvvetin 16,7 milyon tahtasına karşı.
- Soru: pembe karelere hiç vezir konmuyor. Bu “budama”yı kodda hangi satır yapıyor? (Bir sonraki slayt:
guvenliMi.)
🔗 Başka gözle: etkileşimli anlatımlar ve yazılar
Aynı konuyu başka bir anlatımla, kendi elinizle oynayarak görmek çok işe yarar. Kartlar yeni sekmede açılır; çoğu İngilizce ama görsel ve etkileşimli.
🔗 Maze Algorithms
Jamis Buck
Labirent üreten on iki algoritmayı (Kruskal, Prim, geri izleme…) yan yana, canlı izleyin.
🔗 cp-algorithms
cp-algorithms.com
Algoritmaların matematiksel ve kod düzeyinde ayrıntılı anlatımı (geometri, graf, veri yapıları).
🔗 Data Structure Visualizations
David Galles (USF)
Neredeyse her veri yapısı için bir oyun alanı: ekle, sil, ara düğmeleriyle yapının nasıl değiştiğini izleyin.
Kod: geri izlemenin iskeleti (1/2)
Kod: geri izlemenin iskeleti (2/2)
🎒 Kodu okuyalım
| ifade | ne demek | neden böyle |
|---|---|---|
if (satir === n) return true | taban durum: yapacak seçim kalmadı | Özyinelemenin durduğu yer. Buraya ancak bütün satırlar kurallara uyarak dolduysa gelinir. |
for (sutun …) | bu adımın seçenekleri | Her geri izleme probleminde soru aynı: “bu adımda neler seçilebilir?” |
if (!guvenliMi(…)) continue | budama | Kuralı bozan seçeneğin altındaki bütün ağaç hiç açılmaz. Kaba kuvvetten farkın tamamı bu satır. |
vezirler[satir] = sutun | seç | Durumu değiştir. |
if (yerlestir(…, satir + 1)) return true | dene | Kalan problemi (daha küçük, aynı biçimde) kendine sor. “true” gelirse yukarı aynen ilet. |
vezirler.length = satir | geri al | Durumu seçimden önceki hâline getir. En sık unutulan satır: unutulursa eski vezirler tahtada kalır. |
return false | bu adımda hiçbir seçenek olmadı | Çağıran, kendi seçimini geri alıp bir sonrakini deneyecek. |
ÖnermeGeri izleme, çözüm varsa bulur, yoksa bütün ağacı tüketip “yok” der (eksiksizdir). En kötü durumda süre üsteldir: dallanma b, derinlik d ise bd düğüm. Budama bu sayıyı azaltır ama üsteli genelde yok etmez; bu yüzden pratikte her şey budamanın ve seçim sırasının kalitesine bağlıdır.
🌱 Isınma kodu: bu kare güvenli mi?
Önceki her vezir için:
for (let i = 0; i < row; i++) içinde if (queens[i] === col) return false; (aynı sütun) ve if (Math.abs(queens[i] - col) === row - i) return false; (çapraz: yatay uzaklık = dikey uzaklık). Döngü biterse return true.🐍 Laboratuvar: kaç çözüm var?
İç içe bir yardımcı fonksiyon yazın:
def yerlestir(vezirler): · if len(vezirler) == n: return 1 · toplam = 0 · her sutun için güvenliyse (all(v != sutun and abs(v - sutun) != len(vezirler) - i for i, v in enumerate(vezirler))) toplam += yerlestir(vezirler + [sutun]) · return toplam. En sonda return yerlestir([]). İlk çözümde durmayın: hepsini sayın.Quiz 1 · geri izleme
Bir geri izleme fonksiyonu yazdınız; küçük örneklerde doğru, büyüklerde “çözüm yok” diyor (oysa var). Tahtayı yazdırınca, artık geçerli olmayan eski seçimlerin hâlâ üstünde durduğunu görüyorsunuz. Hangi satır eksik?
Seç – dene – geri al üçlüsünün üçüncüsü eksik. Başarısız bir denemeden sonra durum eski hâline getirilmezse, sonraki seçenekler kirli bir tahta üzerinde sınanır ve geçerli seçenekler de “çakışıyor” görünür. Taban durum eksik olsaydı fonksiyon hiç bitmezdi; budama eksik olsaydı sonuç doğru ama çok yavaş olurdu.
LEVEL 1
Çanta: eşyalar sığar mı?
ızgara envanter ve otomatik düzenleme
Problem: envanter tetrisi
🎮 Biçimi olan eşyalar
- Diablo (1996): kılıç 1 × 3, zırh 2 × 3, iksir 1 × 1. Çantanın alanı değil biçimi önemli.
- Resident Evil 4 (2005): silah çantası başlı başına bir mini oyun. Yeni sürümde (2023) “otomatik düzenle” tuşu.
- Escape from Tarkov, DayZ: çanta içinde çanta; yelek, sırt çantası, cepler.
- Backpack Hero, Dredge, Save Room: oyunun kendisi çanta düzenlemek.
- Motorun cevaplaması gereken sorular: “bu eşya buraya sığar mı?”, “çantada herhangi bir yere sığar mı?”, “yerdeki ganimetin hepsi sığar mı; nasıl?”
İlk akla gelen: sığdığı ilk yere koy
Eşyaları sırayla al; çantayı tara; sığdığı ilk yere bırak; geri dönme (açgözlü yerleştirme).
- Hızlı ve basit. Çoğu zaman da çalışır.
- Ama bazen yanlış “sığmıyor” der: ilk eşyayı kötü yere koyduysa sonradan gelen büyük eşyaya yer kalmaz; oysa başka bir düzende hepsi sığardı.
- Oyuncu elle sığdırabildiği şeyi “otomatik düzenle”nin sığdıramadığını görürse o tuşa bir daha basmaz.
Çözüm: aynı “ilk yere koy” kuralı; ama sığmayan eşya çıkınca vazgeçme: bir öncekini kaldır, onu bir sonraki uygun yere koy, yeniden dene. Vezirlerdeki kalıbın aynısı; “sütun” yerine “konum ve yön”.
Çizimle: 4 × 2 çanta, bir bıçak, bir tüfek
Bıçak dik konursa iki satırı birden keser; 4 kare uzunluğundaki tüfeğe boş tam satır kalmaz: geri al. Dört dik konumun hepsi başarısız olur, ancak yatık bıçakla sığar (5. deneme). Önce büyük eşyayı (tüfeği) koyarsak ilk denemede sığar: en zoru önce.
Fikir: aynı kalıp; ve sıra neden önemli?
| N vezir | çanta | |
|---|---|---|
| adım | sıradaki satır | sıradaki eşya |
| seçenekler | 8 sütun | her yön × her (x, y) |
| budama | tehdit altında mı? | taşıyor ya da dolu kareye geliyor mu? |
| geri al | veziri kaldır | eşyanın karelerini boşalt |
| taban | satırlar bitti | eşyalar bitti |
- Bedava budama: eşyaların toplam alanı çantadan büyükse hiç deneme.
- Sıra: hangi eşyayı önce koymalı? En zoru: büyük ve uzun olanları. Küçükler sonradan boşluklara girer; tersi olmaz.
- Genel ilke: başarısız olacaksan erken ol. Zor seçim başta yapılırsa, yanlışlığı ağacın tepesinde, ucuzken anlaşılır.
Elle izleme: 4 × 2 çanta, bıçak (1 × 2) ve tüfek (4 × 1)
Sıra 1: önce bıçak, sonra tüfek
| deneme | bıçak | tüfek | sonuç |
|---|---|---|---|
| 1 | dik, (0,0) | boş tam satır yok | geri al |
| 2 | dik, (1,0) | yok | geri al |
| 3 | dik, (2,0) | yok | geri al |
| 4 | dik, (3,0) | yok | geri al |
| 5 | yatık, (0,0) | (0,1) ✓ | sığdı |
Dik duran bıçak iki satırı da keser; tüfeğe tam satır kalmaz. 5 yerleştirme, 4 geri alma. Açgözlü yöntem 1. denemede “sığmıyor” derdi.
Sıra 2: önce tüfek, sonra bıçak
Tüfek (0,0); bıçak dik sığmaz, yatık (0,1) ✓. 2 yerleştirme, 0 geri alma.
Demodaki 10 eşyalı çantada aynı fark: büyükten küçüğe 10 deneme, küçükten büyüğe 2.248.
Canlı: çantayı bilgisayar düzenlesin 🎒
- Ekranı okuyun: solda 8 × 5 çanta; sağda eşyalar, deneneceği sırayla (yerleşenler soluk ve ✓). Altında son olay ile “yerleştirme denemesi” ve “geri alma” sayaçları.
- Silah çantası, küçükten büyüğe (başlangıç): ▶. Otlar ve mermiler sol üst köşeyi doldurur; sıra tüfeğe gelince yer kalmamıştır. Algoritma küçükleri tek tek söküp taşır: 2.248 deneme. Hızı artırın ya da “⏩ sonuna git”.
- Sırayı “büyükten küçüğe” yapın: 10 deneme, sıfır geri alma. Aynı eşyalar, aynı algoritma.
- “Döndürmek serbest”i kapatın (büyükten küçüğe): 1.432 denemeden sonra “SIĞMIYOR”. Algoritma bunu ancak bütün yerleşimleri tüketerek söyleyebilir: “yok” demek “var” demekten pahalıdır.
- Şekilli eşyalar (L, T, Z biçimleri): büyükten küçüğe 104, küçükten büyüğe 78.786 deneme. Biçim karmaşıklaştıkça sıra daha da önem kazanır.
- Sığmayan çanta: toplam alan 37 kare (40’tan az!) ama üç uzun silah 5 satıra sığmaz. Alan denetimi gerekli, yeterli değil.
🔎 DEMODA DENEYİN
- Ekranı okuyun: solda 8 × 5 çanta; sağda eşyalar, deneneceği sırayla (yerleşenler soluk ve ✓). Altında son olay ile “yerleştirme denemesi” ve “geri alma” sayaçları.
- Silah çantası, küçükten büyüğe (başlangıç): ▶. Otlar ve mermiler sol üst köşeyi doldurur; sıra tüfeğe gelince yer kalmamıştır. Algoritma küçükleri tek tek söküp taşır: 2.248 deneme. Hızı artırın ya da “⏩ sonuna git”.
- Sırayı “büyükten küçüğe” yapın: 10 deneme, sıfır geri alma. Aynı eşyalar, aynı algoritma.
- “Döndürmek serbest”i kapatın (büyükten küçüğe): 1.432 denemeden sonra “SIĞMIYOR”. Algoritma bunu ancak bütün yerleşimleri tüketerek söyleyebilir: “yok” demek “var” demekten pahalıdır.
- Şekilli eşyalar (L, T, Z biçimleri): büyükten küçüğe 104, küçükten büyüğe 78.786 deneme. Biçim karmaşıklaştıkça sıra daha da önem kazanır.
- Sığmayan çanta: toplam alan 37 kare (40’tan az!) ama üç uzun silah 5 satıra sığmaz. Alan denetimi gerekli, yeterli değil.
Kod: “buraya sığar mı?” ve otomatik yerleştirme (1/2)
Kod: “buraya sığar mı?” ve otomatik yerleştirme (2/2)
🎒 Kodu okuyalım
| ifade | ne demek | neden böyle |
|---|---|---|
izgara[yy][xx] !== -1 | kare dolu | Izgara, her karede “hangi eşya” bilgisini tutar: −1 boş. Önce satır (y), sonra sütun (x). |
x + w > GEN | sağdan taşıyor | Sınır denetimi önce: yoksa dizi dışına bakarsınız. |
sigarMi | tek bir konum için evet / hayır | Oyuncu eşyayı sürüklerken yeşil / kırmızı gölgeyi veren fonksiyon da budur. |
yonler | yatık ve 90° dönmüş | Kare eşyada ikisi aynı: boşuna iki kat iş yapma. L, T gibi biçimlerde dört yön (ve ayna) olur. |
doldur(…, i) / doldur(…, -1) | seç / geri al | Aynı fonksiyon, iki değer. Geri alma, seçimin tam tersi olmalı. |
alan > GEN * YUK → false | bir satırlık budama | Aramaya girmeden cevap. Her geri izlemede önce “bedava” denetimleri arayın. |
sort(… b.w * b.h - a.w * a.h) | büyükten küçüğe | Algoritmaya dokunmadan 200 kat hız. Daha da iyisi: en uzun kenara göre sıralamak. |
Önermen eşya ve K kareli çantada arama ağacı en çok (2K)n düğümlüdür (her eşya için 2 yön × K konum). Dikdörtgenleri bir dikdörtgene sığdırma problemi NP-zordur: her durumda hızlı çalışan bir yöntem bilinmiyor. Oyun çantaları küçük olduğu (40–100 kare) ve iyi sıralama çoğu zaman geri almayı sıfıra indirdiği için pratikte sorun olmaz; yine de bir deneme sınırı koyun.
Oyunlarda: çantadan pentominoya
🎮 Tasarımcının kararları
- Otomatik düzenleme ne kadar iyi olmalı? Resident Evil 4’te çantayı düzenlemek oyunun zevklerinden biri; yeni sürümde tuş var ama elle düzenlemek hâlâ serbest. Backpack Hero’da düzenleme oyunun kendisi: otomatik çözücü olsaydı oyun kalmazdı.
- “Yerden alınca sığar mı?” Diablo’da eşyayı alınca oyun ilk uygun yere koyar (açgözlü); sığmazsa “yer yok” der ve düzenlemeyi oyuncuya bırakır. Hızlı ve öngörülebilir.
- Ganimet üretimi: “bu sandıktan çıkanların hepsi oyuncunun çantasına sığabilmeli” kuralı varsa, üretici her sandığı çözücüyle sınar (Y15: üret ve sına).
- Bina / üs yerleştirme: strateji oyununda YZ’nin binaları haritaya dizmesi aynı problemdir; kareler arazi, eşyalar bina.
Aynı problemin ünlü akrabaları
- Pentomino: beş kareden oluşan 12 parçayı 6 × 10’luk kutuya sığdır. 2.339 çözümü var; ilkini bulmak geri izlemeyle saniyeden kısa sürer. Arthur C. Clarke’ın romanlarına ve sayısız bulmaca oyununa (Blokus, Katamino, The Talos Principle’ın kapı bulmacaları) girdi.
- Tam örtme ve “dans eden bağlar”: Donald Knuth 2000’de bu tür “her kareyi tam bir kez ört” problemleri için geri almayı çok ucuzlatan bir veri yapısı yayımladı (Dancing Links): elemanı bağlı listeden çıkarıp aynı işaretçilerle geri takmak. Bağlı Listeler sunumundaki çift yönlü listenin en şık kullanımı.
- Tetris parçaları da (dört kare: tetromino) aynı ailedendir; çanta oyunlarına “envanter tetrisi” denmesi bundan.
- Gerçek dünya: kamyon yükleme, kumaş kesimi, çip üzerinde devre yerleşimi.
🧪 Canlı laboratuvar: eşya buraya sığar mı?
Başlangıç kodu yalnızca tek kareye bakar: 6 × 2’lik tüfek sağdan taşsa bile “sığar” der ve sağdaki görsel ilk hatada durur. İki parça: (1) sınır:
if (x < 0 || y < 0 || x + w > grid[0].length || y + h > grid.length) return false; (2) iki döngü: for (let yy = y; yy < y + h; yy++) for (let xx = x; xx < x + w; xx++) if (grid[yy][xx] !== 0) return false; sonra return true;.Quiz 2 · çanta
Oyununuzun “otomatik düzenle” tuşu eşyaları çantaya küçükten büyüğe sırayla yerleştiriyor ve dolu çantalarda oyun yarım saniye donuyor. En etkili düzeltme?
Küçük eşyalar önce konunca boşluğu parçalar; büyük eşyaya sıra geldiğinde yer kalmaz ve algoritma küçükleri tek tek söküp yeniden dizer (demoda 10 yerine 2.248 deneme). En zor eşyayı önce koymak, başarısızlığı ağacın tepesinde ucuza yakalar. Geri almayı kaldırmak hızlandırır ama sığabilecek çantalara “sığmıyor” dedirtir.
LEVEL 2
Kısıt bulmacaları
sudoku: hangi hücreyle başlamalı?
Problem: kurallara uyan bir doldurma bul
🎮 Sudoku ve akrabaları
- 9 × 9 tahta; her satırda, her sütunda ve her 3 × 3 kutuda 1–9 rakamları birer kez.
- Aynı kalıpta onlarca bulmaca: Kakuro, Nonogram (Picross), KenKen, Minesweeper’da “bu kare kesin mayın mı?”, The Witness’ın panel kuralları.
- Ortak yapı: değişkenler (hücreler), değerler (rakamlar), kısıtlar (kurallar). Adı: kısıt sağlama problemi.
- Oyun programcısının üç işi: çöz (ipucu vermek için), denetle (bu bulmacanın çözümü tek mi?), üret (her gün yeni bulmaca).
İskelet hazır; ama hangi hücre?
Vezirlerdeki kalıp aynen uygulanır: boş bir hücre seç, uyan rakamları sırayla dene, olmazsa geri al.
İlk akla gelen sıra: soldan sağa, yukarıdan aşağı ilk boş hücre.
- Çalışır; gazete bulmacasını birkaç bin denemede çözer.
- Ama ilk boş hücrenin 3–4 adayı olabilir. Yanlışını seçerseniz hata ancak satırlar sonra, onlarca hücre doldurulduktan sonra ortaya çıkar.
- Bu sıraya karşı tasarlanmış bulmacalar var: ilk satırı 9 8 7 6 5 4 3 2 1 olan, 17 ipuçlu bir bulmaca “ilk boş hücre” yöntemine milyonlarca deneme yaptırır.
İnsan nasıl çözüyor? “Şu hücreye yalnızca 5 gelebilir” diyerek: en kısıtlı yerden başlıyor.
Çizimle: hangi boş hücreden başlamalı?
Gazetelerdeki klasik bulmaca. İlk boş hücrenin (turuncu) üç adayı var: üçte iki ihtimalle yanlış tahmin ve sonradan geri alma. Tahtanın ortasındaki hücreye (yeşil) satırı, sütunu ve kutusu yalnızca 5’i bırakıyor: tahmin yok. Algoritma her adımda en az adaylı hücreyi seçerse bu bulmacayı hiç geri almadan 51 adımda bitirir.
Fikir: en az seçeneği olan hücre önce
- Her boş hücre için aday rakamları say (satırında, sütununda ve kutusunda olmayanlar).
- Sıradaki hücre olarak en az adayı olanı seç.
- Tek adaylı hücrede seçim yoktur: tahmin değil, zorunluluk. Yanlış dal hiç açılmaz.
- Sıfır adaylı hücre varsa: hemen geri dön. Çıkmaz, en erken anda görülmüş olur.
- Çantadaki “en zoru önce” kuralının aynısı: başarısız olacaksan erken ol. Yapay zekâ kitaplarındaki adı: en kısıtlı değişken (MRV).
Bir adım ötesi: bir rakam koyunca komşu hücrelerin adaylarını hemen güncelle; biri sıfıra düşerse o rakamı hiç deneme (ileri denetim). Y15’teki dalga fonksiyonu çöküşü tam olarak budur: en az seçenekli hücreyi çökert, komşulara yay, çelişki çıkarsa geri al.
Elle hesap: klasik gazete bulmacasının ilk hamlesi
İlk satır: 5 3 _ _ 7 _ _ _ _. İlk boş hücre: satır 1, sütun 3.
- Satırında: 5, 3, 7. Sütununda: 8. Kutusunda: 5, 3, 6, 9, 8.
- Kullanılanlar {3, 5, 6, 7, 8, 9} → adaylar {1, 2, 4}: üç seçenek, ikisi yanlış.
Tahtanın ortası: satır 5, sütun 5.
- Satırında: 4, 8, 3, 1. Sütununda: 7, 9, 6, 2, 1, 8.
- Kullanılanlar {1, 2, 3, 4, 6, 7, 8, 9} → aday {5}: tek seçenek, tahmin yok.
| hücre seçimi | gazete bulmacası | 17 ipuçlu “zor” bulmaca |
|---|---|---|
| ilk boş hücre | 4.208 yerleştirme | 3.000.000+ (durdurdum) |
| en az adaylı hücre | 51 | 45.267 |
51 boş hücre, 51 yerleştirme: hiç geri alma yok. Bulmaca “mantıkla” çözülebiliyormuş; algoritma bunu kendiliğinden buldu.
Canlı: aynı algoritma, iki sıra 🔢
- Ekranı okuyun: kalın siyah rakamlar ipuçları; mavi rakamlar algoritmanın denemeleri. Yeşil yanan hücre: az önce rakam kondu; kırmızı: rakam geri alındı. Sağda sayaçlar: yerleştirme, geri alma, çıkmaz.
- Gazete bulmacası, “ilk boş hücre”: ▶. Mavi rakamlar üst satırlarda yazılıp silinir, yazılıp silinir… 4.208 yerleştirme. Hızı en sağa çekin.
- Hücre seçimini “en az seçenekli” yapın: rakamlar tahtanın her yerine, bir kez ve doğru konur. 51 yerleştirme, 0 geri alma. Yavaş hızda izleyin: algoritma hep “tek adaylı” bir hücre buluyor.
- Bulmacayı “kaba kuvvete karşı tasarlanmış” yapın, “ilk boş hücre” ile ▶ ve “⏩ sonuna git”: 400.000 denemede çözemez. Aynı bulmaca “en az seçenekli” ile 45.267 yerleştirmede çözülür.
- Soru: iki yöntemin kodu arasındaki fark kaç satır? (Yalnızca
siradakiHucrefonksiyonu.)
🔎 DEMODA DENEYİN
- Ekranı okuyun: kalın siyah rakamlar ipuçları; mavi rakamlar algoritmanın denemeleri. Yeşil yanan hücre: az önce rakam kondu; kırmızı: rakam geri alındı. Sağda sayaçlar: yerleştirme, geri alma, çıkmaz.
- Gazete bulmacası, “ilk boş hücre”: ▶. Mavi rakamlar üst satırlarda yazılıp silinir, yazılıp silinir… 4.208 yerleştirme. Hızı en sağa çekin.
- Hücre seçimini “en az seçenekli” yapın: rakamlar tahtanın her yerine, bir kez ve doğru konur. 51 yerleştirme, 0 geri alma. Yavaş hızda izleyin: algoritma hep “tek adaylı” bir hücre buluyor.
- Bulmacayı “kaba kuvvete karşı tasarlanmış” yapın, “ilk boş hücre” ile ▶ ve “⏩ sonuna git”: 400.000 denemede çözemez. Aynı bulmaca “en az seçenekli” ile 45.267 yerleştirmede çözülür.
- Soru: iki yöntemin kodu arasındaki fark kaç satır? (Yalnızca
siradakiHucrefonksiyonu.)
Kod: sudoku çözücü ve “tek çözümlü mü?” (1/2)
Kod: sudoku çözücü ve “tek çözümlü mü?” (2/2)
🎒 Kodu okuyalım
| ifade | ne demek | neden böyle |
|---|---|---|
adaylar(tahta, i) | bu hücreye konabilecek rakamlar | Budama burada: kurala uymayan rakam listeye hiç girmez. Vezirlerdeki guvenliMi’nin karşılığı. |
s - s % 3 | 3 × 3 kutunun sol üst köşesi | Satır 4 → 3; satır 8 → 6. Tam sayı bölmesiyle de yazılır: floor(s / 3) * 3. |
siradakiHucre | en az adaylı boş hücre | Tek farkı yaratan fonksiyon. enAz = 10 ile başlar: 9’dan büyük herhangi bir sayı. |
| aday yoksa döngü dönmez | çıkmaz → false | Ayrı bir “çıkmaz” denetimi yazmaya gerek yok: boş liste üzerindeki döngü kendiliğinden hiçbir şey yapmaz. |
Python: say parametresi | çözümleri say; ikincide dur | İlk çözümde durmak yerine devam eder. İki çözüm bulunca aramanın gerisi gereksizdir. |
| C#: üretici | dolu tahta üret → hücre sil → tek çözümlü mü? | Bulmaca üretimi = çözücüyü yüzlerce kez çağırmak. Çözücü yavaşsa üretici kullanılamaz. |
ÖnermeSeçim sırası doğruluğu değiştirmez (her sıra aynı çözüm kümesini bulur); yalnızca gezilen ağacın boyunu değiştirir. Sudokuda en kötü durum üsteldir (genelleştirilmiş n² × n² sudoku NP-tamdır); ama 9 × 9 tahtada “en az adaylı hücre” kuralıyla çoğu bulmaca birkaç yüz, en zorları birkaç on bin yerleştirmede çözülür.
Oyunlarda: Simon Tatham’ın bulmaca koleksiyonu
Kaynak: Simon Tatham’s Portable Puzzle Collection, solo.c. 40’tan fazla bulmaca; her platformda, tarayıcıda ve telefonda ücretsiz. Her bulmaca her açılışta yeniden üretilir.
🎮 Yorumlar ne diyor?
- Çözücü önce insan gibi mantık kurallarını dener (tek aday, kesişim, kümeler…). “Hepsi başarısız olursa” geri izlemeye başvurur: en kısıtlı boş kareyi seç, tahmin et, devam et.
- Üretici de aynı fikirle dolu tahta kurar: “boş bir kare seç, olası rakamlardan birini koy, özyinele, gerekirse geri izle”; ve “işin akıllıca kısmı”: her seferinde en az olasılığı olan kareyi seçmek. Az önce ölçtüğümüz kural.
- Zorluk derecesi çözücünün hangi tekniğe ihtiyaç duyduğuyla ölçülür. En üst düzeyin adı: “Unreasonable (tahmin ve geri izleme gerekir)”. Yani: insanın mantıkla çözemeyeceği, deneme-yanılma isteyen bulmaca.
- İyi bulmaca oyunları üretirken geri izlemeyi kullanır ama oyuncudan istemez: üretilen bulmaca yalnızca mantık kurallarıyla çözülebiliyorsa kabul edilir.
- Bilinen sınır: tek çözümlü bir sudoku en az 17 ipucu ister (2012’de bilgisayar aramasıyla kanıtlandı; o arama da devasa bir geri izlemeydi).
🐍 Laboratuvar: bu hücreye hangi rakamlar gelebilir?
Üç kümeyi birleştirin: satır
set(grid[r]), sütun {grid[i][c] for i in range(9)}, kutu (köşesi kr, kc = r - r % 3, c - c % 3) {grid[kr + y][kc + x] for y in range(3) for x in range(3)}. Sonuç: [d for d in range(1, 10) if d not in kullanilan]. Slayttaki iki örnek: (0, 2) → [1, 2, 4]; (4, 4) → [5].Quiz 3 · kısıt bulmacaları
Günlük sudoku oyununuzun üreticisi, bulmacadan ipucu silerken her adımda “çözüm hâlâ tek mi?” diye bakıyor. Bunun için çözücüyü nasıl çalıştırmalı?
İlk çözümde durmak yalnızca “en az bir çözüm var” der. Bütün çözümleri saymak gereksizdir (az ipuçlu bir tahtanın milyonlarca çözümü olabilir). Doğrusu: saymaya devam et, ikinciyi bulduğun an dur. İpucu sayısı tekliği garanti etmez: 17 alt sınırdır, yeter koşul değil.
🎬 Ara: Python ile sudoku çözücü
Python Sudoku Solver
Computerphile (Thorsten Altenkirch) · 10 dk 52 sn · YouTube’da aç
Bu bölümdeki geri izlemenin on satırlık Python hâli, canlı yazılarak. Video “ilk boş hücre” sırasını kullanıyor; bizim “en az adaylı hücre” iyileştirmesiyle karşılaştırmak iyi bir alıştırma.
🤔 İzlerkenVideodaki çözücü bir rakamı nasıl geri alıyor? Neden bütün çözümleri buluyor, ilkinde durmuyor? En az adaylı hücre seçimi bu koda nasıl eklenirdi?
LEVEL 3
Durum uzayında arama
Sokoban: geri al tuşu ve çözücü
Problem: bu seviye çözülebilir mi?
🎮 Hamleli bulmacalar
- Sokoban (Hiroyuki Imabayashi, 1982): depo görevlisi kutuları hedeflere iter. İtebilir, çekemez. Kutuyu köşeye iterseniz seviye biter: çözüm kalmaz, ama oyun bunu söylemez.
- Soyundan gelenler: Baba Is You, Stephen’s Sausage Roll, A Monster’s Expedition, Zelda’daki blok odaları, Pokémon’daki kaya bulmacaları.
- Fark: burada doldurulacak bir tablo yok; bir durum ve onu değiştiren hamleler var. Çözüm bir hamle dizisi.
- Tasarımcının soruları: bu seviye çözülebilir mi? En kısa çözüm kaç hamle? Oyuncu geri dönüşü olmayan bir hata yapabilir mi? İpucu olarak ne göstereyim?
Geri izleme burada neden yetmez?
- Vezirlerde derinlik belliydi: 8 satır, bitti. Burada hamle dizisi istediği kadar uzayabilir.
- Aynı duruma farklı yollardan gelinir: sağa-sola yürümek durumu değiştirmez. Saf geri izleme sonsuz döngüye girer ya da aynı durumu milyonlarca kez yeniden araştırır.
- İlaç: gördüğün durumları hatırla (bir kümede; Hash Tabloları). Aynı duruma ikinci kez geldiysen o dalı kes.
Bu, graflardaki aramanın ta kendisi (Yönsüz Graflar): düğüm = durum, kenar = hamle. Fark: grafı kimse çizmedi; hamleleri uyguladıkça ortaya çıkıyor.
Derinlik öncelikli gidersek (DFS) bu, “ziyaret edilenler” kümesi eklenmiş geri izlemedir. Genişlik öncelikli gidersek (BFS) en kısa çözümü buluruz; bedeli bellek.
Fikir: durum = bir fotoğraf; iki kullanım
① Oyuncu için: geri al tuşu
- Her hamleden önce durumun kopyasını bir yığına koy.
- Z: yığının tepesini al, durumu ona eşitle.
- Oyuncu artık korkmadan dener: yanlış itiş bir tuşla geri alınır. Elle yapılan geri izleme.
- Modern bulmaca oyunlarının neredeyse hepsinde sınırsız geri alma vardır; “kilitlenip seviyeyi baştan başlatma” cezası tasarımdan kalkmıştır.
Durum küçükse (birkaç yüz bayt) kopyalamak en sağlam yoldur. 1.000 hamlelik geçmiş bile kilobaytlar tutar.
② Makine için: çözücü
- Başlangıç durumunu bir kuyruğa koy; “görülenler” kümesine ekle.
- Kuyruktan bir durum al. Çözüm mü? Bitti.
- Değilse dört hamleyi uygula; her yeni durum için: daha önce görülmediyse kümeye ve kuyruğa ekle (nereden, hangi hamleyle gelindiğini de yaz).
- Çıkmaz budaması: hedef olmayan bir köşeye itilen kutu oradan asla çıkamaz. O durumu kuyruğa hiç koyma.
- Kuyruk boşaldıysa: çözüm yok.
| demodaki “orta” seviye | |
|---|---|
| boş kare / kutu | 30 / 3 |
| olası yerleşim (üst sınır) | 30 × C(29, 3) = 109.620 |
| başlangıçtan ulaşılabilen (budamasız / budamalı) | 24.813 / 11.226 |
| en kısa çözüm | 25 hamle |
Canlı: Sokoban — oynayın, geri alın, çözdürün 📦
- Ekranı okuyun: mavi daire sizsiniz; sarı kutular; yeşil halkalar hedefler (hedefteki kutu yeşile döner). Sağda hamle sayısı, geri alma yığınının boyu ve çözücünün raporu.
- W / A / S / D ile oynayın. Bir kutuyu bilerek köşeye itin: “⚠️ bir kutu köşeye sıkıştı: çözüm yok” uyarısı çıkar. Z ile geri alın. (Uyarı olmasaydı ne kadar sonra fark ederdiniz?)
- Birkaç hamle yapıp “🤖 çöz”e basın: “buradan en kısa çözüm N hamle”, “taranan durum: …”. “💡 ipucu” yalnızca ilk hamleyi kırmızı okla gösterir; “▶ çözümü oynat” hepsini.
- “Köşe budaması”nı kapatıp yeniden çözdürün: aynı çözüm, iki katından fazla durum (başlangıçta 11.226 yerine 24.813).
- Kutuyu köşeye itip “çöz”e basın: “bu durumdan çözüm YOK”. Çözücü bunu, ulaşılabilen bütün durumları tüketerek söyler. Bir seviye editöründe bu denetim, kilitlenen seviyelerin yayımlanmasını önler.
- “Zor” seviyeyi kendiniz çözmeyi deneyin (27 hamle). Kaç kez Z’ye bastınız?
🔎 DEMODA DENEYİN
- Ekranı okuyun: mavi daire sizsiniz; sarı kutular; yeşil halkalar hedefler (hedefteki kutu yeşile döner). Sağda hamle sayısı, geri alma yığınının boyu ve çözücünün raporu.
- W / A / S / D ile oynayın. Bir kutuyu bilerek köşeye itin: “⚠️ bir kutu köşeye sıkıştı: çözüm yok” uyarısı çıkar. Z ile geri alın. (Uyarı olmasaydı ne kadar sonra fark ederdiniz?)
- Birkaç hamle yapıp “🤖 çöz”e basın: “buradan en kısa çözüm N hamle”, “taranan durum: …”. “💡 ipucu” yalnızca ilk hamleyi kırmızı okla gösterir; “▶ çözümü oynat” hepsini.
- “Köşe budaması”nı kapatıp yeniden çözdürün: aynı çözüm, iki katından fazla durum (başlangıçta 11.226 yerine 24.813).
- Kutuyu köşeye itip “çöz”e basın: “bu durumdan çözüm YOK”. Çözücü bunu, ulaşılabilen bütün durumları tüketerek söyler. Bir seviye editöründe bu denetim, kilitlenen seviyelerin yayımlanmasını önler.
- “Zor” seviyeyi kendiniz çözmeyi deneyin (27 hamle). Kaç kez Z’ye bastınız?
Kod: hamle, geri al, çözücü (1/2)
Kod: hamle, geri al, çözücü (2/2)
🎒 Kodu okuyalım
| ifade | ne demek | neden böyle |
|---|---|---|
{ oyuncu, kutular } | durumun tamamı | Duvarlar ve hedefler değişmez: duruma girmez. Durum ne kadar küçükse arama o kadar hızlı. |
kutular.sort(…) | kutuları sıralı tut | Kutular birbirinin aynısı: [5, 9] ile [9, 5] aynı durum. Sıralamazsanız küme ikisini farklı sanar ve arama katlanır. |
hamleYap yeni nesne döndürür | eski durum değişmez | Geri al yığını ve çözücü eski durumlara güvenir. Durumu yerinde değiştirirseniz geçmiş de bozulur. |
gecmis.push(durum) | hamleden önce sakla | Geri al = pop. Yığın (Yığınlar ve Kuyruklar). |
anahtar(d) | durumu metne çevir | Kümeye koymak için (Hash Tabloları). "12|9,17,24" gibi. |
gorulen.has(a) → continue | bu duruma daha önce geldik | Döngüleri ve tekrarları kesen satır. Onsuz arama bitmez. |
koseMi(…) → continue | çıkmaz budaması | İki komşu duvar (biri yatay, biri dikey) ve hedef değil: kutu oradan çıkamaz. |
ÖnermeGenişlik öncelikli arama, çözüm varsa en az hamleli olanı bulur; süre ve bellek, ulaşılabilen durum sayısıyla orantılıdır. Bu sayı kutu sayısıyla üstel büyür: Sokoban’ın genel hâli PSPACE-tamdır. Küçük seviyeler (3–5 kutu) anında çözülür; gerçek seviyeler (10+ kutu) özel çıkmaz kalıpları ve sezgisel arama ister (A*: Y8).
Oyunlarda: PuzzleScript’in geri al tuşu
Kaynak: PuzzleScript, engine.js. Tarayıcıda çalışan açık kaynak bulmaca oyunu motoru; binlerce oyun yapıldı. Stephen’s Sausage Roll ve Baba Is You gibi oyunların ilk prototipleri bu tür araçlarda doğdu.
🎮 Satır satır
backups.push(state): az önce yazdığımızgecmis.push(durum).DoUndo: yığının tepesini geri yükle, yığından çıkar. SlayttakigeriAl.noundo: oyun yazarı isterse geri almayı kapatabilir. Bu bir tasarım kararıdır; motor varsayılan olarak açık tutar.- Motorda Z geri al, R baştan başlat: bugün bulmaca oyunlarının standart tuşları.
Geri almanın tasarıma etkisi
- Braid (2008): zamanı geri sarmak oyunun ana mekaniği; ölmek diye bir şey yok.
- Baba Is You, Stephen’s Sausage Roll: sınırsız geri alma sayesinde seviyeler acımasızca zor olabilir.
- Çözücü kullanan araçlar: seviye editörleri “çözülebilir mi / en kısa çözüm” gösterir; rastgele eşya dağıtan “randomizer”lar (Zelda, Metroid) her tohumu “oyun bitirilebilir mi?” diye sınar; günlük bulmaca oyunları çözücünün bulduğu en kısa çözümü “hedef hamle sayısı” yapar.
LEVEL 4
En değerli yük
taşıma kapasitesi ve dal-sınır
Çizimle: al ya da alma ağacı (kapasite 10 kg)
Her eşya için iki dal: al ya da alma. Heykeli alan dal (açgözlünün seçimi) 6 kg’da kalır; kupa ya da tabak eklenince 11 kg olur, dal kesilir: 30 altın. Heykeli almayan dalda kupa + tabak tam 10 kg ve 40 altın. Dal-sınır yöntemi, “bu daldan en iyi ihtimalle ne çıkar?” tahmini bulunan en iyiyi (40) geçemeyen dalları hiç açmaz.
Problem ve fikir: al ya da alma
🎮 “Çok fazla taşıyorsunuz”
- Skyrim, Fallout, The Witcher, Baldur’s Gate: çantanın ağırlık sınırı var; her eşyanın ağırlığı ve değeri.
- Zindanın sonunda yerde 15 eşya; hepsini taşıyamazsınız. Hangilerini almalı ki satınca en çok altın etsin?
- YZ tarafı: bir NPC tüccar kervanını yüklüyor; bir strateji YZ’si sınırlı bütçeyle hangi birimleri üreteceğini seçiyor; bir “yapı” (build) puan bütçesiyle hangi yetenekleri alacağını.
- Adı: sırt çantası problemi (0/1 knapsack).
Açgözlü çözüm: “kilo başına en değerli”den başla. Hızlı ve çoğu zaman iyi; ama en iyiyi garanti etmez.
Elle hesap: kapasite 10 kg
| eşya | ağırlık | değer | değer / kg |
|---|---|---|---|
| altın heykel | 6 | 30 | 5 |
| gümüş kupa | 5 | 20 | 4 |
| gümüş tabak | 5 | 20 | 4 |
- Açgözlü: heykel (6 kg, 30). Kalan 4 kg: başka hiçbir şey sığmaz. Toplam 30.
- En iyisi: kupa + tabak (10 kg). Toplam 40.
Geri izleme: her eşya için iki dal: al (sığıyorsa) / alma. n eşya → 2ⁿ yaprak.
- 3 eşya: 8 seçim. 20 eşya: 1.048.576. 40 eşya: bir trilyon.
- Budama 1: kapasiteyi aşan dalı kes.
- Budama 2 (sınır): “şu ana kadarki değer + geri kalan her şeyin değeri” bile eldeki en iyi çözümü geçemiyorsa bu dalı kes. İyimser tahmin bile yetmiyorsa uğraşma.
İkinci budamaya dal-sınır (branch and bound) denir: en iyi çözümü arayan her geri izlemede kullanılır.
Kod: en değerli yük
JavaScript ve C# sürümleri aynı yapıdadır. Ağırlıklar küçük tam sayılarsa aynı problem bir tabloyla (dinamik programlama) n × kapasite adımda çözülür; Kaynaklar’daki videoya bakın.
🎒 Kodu okuyalım
dene(i, agirlik, deger, kalan_deger): i. eşyadayız; çantada şu kadar ağırlık ve değer var; henüz karar verilmemiş eşyaların toplam değerikalan_deger.en_iyi = max(…): burada “çözüm bulunca dur” yok; her geçerli seçim bir adaydır ve en iyisi saklanır. Karar probleminden en iyileme problemine geçtik.deger + kalan_deger <= en_iyi → return: sınır. Ne kadar erken iyi bir çözüm bulunursa o kadar çok dal kesilir; bu yüzden önce “al” dalı denenir ve eşyalar değer/ağırlık oranına göre sıralanırsa daha da hızlanır.- Geri alma nerede? Parametreler kopyalanarak geçiyor: üst çağrının
agirlikvedegerdeğişkenleri hiç değişmedi. Durum küçük sayılarsa en temiz yol budur. - Oyunda: “en iyi ganimeti al” tuşu; tüccarın stok seçimi; YZ’nin bütçeyle ordu kurması; hız koşularında (speedrun) eşya rotası.
Önerme: dal-sınır en iyi çözümü kesin bulur (yalnızca en iyiyi içeremeyecek dalları keser); en kötü durumda yine 2ⁿ’dir.
🐍 Laboratuvar: en değerli ganimet
En kısa doğru çözüm:
def dene(i, kalan): · if i == len(esyalar): return 0 · almadan = dene(i + 1, kalan) · a, d = esyalar[i] · if a > kalan: return almadan · return max(almadan, d + dene(i + 1, kalan - a)); sonra return dene(0, kapasite). Slayttaki örnek: [[6, 30], [5, 20], [5, 20]], kapasite 10 → 40; kapasite 9 → 30.LEVEL 5
Hepsi bir arada
tam kod, araçlar, kapanış
Geri izleme ailesi: hangi soru, hangi sürüm?
| soru | sürüm | durduğu yer | bu sunumdaki örnek | hız için |
|---|---|---|---|---|
| Bir çözüm var mı? | geri izleme (DFS) | ilk çözüm | vezirler, çanta, sudoku | budama + zor seçimi önce yap |
| Kaç çözüm var? Tek mi? | geri izleme, durmadan | hepsi (ya da ikincisi) | vezir sayma, sudoku tekliği | “yeterince bulunca dur” |
| En iyi çözüm hangisi? | dal-sınır | ağaç tükenince | en değerli yük | iyimser sınır + iyi çözümü erken bul |
| En kısa hamle dizisi? | durum uzayında BFS (+ görülenler kümesi) | ilk çözüm = en kısa | Sokoban | çıkmaz budaması; A* (Y8) |
| Oyuncu hata yaparsa? | durum yığını | — | geri al tuşu (Z) | durumu küçük tut |
Hepsinin altında aynı üç soru var: durum nedir? Bir adımda hangi seçenekler var? Bir seçeneğin işe yaramayacağını en erken ne zaman anlayabilirim?
Ne zaman geri izleme kullanmamalı?
Her karede çalışacak işlerde (yol bulma, çarpışma) ve durum uzayı sınırsız büyüyen yerlerde. Geri izleme “oyuncu bir tuşa bastı, yarım saniyem var” ya da “seviyeyi yüklerken / üretirken” işleri içindir. Her zaman bir deneme sınırı koyun.
Akrabaları
Oyun ağaçları (Y12: minimax, rakip de seçim yapar) · GOAP (Y6: eylem planı arama) · dalga fonksiyonu çöküşü (Y15: kısıt yayma + geri izleme) · A* (Y8: sezgiyle yönlendirilen durum araması).
📦 Tam kod: p5.js ile çanta düzenleyici
Çekirdek. Eksiksiz dosyada fareyle al / bırak, gölge önizleme ve çizim de var.
🎮 Çalıştırın, kopyalayın, bozun
▶ Eksiksiz örneği aç — yaklaşık 90 satır: eşyaya tıklayıp alın, çantaya bırakın; R döndür, O otomatik yerleştir, N yeni ganimet.
Deneyin:
- Sıralamayı küçükten büyüğe çevirin; deneme sayısını karşılaştırın.
- L ve T biçimli eşyalar ekleyin (kare listesiyle).
- Yerleştirmeyi animasyonlu yapın: her karede bir adım (özyineleme yerine kendi yığınınızla).
- Eşyalara değer verin; sığmıyorsa “en değerli sığan alt küme”yi bulun (iki problemin birleşimi).
- Z ile geri al ekleyin: her al / bırak işleminden önce durumu yığına koyun.
🧰 Araçlar ve kütüphaneler
| Bulmaca motorları | PuzzleScript · Puzzlescript Next · Bitsy | Tarayıcıda, kural yazarak ızgara bulmacası; geri al / baştan başlat hazır. Prototip için ideal. |
| Hazır çözücüler | Simon Tatham’s Puzzles (C, kaynak açık) · sokoban solver’lar (YASS, Sokolution) | Üretici + çözücü + zorluk derecelendirme örnekleri; okunacak en iyi kod. |
| Kısıt çözücüler | Google OR-Tools (CP-SAT) · python-constraint · MiniZinc · Z3 | Kuralları yazarsınız, aramayı o yapar. Seviye üretimi ve denetimi için çevrimdışı araç olarak. |
| Tam örtme | Knuth’un Algorithm X / Dancing Links’i (her dilde kütüphanesi var) | Pentomino, sudoku, çanta doldurma gibi “her kareyi bir kez ört” problemleri. |
| Unity / Godot | ızgara envanter paketleri · Stack<T> ile geri al · Coroutine / thread ile uzun arama | Aramayı ana iş parçacığında sınırsız çalıştırmayın: ya sınır koyun ya kareler arasına yayın. |
| Seviye tasarımı | çözücüyü editöre bağlayın | “çözülebilir ✔ · en kısa 25 hamle · 3 çıkmaz noktası” satırı tasarımcıya saatler kazandırır. |
Pratik kural: oyunun içinde (çalışma anında) küçük ve sınırlı aramalar; büyük aramalar üretim / tasarım zamanında, sonuçları seviyeyle birlikte saklanarak.
🤖 Bu konuyu bir YZ kod asistanıyla yazarken
Sık yapılan hatalar — kontrol edin
- Geri almanın unutulması (ya da seçimin tam tersi olmaması)
- Taban durumun eksik / yanlış yerde olması
- Durumu kopyalamadan paylaşmak: yığındaki “eski” durumlar da değişir
- Görülen durumlar kümesi olmadan hamle araması: sonsuz döngü
- Özdeş nesneleri (kutular) sıralamadan anahtar üretmek: aynı durum defalarca
- Deneme sınırı / zaman sınırı olmayan arama: oyunun donması
- “Sığmıyor” demek için alan denetimini yeterli sanmak
- En iyileme probleminde ilk çözümde durmak
İyi bir istek (prompt) örneği
“p5.js, kütüphane yok. 8 × 5 ızgara envanter: (1) sigarMi(izgara, w, h, x, y). (2) otomatikYerlestir(esyalar): önce toplam alan denetimi; eşyaları alana göre büyükten küçüğe sırala; özyinelemeli geri izleme (seç / dene / geri al), 90° döndürme serbest; 200.000 denemede vazgeç ve bunu bildir. (3) Sayaçlar: yerleştirme denemesi ve geri alma sayısı ekrana yazılsın. (4) Hata ayıklama: bir tuşla aramayı adım adım oynat. (5) Test: verdiğim on eşya büyükten küçüğe 10 denemede, küçükten büyüğe 2.248 denemede sığmalı; döndürme kapalıyken ‘sığmaz’ demeli.”
- Yöntemin adını ve seçim sırasını söyleyin; asistan çoğu zaman en saf sırayı yazar.
- Sayaç isteyin: budamanın çalışıp çalışmadığını ancak sayarak görürsünüz.
- Bilinen cevaplı test verin (8 vezir → 92).
💬 Tartışma soruları
Yanınızdakiyle 2 dakika konuşun, sonra sınıfça tartışalım
- Çanta düzenlemek bazı oyunlarda zevk (Resident Evil 4, Backpack Hero), bazılarında angarya (ağırlık sınırı yüzünden sürekli eşya atmak). Farkı ne yaratıyor? “Otomatik düzenle” tuşu hangisinde olmalı?
- Sınırsız geri alma bulmaca oyunlarını nasıl değiştirdi? Geri alması olmayan bir bulmaca oyunu (eski Sokoban, satranç problemleri) size ne hissettirir? Hangi durumda geri almayı bilerek kapatırdınız?
- İyi bir bulmaca “mantıkla çözülebilir” olmalı, “deneme-yanılmayla” değil; deniyor. Katılıyor musunuz? Geri izleme gerektiren bir bulmaca kötü tasarım mıdır?
- Bilgisayar bir Sokoban seviyesini saniyede çözüyor; insan yarım saatte. Çözücünün “taranan durum sayısı” seviyenin insan için zorluğunu ölçer mi? Başka ne ölçülebilir?
- Rastgele eşya dağıtan bir Zelda “randomizer”ında anahtar, ancak o anahtarla açılan kapının arkasına düşerse oyun bitirilemez. Üretici bunu nasıl önler? (İpucu: Y15’teki “üret ve sına”.)
🚀 Proje ve araştırma önerileri
- [kolay] Vezir bulmacası — N vezir oyununu oynanır yapın: tıklayarak vezir koy / kaldır, tehdit edilen kareleri boya, “ipucu” tuşu çözücüden bir sonraki güvenli kareyi göstersin.
- [kolay] Geri alınabilir Sokoban — Örnek seviyelerle p5.js Sokoban: Z geri al, R baştan (o da geri alınabilir), hamle sayacı. Kendi seviyenizi metinle tanımlayın.
- [orta] Sudoku üreticisi — Dolu tahta üret, tek çözümlülüğü koruyarak ipucu sil. Zorluk: çözücünün geri alma sayısı. Kolay / orta / zor düğmeleri.
- [orta] Çanta oyunu — Backpack Hero benzeri: her savaştan sonra üç eşyadan biri; L / T biçimli eşyalar; yan yana gelen eşyalar birbirini güçlendirsin. “Otomatik düzenle” en yüksek güç puanını arasın (dal-sınır).
- [zor] Seviye denetçisi — Sokoban seviye editörü: çizdikçe çözücü çalışsın; “çözülebilir, en kısa N hamle, şu kareler çıkmaz” göstersin. 4 × 4’lük rastgele seviyeler üretip en uzun çözümlü olanı bulun.
- [araştırma] Kilit–anahtar zindanı — Rastgele zindan üreticisine anahtar ve kilitli kapılar ekleyin (Y15). Her üretimi “erişilebilirlik” aramasıyla sınayın: anahtarlar toplandıkça açılan bölgeler. Kilitlenme olasılığını ölçün; üreticiyi kilitlenmeyecek biçimde düzeltin.
Neler öğrendik? 🎒
- Geri izleme: seç → dene → geri al; taban durum; budama. Dört satırlık iskelet her bulmacaya uyar.
- Budama ve sıra: algoritma aynı kalır, iş binlerce kat değişir. “Başarısız olacaksan erken ol”: en zor eşya önce (çanta: 2.248 → 10), en az adaylı hücre önce (sudoku: 4.208 → 51).
- Çanta: “buraya sığar mı” + geri izleme = otomatik düzenleme. Alan denetimi bedava budama; deneme sınırı şart.
- Kısıt bulmacaları: çözücü aynı zamanda denetçi (“tek çözümlü mü?”) ve üreticinin motorudur. (Simon Tatham.)
- Durum uzayı: hamleli bulmacalarda görülen durumları hatırla; BFS en kısa çözümü verir; çıkmazları erken kes. Oyuncunun geri al tuşu aynı durum yığınıdır. (PuzzleScript.)
- En iyileme: al / alma ağacı + iyimser sınır (dal-sınır). Açgözlü seçim hızlıdır ama en iyiyi garanti etmez.
- Sonraki: kamera algoritmaları: oyuncu neyi görmeli? Takip kuralları, sarsıntı, çok hedef, 3B kamera kolu.
🎮 Bu sunumdaki oyunlar
Adı geçen oyunu tanımıyorsanız: oyuncuların kullandığı wiki sayfası ve oyunu kısaca gösteren bir video. ▶ video slaydın üstünde açılır (Esc ile kapanır); 🎯 işaretli bağlantılar doğrudan bu sunumdaki konuya gider.
Resident Evil 4 2005 · korku / aksiyon
Omuz üstü kamerayı popülerleştiren korku-aksiyon oyunu.
Diablo 1996 · aksiyon RPG
Rastgele üretilen zindanlarda canavar ve ganimet; ızgaralı envanteriyle de meşhur.
Tetris 1984 · bulmaca
Düşen dörtlü blokları satır tamamlayacak biçimde yerleştirirsiniz; modern sürümler “7-torba” ile karıştırır.
The Legend of Zelda 1986– · aksiyon-macera
Nintendo’nun zindan ve bulmaca serisi; anahtar–kapı düzenleri seviye tasarımının klasiği.
Braid 2008 · bulmaca platform
Zamanı geri sarmanın ana mekanik olduğu bulmaca-platform oyunu.
The Elder Scrolls V: Skyrim 2011 · açık dünya RPG
Dev açık dünyalı fantastik rol yapma oyunu; ağırlık sınırlı envanter ve sayısız mod.
Kaynaklar: videolar 🎬
Kaynaklar: kaynak kodu, yazılar ve oynanabilir sayfalar 📚
- Simon Tatham: Portable Puzzle Collection — 40’tan fazla bulmaca, tarayıcıda oynanır; üretici ve çözücülerin kaynak kodu (
solo.csudoku) - Stephen Lavelle: PuzzleScript · engine.js (geri al yığını)
- Peter Norvig: Solving Every Sudoku Puzzle — kısıt yayma + en az adaylı hücre; kısa ve çok öğretici
- Donald Knuth: Dancing Links (2000) — tam örtme, pentomino ve vezirler için geri izleme
- Sokoban Wiki: Deadlocks ve Solver — çıkmaz kalıpları ve çözücü teknikleri
- Red Blob Games: Introduction to A* — durum uzayı aramasını sezgiyle hızlandırmak (Y8)
- McGuire, Tugemann & Civario (2012), “There is no 16-Clue Sudoku” · Culberson (1997), “Sokoban is PSPACE-complete”
NEXT LEVEL ▶
Kamera Algoritmaları
takip kuralları, ekran sarsıntısı, kadraja sığdırma, kamera kolu
SONRAKİ SUNUM ▶