Bir 15'li bulmacayla otuz dakika geçirip bir türlü bitirememişsen — yaptığın her hamle en sonda yer değiştirmiş iki taşa çıkıyorsa — bulmacan matematiksel olarak çözülemez olabilir. Tüm 15'li bulmaca dizilimlerinin tam yarısı öyledir. Kötü yazılmış bir uygulama bunlardan birini yanlışlıkla üretebilir.
Bu makale pratik kontroldür. Tam matematiksel gerekçe parite teoreminde; burada işi sade tutuyoruz.
30 saniyelik kontrol
Taşlara okuma sırasıyla bak — her satırda soldan sağa, yukarıdan aşağıya — boşluğu yok sayarak.
Her taş çifti için, büyük bir sayının küçük bir sayıdan önce kaç kez geldiğini say. Bu sayı inversiyon sayısıdır.
Sonra boş hücrenin hangi satırda olduğunu, aşağıdan sayarak not et (en alt satır 1, üstündeki 2, sonra 3, en üstte 4).
İnversiyon sayısıyla boşluğun aşağıdan satır numarasını topla. Sonuç tekse bulmaca çözülebilir. Çiftse çözülemez.
Bu kadar. Kontrolün tamamı bu.
Çözümlü bir örnek
Tahtan şöyle görünsün:
1 2 3 4
5 6 7 8
9 10 11 12
13 15 14 _
Okuma sırası: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14.
İnversiyonları sayalım. Büyük bir sayının küçük bir sayıdan önce geldiği her çifti bulmamız gerekiyor. Bakınca: 15, 14'ten önce geliyor ve tek inversiyon bu. Yani inversiyon sayısı = 1.
Boşluk en alt satırda → aşağıdan 1. satır.
Toplam: 1 + 1 = 2. Çift. Bu tahta çözülemez.
Bu aslında Sam Loyd'un 1880 tarihli ödüllü bulmacasıdır. Adam çözene 1000 dolar teklif etti. Bulmaca çözülemezdi; parası cebinde kaldı.
Bir örnek daha
Tahtan şöyle görünsün:
5 1 3 4
2 6 7 8
9 10 11 12
13 14 15 _
Okuma sırası: 5, 1, 3, 4, 2, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.
İnversiyonları sayalım:
- 5, 1'den önce → 1 inversiyon (5 > 1 ve 5 önce geliyor)
- 5, 3'ten önce → 1 inversiyon
- 5, 4'ten önce → 1 inversiyon
- 5, 2'den önce → 1 inversiyon
- 3, 2'den önce → 1 inversiyon
- 4, 2'den önce → 1 inversiyon
Toplam inversiyon: 6.
Boşluk en alt satırda → 1. satır.
Toplam: 6 + 1 = 7. Tek. Bu tahta çözülebilir.
Bu neden çalışır (kısaca)
Geçerli bir kaydırma ya bir taşı yatay oynatır (inversiyonlar değişmez, boşluğun satırı değişmez) ya da dikey oynatır (inversiyonları tek bir sayı kadar değiştirir, boşluğun satırını 1 değiştirir).
Her iki durumda da inversiyonlar + boşluğun satırı toplamının tek-çift durumu başladığı gibi kalır. Yani bu toplam bir değişmezdir — geçerli hamlelerin değiştiremeyeceği bir bulmaca özelliği.
Hedef durumun (1‑2‑3‑...‑15, boşluk sağ altta) 0 inversiyonu vardır ve boşluk aşağıdan 1. satırdadır. Toplam: 1, tek. Dolayısıyla çözülebilir her bulmacanın toplamı tektir. Toplamı çift olan hiçbir bulmaca hedefe ulaşamaz.
Tüm durumların işlendiği tam kanıt için parite teoremi sayfasına bak.
Peki 8'li bulmacalar (3×3)?
3×3 için kontrol daha basittir:
- Okuma sırasında inversiyonları say.
- Çiftse çözülebilir.
- Tekse çözülemez.
3×3'te boşluğun satırını izlemene gerek yok, çünkü bulmacanın simetrisi satır bağımlılığını gereksiz kılar.
(5×5 için — 3×3 ile aynı kural. 6×6 için — 4×4 ile aynı kural. Kural şu: "N çiftse boşluğun satırı önemlidir".)
Uygulaman çözülemez bulmacalar üretiyorsa ne yapmalı
Bu asla olmamalı. İyi yazılmış bir uygulama bundan kaçınmak için iki yöntemden birini kullanır:
Hedeften geriye yürüyerek üret. Hedef durumla başla, rastgele geçerli hamleler uygula ve ortaya çıkan durumu başlangıç konumu olarak kullan. Bu şekilde üretilen her konum, yapısı gereği çözülebilirdir.
Rastgele üret, sonra pariteyle test et. Taşları düzgün rastgele karıştır; parite kontrolünü hesapla; çiftse herhangi iki taşın yerini değiştirerek düzelt. Ortaya çıkan konum garantili çözülebilirdir.
Bir uygulamada çözülemez bir bulmacayla karşılaşırsan, o uygulama bozuktur. Hatayı bildir, uygulama değiştir. Slide Puzzle hedeften-geriye-yürüme yöntemini kullanır ve çözülemez başlangıç konumu üretemez.
Fiziksel bulmacanın çözülemez olduğundan şüpheleniyorsan
İki şey:
- Kontrolü yap. İnversiyonlar artı boşluğun satırı. Çiftse, fiziksel parçalar yanlış takılmış demektir. Bir taşı çıkar, bitişik bir taşla yerini değiştir; bulmaca artık çözülebilir.
- Takastan sonra bile bulmaca hâlâ direniyorsa — direnen bulmaca değil, stratejindir.
Parite kontrolü yaklaşık otuz saniye sürer. Sıkışmış bir tahtaya bir saat daha gömmeden önce bunu yapmak, o saniyelerin makul bir kullanımıdır.