Bir 15 bulmacayı çözmenin iki yolu vardır. Biri, her oyuncunun eninde sonunda kendi kendine bulduğu yol — üst satırı çöz, sonra sol sütunu, sonra içe doğru tekrarla. Diğeri, bilgisayarların yolu: kalan hamle sayısına dair akıllıca bir alt sınır tahminiyle yönlendirilen, milyonlarca durumu tarayan bir sezgisel arama.
Bu rehber ikisini de kapsıyor — kabaca insanların öğrenme sırasıyla.
15 bulmaca, tek paragrafta
4×4 bir tahta, on beş numaralı taş, bir boş kare. Taşları boşluğa kaydırarak sayıları sıraya dizersiniz — 1'den 15'e, boşluk sağ alt köşede. Tahta 1874'te Noyes Chapman tarafından icat edildi ve Sam Loyd'un çözülemez bir dizilim için 1000 dolar ödül vaat etmesinin ardından 1880'lerde uluslararası bir çılgınlığa dönüştü. Özünde 8 bulmacayla aynı oyundur — sadece bir satır ve bir sütun daha büyük.
Elle çözüm: satır-sütun yöntemi
Her insanın eninde sonunda bulduğu teknik şudur:
- 1. satırı çözün. 1 ve 2'yi yerleştirin. Sonra 3'ü sağ üst köşeye koyun. Köşeleri mümkün kılan numara, "L" şeklindeki manevradır — 4'ü 3'ün konumuna getirin, 3'ü altına kaydırın, sonra ikiliyi köşeye döndürün.
- 1. sütunu çözün. Aynı L şeklindeki köşe hilesiyle 5'i, sonra 9'u, sonra 13'ü sol alt köşeye yerleştirin.
- İçe doğru tekrarlayın. Geriye kalan 3×3'lük bir alt bulmacadır — yani zaten çözmeyi bildiğiniz bir 8 bulmaca.
Deneyimli bir oyuncu 15 bulmacayı elle 3–5 dakikada çözer. Yeni bir oyuncu ilk seferinde 20 dakika harcayabilir; üçüncü denemede bunun üçte birine iner.
Aynı yöntem 5×5 ve 6×6'ya da ölçeklenir. Tekrarlama her zaman 3×3'lük bir oyun sonuna varır.
Optimal çözücü: Manhattan mesafeli A*
Bilgisayar, satır-sütun yönteminden çok daha iyisini yapabilir. Somut olarak: en kısa çözümü bulabilir — ki bir insanın oynadığı çözüm nadiren en kısasıdır.
Matematiksel gerçek: ortanca 15 bulmaca, optimal çözüldüğünde yaklaşık 52 tek taşlık hamle ister. En kötü durum 80'dir. Satır-sütun yöntemi aynı tahtada tipik olarak 100–150 hamle kullanır.
Optimal çözümü bulmak için A* araması her tahta durumunu bir düğüm, her hamleyi bir kenar olarak ele alır ve sorar: hedefe en az kaç hamle var? Kalan minimum hamle sayısını bulmacayı çözmeden tam hesaplamak imkânsızdır, ama iyi bir alt sınır A*'ı hızlandırır.
Klasik alt sınır Manhattan mesafesidir:
Her taş için, şu anki konumundan hedef konumuna olan satır mesafesi ile sütun mesafesini toplayın. (Boşluğu yok sayın.)
Manhattan mesafesi kabul edilebilirdir (admissible) — gerçek mesafeyi asla abartmaz, çünkü her taş en az o kadar yol katetmek zorundadır. A* ve Manhattan mesafesiyle 8 bulmaca mikrosaniyelerde, 15 bulmaca saniyelerde çözülür.
IDA*: bellek dostu kuzen
A*, keşfettiği her durumu hatırlamak zorundadır. 15 bulmacada bu, en zor tahtalar için yüzlerce megabayt RAM demektir. Yinelemeli derinleştirmeli A* (IDA*), sezgiselle derinlik sınırlı DFS yapıp her turda sınırı yükselterek belleği zamanla takas eder.
Her referans çözücünün 15 bulmaca için fiilen kullandığı algoritma IDA*'dır. Richard Korf 1985 tarihli makalesinde onu tam da 1980'lerin başındaki donanımlarda 15 bulmacaları optimal çözmek için tanıttı.
Manhattan'ın ötesi: yürüme mesafesi ve örüntü veritabanları
Manhattan mesafesi hızlıdır ama gevşektir. Taşların birbirinin içinden serbestçe geçebildiğini varsayar. Geçemezler — aynı satırdaki iki taş sırayla ilerlemek zorundadır ve bu ekstra hamlelere mal olur.
Yürüme mesafesi (walking distance) o ekstra hamleleri sayar. Her satır çifti için, taşları doğru satırlara yerleştirmek için gereken minimum "satır takası" sayısını önceden hesaplayın. Aynısını sütunlar için yapın. İkisini toplayın. Sonuç, Manhattan mesafesinden kanıtlanabilir biçimde daha sıkıdır — tipik olarak %25 kadar büyüktür, bu da A*/IDA*'ın çok daha az düğüm keşfetmesi demektir.
15 bulmaca için bilinen en güçlü sezgisel, toplamsal ayrık örüntü veritabanıdır (additive disjoint pattern database):
- Taşları ayrık gruplara bölün (yaygın bir bölme, 5-5-5 artı boşluktur).
- Her grup için, o grubun taşlarının tahtadaki her olası dizilimi için, diğer tüm taşları yok sayarak o taşları hedef konumlarına götürmenin minimum hamle sayısını önceden hesaplayın.
- Arama sırasında her grubun değerini tablodan alıp toplayın.
15 bulmaca için 7+8'lik bir bölme yaklaşık 1 GB yer kaplar ama IDA*'ın herhangi bir 15 bulmacayı milisaniyelerde çözmesini sağlar. 24 bulmaca (5×5) için örüntü veritabanları neredeyse tek pratik yaklaşımdır.
Elle çözmek (tek bulmaca için) neden genellikle daha hızlıdır
Kısa bir gerçeklik kontrolü: bir A* uygulaması yazmak, sezgisel seçmek ve çalışmasını beklemek, eline tek bir 15 bulmaca alıp elle çözmekten daha uzun sürer. Matematiği ilginçtir; pratikte ise satır-sütun yöntemini bilen biri herhangi bir tahtayı beş dakikada bitirir.
Çözücülerin önemi toplamdadır: binlerce rastgele örnek üzerinde sezgiselleri karşılaştıran araştırma makaleleri, 15 bulmacayı kıyaslama ölçütü olarak kullanan yapay zekâ ders kitapları ve zorluk ayarı için kabaca N hamlede çözülebileceği garantili bulmacalar üretmesi gereken uygulamalar.
Önerilen okuma sırası
Bu sayfaya bir çözücü yazma umuduyla geldiyseniz, A*/Manhattan ile başlayın, birkaç 8 bulmacayı çözmesini izleyin, sonra 15 bulmacalar için IDA*'a geçin. Ardından yürüme mesafesi, hızınızı ikiye katlayan 100 satırlık bir ektir. Örüntü veritabanları ise size bir kat daha hız kazandıran bir hafta sonu projesidir.
Buraya bir 15 bulmaca oynama umuduyla geldiyseniz, önce satır-sütun yöntemini öğrenin, sonra bazı tahtaların neden çözülemez olduğunu okuyun, teori için buraya geri dönün.