Pentomino Bölümlerini Dancing Links ile Nasıl Üretiyoruz

Nesim Razon, bağımsız Android geliştiricisi · 2026-11-10

Pentolings'teki her Döşe bölümü bir sözdür: bu şekli bu parçalarla doldurmanın bir yolu var. Bu sözü 150 bölümde tutmak ve istediğin an sana ipucu verebilmek için oyunun içinde Donald Knuth'un Dancing Links yöntemine dayanan küçük bir çözücü var. Herkesin izleyebileceği küçük bir örnekle nasıl çalıştığını anlatıyoruz.

Pentomino bulmacası bir tam kapsama problemidir

Bir bölüme kurallar listesi olarak bak. Her parça tam bir kez kullanılmalı. Şeklin her karesi tam bir kez kaplanmalı. Hiçbir şey üst üste binmemeli ve hiçbir şey artmamalı. Böyle kurallardan oluşan probleme tam kapsama (exact cover) problemi denir ve Sudoku'dan çizelgelemeye kadar çok bulmaca tam olarak budur.

Bilgisayara çözdürmek için problemi bir tablo olarak yazarız. Her sütun bir kuraldır: her parça için bir sütun ve şeklin her karesi için bir sütun. Her satır olası bir hamledir: belirli bir parça, belirli bir yöne çevrilmiş, belirli bir yere konmuş. Satır, sağladığı sütunları işaretler: parçanın kendi sütunu ve kaplayacağı beş kare. Satırları öyle seçersen ki her sütun tam bir kez işaretlenmiş olsun, bulmaca çözülmüştür.

63 duruş: tablonun satırları

Bir pentomino döndürülüp ters çevrilebilir; bu yüzden oyun önce on iki parçanın her birinin bütün farklı duruşlarını listeler. Şekli döndürür, aynalar ve yalnızca gerçekten yeni olan sonuçları tutar. X 1 duruş, I 2 duruş, T, U, V, W ve Z dörder, F, L, N, P ve Y sekizer duruş verir. Bunlar takım için toplam 63 duruş eder ve kod bu sayıyı denetler.

Sonra bölümün şekli için her duruşu, beş karesinin de şeklin içinde kaldığı her yere kaydırır. Tüm on iki parçalı 3x20 dikdörtgen için bu 1236 aday satır eder. En büyük bölüm olan 6x10 dikdörtgen için 2056 satır vardır. Tabloda 72 sütun bulunur: 12 parça ve 60 kare.

Küçük bir örnek

3x5'lik bir dikdörtgen ve P, U, V parçalarını al. Tabloda 3 parça sütunu ve 15 kare sütunu, yani toplam 18 sütun vardır. Parçaların sırasıyla 40, 20 ve 12 olası yerleşimi var; bu da 72 satır eder. Her sütunu tam bir kez işaretleyen üç satır seçince cevap çıkar: V sol ve alt kenarda, U sağda, P ortada. Yazıyla tahtanın üç satırı VPPUU, VPPPU ve VVVUU olarak okunur. Tüm dikdörtgeni döndürmek ya da aynalamak aynı cevabın dört sürümünü verir; yani çözücü, bir insana aynı görünen dört çözüm bulur.

Knuth'un Dancing Links yöntemi, sade sözlerle

Arama, Algoritma X'tir. Henüz kaplanmamış bir sütun seç. Onu işaretleyen her satırı dene. Bir satırı seçmek, onun diğer sütunlarının artık alındığı anlamına gelir; bu yüzden onunla çakışan her satır atılabilir. Sonra küçülmüş tabloyla aynı işlemi tekrarla. Bir sütunda hiç satır kalmazsa daha önce yanlış seçim yapmışsındır; geri çekilip sıradaki satırı denersin.

Zekice olan, tablonun saklanış biçimidir. Donald Knuth, işaretleri bağlı listelerde tutabileceğini fark etti: her işaret sol, sağ, üst ve alt komşusunu gösterir. Bir satırı kaldırmak birkaç bağlantıyı yeniden yönlendirmekten ibarettir ve kaldırılan öğe yerini hatırlamaya devam eder; geri koymak adımları tersine yapmak demektir. Düğümler sanki dışarı fırlayıp geri giriyor gibi göründüğünden bu tekniğe Dancing Links (dans eden bağlantılar) adını verdi. Pentolings'te Dlx.kt yaklaşık seksen satırdır ve hız için düz tamsayı dizileriyle çalışır.

