Çözücü nasıl kullanılır
Yukarıdaki araç, çözülebilir herhangi bir 3×3, 4×4 veya 5×5 tahtayı optimal çözer — verdiği cevap yalnızca işe yarayan değil, mümkün olan en kısa hamle dizisidir.
- Düzenle'ye bas ve tahtanı gir: taşları bitmiş bulmacada okunacakları gibi numaralandır (sol üst 1'dir) ve şu an bulundukları yerlere yerleştir. Resimli bir bulmaca mı çözüyorsun — bir oyundan, bir fotoğraf uygulamasından, ahşap bir oyuncaktan? Önce bitmiş resmi zihninde sol üstten sağ alta doğru numaralandır.
- Çöz'e bas. Hamle listesi 3×3 tahtalarda anında, 4×4'te birkaç saniye içinde belirir.
- Hamleleri gerçek bulmacanda teker teker uygula.
Çözücü tahtanın çözülemez olduğunu söylüyorsa bu bir hata değil — tüm dizilimlerin tam yarısı asla çözülemez ve hiçbir geçerli hamle dizisi bunu düzeltemez. Hamleleri okumak yerine tekniği öğrenmeyi mi tercih edersin? İnsan yöntemi burada.
Bir kayan bulmaca çözücü nasıl çalışır — altı algoritmanın karşılaştırması
Kendi kayan bulmaca çözücünü yazıyorsan ve hangi algoritmayı kullanacağından emin değilsen, makalenin geri kalanı iyi bilinen altı algoritmayı hız, bellek, kod karmaşıklığı ve rahatça başa çıktıkları tahta boyutu açısından karşılaştırıyor. Cevaplar 3×3, 4×4 ve 5×5 için farklıdır.
1. Genişlik öncelikli arama (BFS)
En aptal ama doğru algoritma. Hedefi bulana kadar durumları seviye seviye keşfet.
- Zaman — çözüm derinliğinde üstel. 8'li bulmacada saniyenin küçük bir kesrinde biter. 15'li bulmacada, bilgisayarının RAM'i bitmeden bitmez.
- Bellek — ziyaret edilen kümenin tamamını bellekte tutar. Zor 15'li bulmacalarda on milyonlarca durum.
- Kod karmaşıklığı — yirmi satır.
- Sonuç — 3×3 için yeterli, ötesinde işe yaramaz.
2. Manhattan mesafeli A*
İlk gerçek algoritma. Yapı BFS ile aynı, ama durumlar f = g + h ile sıralanan bir öncelik kuyruğundan çekilir; buradaki h, Manhattan mesafesi sezgiselidir.
- Zaman — 8'li bulmacada milisaniyeler, 15'li bulmacada saniyelerden dakikalara.
- Bellek — keşfedilen her şeyi hâlâ bellekte tutar; 8 için idare edilir, 15 için sancılı.
- Kod karmaşıklığı — elli satır, çoğu öncelik kuyruğu tesisatı.
- Sonuç — 8'li bulmaca için doğru araç. 15 için sınırda.
3. Manhattan + doğrusal çakışmalı A*
Aynı satırda olup ikisi de hedef satırında ama yanlış sırada duran her taş çifti için sezgisele 2 hamle ekle (sütunlar için de aynısı). Birbirlerinin yanından geçmeleri gerekecek — Manhattan mesafesinin göremediği şey bu.
- Zaman — düz Manhattan A*'dan tipik olarak %5–15 daha hızlı.
- Bellek — değişmez.
- Kod karmaşıklığı — altmış satır.
- Sonuç — düz Manhattan A*'dan kesinlikle daha iyi. Her zaman bunu kullan.
4. Manhattan + doğrusal çakışmalı IDA*
Yinelemeli derinleştirmeli A*. f-maliyetini derinlik ölçüsü olarak kullanarak derinlik sınırlı DFS yap, her yinelemede sınırı yükselt. Yeniden keşfetme pahasına belleği zamana takas eder.
- Zaman — tekrarlı keşif yüzünden düğüm başına A*'dan biraz yavaş, ama düşük bellek baskısı zor 15'li bulmacalarda genellikle kazanır.
- Bellek — O(derinlik), O(keşfedilen durum) değil. Kazanç burada.
- Kod karmaşıklığı — seksen satır (özyinelemeli DFS, eşik yönetimi).
- Sonuç — 4×4 için doğru araç. Korf 1985'ten beri standart.
5. Walking distance'lı IDA*
Walking distance daha sıkı bir sezgiseldir. Her taş dizilimi için, yalnızca satırlara izdüşümü alınmış halde, her taşı doğru satırına götürecek minimum satır-değişimi sayısını önceden hesapla. Sütunlar için de aynısını yap. Topla.
Manhattan'ın kaçırdığı bir şeyi yakalar: aynı satırdaki taşların aynı yer için "kavga etmesini".
- Zaman — zor 15'li bulmacalarda Manhattan + doğrusal çakışmadan tipik olarak 2 kat hızlı, çünkü sezgisel daha sıkı olduğundan IDA* daha çok budar.
- Bellek — küçük bir önhesap tablosu ekler (4×4 için ~500 KB).
- Kod karmaşıklığı — 150 satır. Önhesap, indirgenmiş bir durum uzayında BFS'tir.
- Sonuç — mühendislik bütçen varsa 4×4 için doğru araç. İlk kayda değer iyileştirme.
6. Toplanabilir ayrık örüntü veritabanlı IDA*
Kayan bulmacalar için bilinen en güçlü sezgisel. Taşları ayrık gruplara böl (15'li bulmacada yaygın bölümleme 7+8 veya 5+5+5'tir). Her grup için, o grubun olası tüm dizilimleri üzerinde, grubun taşlarını hedef konumlarına götürmenin maliyetini önceden hesapla. Arama sırasında her grubun katkısını tablodan oku ve topla.
- Zaman — en zor 15'li bulmacayı milisaniyelerde çözer. Rastgele 24'lü bulmacaları saniyelerde çözer.
- Bellek — ciddi. 15'li bulmaca için 7+8 bölümlemesi yaklaşık 1 GB. 24'lü bulmaca için 5+5+5+9 bölümlemesi yaklaşık 4 GB. Mühendisliğin belkemiği bellek.
- Kod karmaşıklığı — 300+ satır. Önhesap adımı grup durum uzayında geriye dönük BFS kullanır ve işin büyük kısmı budur.
- Sonuç — 5×5 ve 6×6 için doğru araç. 3×3 için aşırıya kaçmak.
Özet öneriler
Bugün bir çözücü yazıyorsan:
- 3×3 için Manhattan + doğrusal çakışmalı A* kullan. Gerisi aşırı mühendislik.
- 4×4 için walking distance'lı IDA* kullan. Örüntü veritabanları bu boyutta marjinal kazanç sağlar; mühendislik karmaşıklığına değmez.
- 5×5 için toplanabilir örüntü veritabanlı IDA* kullan (standart 5+5+5+9). Örüntü veritabanı olmadan en zor örneklerde zaman aşımına uğrarsın.
- 6×6 için (35'li bulmaca) aynı algoritmalar rastgele örnekleri çözebilir, ama en zor durumlar hâlâ araştırma konusu. Çoğu uygulama denemez bile.
Peki ya makine öğrenmesi?
2026'da makul bir soru. Sinir ağı sezgiselleri en az 2014'ten beri çalışılıyor ve kayan bulmacalar için hızlı sezgiseller üretebiliyor. Sorun şu: bunlar tipik olarak kabul edilebilir (admissible) değildir — maliyeti fazla tahmin edebilirler, bu da ortaya çıkan algoritmanın artık optimal sonucu garanti etmediği anlamına gelir. Zorluk kalibrasyonu için garantili-optimal çözümler isteyen uygulama geliştiricileri açısından klasik örüntü veritabanları doğru araç olmaya devam ediyor.
Araştırma merakı için: sinir ağıyla eğitilmiş örüntü veritabanları, en zor 15'li bulmaca örneklerinde küçük hızlanmalar sağlıyor. Akademik makaleler için faydalı, yayınlanan yazılım için marjinal.
Gerçek bir uygulamaya ne girer
İpucu üretimi için çözücüye ihtiyaç duyan, yayınlanmış bir mobil uygulama neredeyse her zaman şuraya varır:
- 4×4 için IDA* + walking distance.
- 5×5 için IDA* + küçük bir örüntü veritabanı.
- İpucu düğmesinden yalnızca-sonraki-hamle çağrısı.
- Her şey cihazda çalışır. Çözücünün tamamı birkaç yüz kilobayt kod artı birkaç megabayt önhesaplanmış tablodur.
Sakin bir telefon uygulaması için doğru pragmatik yığın bu. Slide Puzzle'ın ipucu düğmesi tam olarak böyle çalışıyor.