1 Kombinatorik Temel: Kaç Tamamlanmış Izgara Var?
Sudoku’nun kalbinde kombinatorik vardır. 9×9’luk tamamlanmış (geçerli) Sudoku ızgaralarının sayısı yaklaşık 6,67×1021’dir. Bu astronomik sayı, “tüm satırlar, sütunlar ve 3×3 kutular 1–9’u tekrarsız içerir” kısıtları altında olası yerleşimlerin sayılmasıyla elde edilir. Sayım; permütasyonlar, satır bantları ve sütun istifleri üzerinde simetri azaltımıyla yapılır.
Pratik sonuç: Üreteçler (generator) bu uzaydan örnek çekerken genellikle önce tamamlanmış bir ızgara kurar, ardından ipuçlarını (clues) seçip geri siler. Böylece mantık yürütmeye elveren, tek çözümlü bulmaca elde edilir.
2 Kısıt Programlama: Adaylar, Çıkarım ve Tutarlılık
Sudoku, bir kısıt tatmin problemi (CSP) olarak modellenir: 81 hücre değişken, alanları {1,…,9}, kısıtlar satır/sütun/kutu tekilliğidir. Çözücüler; ileri denetim, alan daraltma ve tutarlılık (ör. AC-3) gibi yöntemlerle adayları eler. “Naked/Hidden Single, Pair/Triple, Pointing/Claiming, X-Wing” gibi teknikler bu CSP mantığının insan-dostu adlandırılmış halleridir.
- Notlar (kandideler): Her hücre için olası rakam kümesini izler.
- Yerleştirme etkisi: Bir sayı konunca ilişkili satır/sütun/kutu alanları daralır.
- Çatallaşma: Tıkanınca en kısıtlı hücreden dallanma (search) yapılır.
3 Grafik Kuramı: 9-Renkleme ve Çakışma Grafiği
Sudoku, düğümleri hücreler olan ve kenarları “aynı satır/sütun/kutu” komşuluğunu gösteren bir çakışma grafiğine dönüştürülebilir. Amaç; 9 rengi (1–9) öyle atamak ki komşu düğümler aynı rengi alamasın. Bu bir graf renkleme problemidir. Ancak 3×3 kutu kısıtı klasik satranç vari ızgaralara göre grafiği yoğunlaştırır; bu yüzden sezgisel kurallar ve global örüntüler (X-Wing, Swordfish vb.) önem kazanır.
4 Exact Cover ve DLX (Dancing Links)
Sudoku, “her kısıt tam olarak bir kez karşılanmalı” biçiminde Exact Cover’a indirgenir. Dört kısıt ailesi (hücre-doluluk, satır-rakam, sütun-rakam, kutu-rakam) için 729×324 boyutlu ikili bir matris kurulur. Knuth’un DLX algoritması bu matriste çok hızlı geri izleme yapar. DLX, sütun-satır kaldırma ve geri getirme işlemlerini dancing links veri yapısıyla verimli kılar; birçok makine çözücüsü bu yaklaşımı kullanır.
5 Zorluk Ölçümü: Bilgi İçeriği, Entropi ve Arama Derinliği
Zorluk, yalnızca boşluk sayısına bağlı değildir. İki temel bileşen öne çıkar: (1) Bilgi kuramı açısından ipuçlarının ızgarayı ne kadar kısıtladığı (kalan adayların ortalama entropisi), (2) arama maliyeti (gereken çıkarım zincirlerinin uzunluğu, insan tekniklerinin sırası). İyi tasarlanmış bir bulmaca, tek çözümlüdür ve çözüm sırasında bilgi akışı kademeli ilerler.
6 Eşsizlik, İpucu Sayısı ve Simetri
İyi bir Sudoku tek çözümlü olmalıdır; aksi halde tahminle çoklu çözüm oluşabilir. 9×9 klasik Sudoku için bilinen en düşük ipucu sayısı 17’dir; 16 ipucuyla tek çözümlü klasik Sudoku yoktur. Tasarımda simetriler (dönme, yansıma) estetik sağlar ancak gereğinden fazla simetri bazen çoklu çözüme yol açabileceği için ek kısıtlar gerekir. Bu denge, tasarımcının matematiksel sezgisidir.
7 Sonuç: Mantığın Matematikle Buluşması
Sudoku; kombinatorik sayım, grafik renkleme, kısıt programlama ve Exact Cover gibi güçlü matematiksel kavramların pratik bir oyun yüzüdür. İyi bir ızgara, rastgelelik değil, bilgi akışı tasarımıdır. Teoriyi pratiğe dökmek için şimdi bir bulmaca aç: Ozerlyn Sudoku.