Kısıtlama modeli
Değişkenler: her boş hücre. Alan: 1–9 rakamlar. Kısıtlamalar: her satır, sütun ve 3×3 kutu tam olarak bir kez tüm rakamları içermelidir. Bu klasik bir tam kapsam problemidir. Donald Knuth'un Algoritma X'i, dans eden bağlantılarla uygulanan, kısıtlama alanını kapsamlı arayarak herhangi bir geçerli Sudoku'yu milisaniyeler içinde çözer.
İnsan stratejileri sezgi olarak
İnsanlar Sudoku çözerken 'çıplak çiftler', 'X-Kanat' ve 'kılıçbalığı' gibi isimleri olan stratejiler kullanır. Her biri hücrelerden adayları eleyen bir kalıptır. AI terimlerinde bunlar kısıtlama yayılımı sezgileridir — geri izleme gerekmeden önce arama alanını azaltan kurallar. 'Şeytani' olarak derecelendirilen bir bulmaca basitçe basit sezgisellerin yetersiz kaldığı biridir.
Çözme çözmekten daha zor
Benzersiz bir çözümü olan bir Sudoku yaratmak birini çözmekten hesaplama açısından daha zordur. Oluşturucular tam bir ızgarayla başlar, sayıları kaldırır ve her kaldırma sonrası benzersizliği kontrol eder. Zorluk kontrol etmek bir sanattır: çok fazla verilen ve önemsizdir; çok az ve kaba kuvvet gerekir. En iyi bulmaca yayınları insan derecelendirilmiş zorluk eğrileri kullanır.
Bulmacadan paradigmaya
Sudoku'nun kısıtlama yapısı programlama, kaynak tahsisi, devre tasarımında ve hatta radar hedef ilişkilendirme problemlerinde görülür. Bir radarın birden fazla hedefi ve birden fazla izi varsa, ölçümleri izlere atamak ek olasılıksal ağırlıkları olan bir kısıtlama memnuniyeti problemidir. Gazete Sudoku'nuzu çözen çözücü, füze izlerinin takas edilmesini önleyen çözücüyle kuzenidir.
Minimum ipucu sayısının matematiği
Graf teorisi ve mantık kesişimindeki en köklü sorulardan biri, bir Sudoku'nun benzersiz bir çözüme sahip olması için gereken minimum başlangıç ipucu sayısıydı. 2012 yılında, Dublin Üniversitesi'nden Gary McGuire liderliğindeki bir ekip, aylar süren kapsamlı bir bilgisayar taraması sonucunda 16 ipucuna sahip benzersiz bir Sudoku'nun var olamayacağını kanıtladı. Bu sonuç, geçerli bir bulmaca için 17 ipucunun mutlak alt sınır olduğu kuralını kesinleştirdi. Milyonlarca CPU saati süren bu hesaplama, 9x9 luk bir ızgaranın basit görünmesine rağmen, konfigürasyon alanının küresel kanıtlar için süper bilgisayar gücü gerektirecek kadar geniş olduğunu göstermiştir.
Bu sınır sadece bir bilgi notu değil, aynı zamanda Sudoku oluşturma algoritmalarının limitlerini belirleyen bir unsurdur. Eğer bir oluşturucu ızgarayı 16 ipucuna kadar düşürürse, kaçınılmaz olarak birden fazla geçerli tamamlamanın mümkün olduğu bir mantıksal belirsizliğe girer. İlginçtir ki, 17'den 18 ipucuna geçiş zorlukla doğrusal olarak ölçeklenmez. 17 ipuçlu bir bulmaca temel tarama yöntemleriyle çözülebilirken, 25 ipuçlu bir bulmaca ileri düzey zincirleme mantık gerektirebilir. Karmaşıklık, başlangıç rakamlarının yoğunluğundan ziyade kısıtlamaların kendi aralarındaki spesifik etkileşimi tarafından belirlenir.
Sudoku'nun kökeni ve 1979'daki çıkışı
İsminden dolayı genellikle Japon kültürüyle bağdaştırılsa da, modern Sudoku formatı Amerikalı mimar ve bağımsız bulmaca tasarımcısı Howard Garns tarafından icat edilmiştir. İlk olarak 1979'da Dell Pencil Puzzles and Word Games dergisinde 'Number Place' başlığıyla yayımlandı. Garns, 18. yüzyılda Leonhard Euler tarafından üzerinde çalışılan 'Latince Kareler' kavramını, alt ızgara kısıtlamasını ekleyerek uyarladı. Bu küçük ekleme, standart bir kombinatoryal problemi, çözücüleri bölgesel kutu kısıtlamaları ile küresel satır ve sütun kurallarını dengelemeye zorlayan karmaşık bir mantık mücadelesine dönüştürdü.
Bulmaca, 1980'lerin ortalarına kadar uluslararası bir ün kazanmadı; bu dönemde Japon bulmaca şirketi Nikoli'nin başkanı Maki Kaji kuralları sadeleştirdi ve adını 'Sūji wa dokushin ni kagiru' ifadesinin kısaltması olan Sudoku olarak değiştirdi. Kaji'nin en büyük katkısı, simetriyi standartlaştırmak ve bilgisayar yapımı bulmacalar yerine elle tasarlanmış olanları tercih etmekti. Bu manuel kürasyon, her bulmacanın tahmin yürütmeden bir insan tarafından çözülebilecek mantıklı bir yol izlemesini sağlayarak, Sudoku'yu rastgele rakam yerleştirmelerinden ayıran pedagojik bir felsefe oluşturdu.
Boolean Sağlanabilirlik yaklaşımı
Geriye dönük arama standart bir pedagojik yaklaşım olsa da, modern yüksek hızlı çözücüler Sudoku'yu genellikle bir Boolean Sağlanabilirlik (SAT) problemi olarak yeniden formüle eder. Her hücrenin potansiyel değeri, hücre (i,j) d rakamını içeriyorsa 'x_i_j_d'nin doğru olduğu bir dizi ikili değişken olarak kodlanarak bulmaca Konjonktif Normal Form'a (CNF) dönüştürülür. Standart 9x9'luk bir ızgara yaklaşık 729 değişken ve 8.000'den fazla yan tümce üretir. Bu, MiniSat veya Glucose gibi çözücülerin çatışma odaklı yan tümce öğreniminden (CDCL) yararlanmasına olanak tanır. Bu algoritmalar sadece arama yapmaz; çelişkilerden mantıksal çıkarımlar öğrenerek çözümü basit deneme yanılma yerine önermesel mantık yoluyla kanıtlarlar.
SAT tabanlı çözücülerin verimliliği, standart 9x9 ızgaranın ötesine geçildiğinde belirginleşir. 'Sudoku-X' veya 'Hiper Sudoku' varyantları için köşegen veya örtüşen kısıtlamaların eklenmesi, yan tümce kümesinin karmaşıklığını artırır ancak çözücüyü nadiren yavaşlatır. Aslında birçok araştırma makalesi, hücresel ağlarda frekans ataması veya yazılım paketi bağımlılık çözümlemesi gibi daha karmaşık kombinatoryal problemleri açıklamak için Sudoku'yu bir geçit olarak kullanır. Izgara, sınırlı bir olasılık kümesi genelinde birden fazla çelişen gereksinimin aynı anda karşılanması gereken kaynak tahsisinin gizli karmaşıklığı için görsel bir temsilci görevi görür.
17 ipucu eşiği
Sudoku matematiğinde uzun süredir devam eden bir soru, benzersiz bir çözüm için gereken minimum ipucu sayısıydı. 2012 yılında, Dublin Üniversitesi'nden Gary McGuire ve ekibi, kapsamlı bir hesaplamalı arama yoluyla, benzersiz bir çözüme sahip hiçbir 16 ipuculu Sudoku'nun var olmadığını kanıtladı. Proje, 600'den fazla düğümden oluşan bir kümede yedi milyon CPU saatinden fazla zaman gerektirdi. Herhangi bir 16 ipuculu yapılandırmanın kaçınılmaz olarak en az iki geçerli tamamlamaya yol açacağını göstermek için bir 'vuruş kümesi' (hitting set) algoritması kullandılar ve böylece 17'yi düzgün biçimlendirilmiş bir bulmaca için matematiksel taban olarak sabitlediler.
Bu kanıt, on yıllık spekülasyonu sona erdirdi ve 'çözülebilirlik' ile 'iyi tanımlanmışlık' arasındaki ayrımı vurguladı. 17'den az ipucu içeren bir bulmaca oluşturmak mümkün olsa da, bu her zaman matematiksel olarak belirsiz kalacaktır. İlginç bir şekilde, 'en zor' 17 ipuculu bulmaca arayışı, 2006 yılında Arto Inkala tarafından 'AI Escargot'un yaratılmasına yol açtı. Bu bulmaca, derin ileriye bakma adımları gerektirerek basit dallanma algoritmalarını alt etmek için özel olarak tasarlanmıştı. Bu tür bulmacalar, zorluğun yalnızca ipucu sayısının bir fonksiyonu olmadığını, başlangıç durumu ile ilk türetilebilir çıkarım arasındaki mantıksal mesafeye bağlı olduğunu kanıtlar.