Bir numara daha: çözücü her adımda geriye en az satırı kalan sütunu seçer. Bir kare yalnızca iki yolla kaplanabiliyorsa arama, tabloda gezinmek yerine hemen bu ikisini dener. Bu, rehberde söylediğimizin bilgisayar sürümüdür: önce dar yerlerden başla.

Kilitli parçalar ve adil bölümler

Bazı Pentolings bölümleri kilitli bir parçayla başlar. Bu parçalar gerçek bir çözümden gelir: üretici bir cevap bulur, sonra onun bir ya da iki parçasını dondurur. Çözücü onları zaten seçilmiş sayar, karelerini ve sütunlarını tablodan çıkarır ve geriye kalanı sayar.

Bölüm yapmak çözmekten fazlasıdır. Üretici, parçaları rastgele yan yana koyarak bir silüet oluşturur; böylece yapısı gereği bir çözüm vardır. Sonra çok sayıda silüeti puanlar: dolgun şekilleri ödüllendirir, delikleri cezalandırır, simetriyi ödüllendirir ve ilk bölümlerde daha çok cevabı olan şekilleri tercih eder. Bu yolla yapılan silüetlerin çoğunun tam bir çözümü olduğundan, zorluk esas olarak parça sayısı ve silüetin tuhaf biçiminden gelir. 150 bölümün her biri testlerde yeniden çözülür, tekrar var mı diye bakılır (döndürülmüş ya da aynalanmış kopya aynı sayılır) ve son bölüm olan 6x10 dikdörtgen, çok büyük sayıda cevabı olan tek yerdir. Bir test ayrıca 3x20 için klasik sayıyı doğrular: sekiz; bu, iki gerçek cevabın dikdörtgeni döndürme ya da aynalamanın dört yolu ile çarpımıdır.

Neden her şeyi denemiyoruz?

Bir bulmacayı her parçayı her duruşta sırayla deneyerek ve sonunda kontrol ederek çözebilirsin. Bu, bilgisayar için bile işe yaramaz. On iki parça, 63 duruş ve onlarca yerle kombinasyon sayısı astronomiktir ve neredeyse hepsi ilk birkaç hamlede üst üste biner ya da boşluk bırakır.

Püf noktası, kötü bir dalın kötü olduğunu görür görmez durdurmaktır. Algoritma X tam olarak bunu yapar. Bir kareyi kaplayabilecek hiçbir parça kalmadığı anda arama daha derine gitmez ve geri çekilir. Dancing Links her geri çekilmeyi ucuzlatır. 2056 aday yerleşimli bir 6x10 tahtanın telefonda bile çabucak çözülmesinin ve ipucu düğmesinin sunucuya ihtiyaç duymamasının nedeni budur.

Ne öğrendik

Aynı çözücü mantığı iki yerde var: 150 bölümlük paketi üreten ve denetleyen Python'da ve uygulamada yayına giden Kotlin'de. Kotlin testleri paketin her bölümünü sıfırdan yeniden çözer. İki bağımsız uygulama olması, birindeki hatanın ötekinden saklanmasını zorlaştırır.

En büyük sürpriz, rastgele bir silüetin birden fazla cevabının ne kadar nadir olduğuydu. Birçok bulmacanın birkaç çözümü olmasını bekliyorduk ve tersini bulduk. Bunun sorun olmadığı ortaya çıktı: oyuncular bir bölümün çözülebilir ve adil olmasını önemser, kaç çözümü olduğunu değil; bu yüzden oyun geçerli her doldurmayı kabul eder. Çözücünün bize verdiği, her bölümün ve her ipucunun güvenilebileceği sözüdür.

İpuçları aynı çözücüden gelir

İpucu düğmesi çözücüye yeni bir soru sorar: şimdiye kadar yerleştirdiğin parçalar verilmişken geri kalanı nasıl sığar? Yerleştirdiğin parçaları sabit sayar, kalanı çözer ve bulduğu cevaptaki sıradaki parçayı parlatır. İpucunu izlersen bir sonraki, yeniden çözmeden bellekten gelebilir. İş arka planda, zaman sınırıyla çalışır; ekran hiç donmaz.

Yerleştirdiğin parçalar çözümü imkânsız kılıyorsa çözücü hiçbir şey bulamaz ve oyun bunu söyler: buradan çözüm yok, bir parçayı geri al. Bu, ipucunu yalnızca takıldığında değil, emin olmadığında da işe yarar kılar. Oyun, şekli doldurmanın üreticinin bulduğu yolu değil, geçerli herhangi bir yolunu kabul eder; yani yazarın cevabını tahmin etmeye zorlanmazsın.