Çoğumuz sudokuyla hazır bir ürün olarak tanışırız: birkaç rakamı önceden yazılmış bir tablo ve tepesinde bir zorluk etiketi. O tablonun nereden geldiğini pek düşünmeyiz. Hangi hücrelerin açık bırakılacağına kim karar verdi? Düzgün bir bulmacanın neden her zaman tek bir cevabı var? “Kolay” yazan bir bulmaca neden sizi yirmi dakika uğraştırırken, bomboş görünen bir başkası birkaç dakikada çözülüyor? Bu soruların arkasında şaşırtıcı derecede derin bir matematik yatıyor. İşin içinde bir yıl boyunca süper bilgisayarda çalışan meşhur bir kanıt bile var. Bu yazıda konuyu sade bir dille anlatıyor, ardından bulmaca seçerken ve çözerken işinize yarayacak pratik sonuçlara bağlıyoruz.

Kaç farklı sudoku tablosu var?

Önce tamamlanmış tablolarla başlayalım: her satırda, her sütunda ve her 3×3 kutuda 1’den 9’a kadar rakamların birer kez yer aldığı 9×9 tablolar. Bertram Felgenhauer ve Frazer Jarvis bunları bilgisayarla saydı ve sonucu 2006’da Mathematical Spectrum dergisinde yayımladı. Tam olarak 6.670.903.752.021.072.936.960 tane, yani yaklaşık 6,67 × 10²¹ geçerli tablo var.

Ancak bu tabloların çoğu aslında kılık değiştirmiş aynı tablodur. Rakamların adını değiştirebilirsiniz (bütün 1’leri 7 yapmak gibi), üçlü bir bant içindeki satırların yerini değiştirebilir, bantları kendi aralarında takas edebilir, aynısını sütunlara uygulayabilir ya da tabloyu köşegen boyunca çevirebilirsiniz. Ed Russell ve Frazer Jarvis, grup teorisindeki Burnside önsavını kullanarak bu dönüşümlerden sonra gerçekten farklı kalan tabloları saydı. McGuire ve arkadaşlarının aktardığına göre hesaplamanın kendisi yalnızca bir saniye kadar sürdü. Sonuç: 5.472.730.538 “özünde farklı” tablo.

Tamamlanmış sudoku tablolarının sayısı
Sayılan	Adet	Kaynak
Tamamlanmış 4×4 tablolar (2×2 kutulu)	288	McGuire, Tugemann ve Civario
Tamamlanmış 9×9 tablolar	6.670.903.752.021.072.936.960	Felgenhauer ve Jarvis (2006)
Özünde farklı 9×9 tablolar	5.472.730.538	Russell ve Jarvis (2007)

En az 17 ipucu: 16 neden imkânsız?

Bir bulmaca, rakamlarının çoğu silinmiş bir çözüm tablosudur. Fazla silerseniz geriye kalan ipuçları artık tek bir cevaba işaret etmez. Peki düzgün bir bulmaca en az kaç ipucuyla kurulabilir? Meraklılar 17 ipuçlu on binlerce bulmaca buldu. Gordon Royle bunları bir listede topladı ve listesi zamanla 49.151 farklı 17 ipuçlu bulmacaya ulaştı. 16 ipuçlu geçerli bir bulmaca ise hiç bulunamadı. Fakat “kimse bulamadı” demek bir kanıt değildir.

Kanıtı Gary McGuire, Bastian Tugemann ve Gilles Civario getirdi. Ön baskıları Ocak 2012’de yayımlandı, hakemli sürümü ise 2014’te Experimental Mathematics dergisinde çıktı. Yöntemlerini anlatmak kolay, uygulamak son derece zordu: olası bütün çözüm tablolarını tek tek tarayıp içlerinde saklı 16 ipuçlu bir bulmaca aramak.

İşin anahtarı kaçınılmaz küme (unavoidable set) kavramı. İki satır, iki sütun ve iki kutuya yayılan dört hücre düşünün; içlerinde 3-8 / 8-3 düzeni olsun. Bu dört hücredeki 3’lerle 8’lerin yerini değiştirirseniz yine tamamen geçerli bir tablo elde edersiniz. Demek ki bu dört hücreden hiçbiri ipucu olarak verilmezse bulmacanın iki çözümü olur. Her tamamlanmış tabloda büyüklü küçüklü pek çok böyle küme vardır ve düzgün bir bulmaca her birine en az bir ipucu yerleştirmek zorundadır. Matematikte buna vuran küme (hitting set) problemi denir. Ekip, bir tablonun 16 hücreli bütün vuran kümelerini listeleyip bunlardan herhangi birinin tek çözüm verip vermediğini test eden checker adlı çok hızlı bir program yazdı.

Ardından programı 5.472.730.538 özünde farklı tablonun tamamı üzerinde çalıştırdılar. Arama Ocak–Aralık 2011 arasında İrlanda Yüksek Başarımlı Hesaplama Merkezi’ndeki (ICHEC) Stokes kümesinde yürütüldü. Yaklaşık 7,1 milyon çekirdek-saat harcandı ve tablo başına ortalama süre 3,6 saniye civarındaydı. Yazarlar, programlarının 2006’daki ilk sürümüyle aynı işin tahminen 300.000 işlemci-yılı süreceğini belirtiyor. Daha iyi algoritmalar bunu yaklaşık 800 işlemci-yılına indirdi. Hiçbir 16 ipuçlu bulmaca çıkmadı. Yani en az ipucu sayısı gerçekten 17.

Kanıtı tek cümleye sığan daha basit bir gerçek de var: düzgün bir bulmacada dokuz rakamdan en az sekizi ipucu olarak görünmelidir. Örneğin 4 ve 6 ipuçlarında hiç yer almasaydı, çözümdeki bütün 4’lerle 6’ların yerini değiştirip ikinci bir geçerli cevap elde edebilirdiniz.

Tek çözüm neden önemli? (Ve neden asla tahmin etmeniz gerekmez?)

Peter Norvig, sudoku çözmeye dair tanınmış yazısında şöyle der: “Puzzles that appear in books and newspapers always have one unique solution.” (Kitap ve gazetelerde yer alan bulmacaların her zaman tek bir çözümü vardır.) Bu yalnızca bir gelenek değildir. Sudokuyu şans oyunu değil mantık bulmacası yapan şey tam olarak bu tekliktir.

Bir bulmacanın tek çözümü varsa her hücrenin değeri ipuçları tarafından zorunlu kılınır. Yani başlangıçtan sona uzanan bir akıl yürütme zinciri mutlaka vardır, uzun ve bulması zor olsa bile. İki çözümlü bir bulmacada ise eninde sonunda bir hücreye hem 2’nin hem 5’in uyduğu ve tablodaki hiçbir şeyin hangisini seçeceğinizi söyleyemediği bir ana gelirsiniz. Tahmin etmek zorunda kalırsınız. Üstelik kitabın arkasındaki “doğru” cevap, son derece mantıklı sonucunuzla yarı yarıya çelişir.

Norvig’in yazısı tekliğin neden bilerek kontrol edilmesi gerektiğini de gösteriyor. Basit rastgele üreticisi, en az 17 kare ve 8 farklı rakam dolana kadar hücreleri dolduruyor. Hızlı bir yöntem ama Norvig sonucun tek çözümlü olmasının garanti olmadığını vurguluyor: rastgele bulmacalarının bazılarının birden çok çözümü var, küçük bir kısmının ise hiç çözümü yok.

Simetri ve el yapımı bulmacalar

Bugün sudoku dediğimiz bulmaca ilk olarak ABD’de ortaya çıktı. Genellikle Howard Garns’a atfedilir ve 1979’da Dell Magazines tarafından Number Place adıyla yayımlandı. Japon yayıncı Nikoli, internet sitesinde bulmacayı bir Amerikan dergisinde gördüğünü ve 1984’te Japon okurlarına tanıttığını, uzun Japonca adını da sonradan “Sudoku” olarak kısalttığını anlatıyor. Nikoli’ye göre bulmaca başta pek tutmadı. 1986’da editörler ipuçlarının simetrik bir düzende yerleştirilmesi kuralını getirdi ve bundan sonra büyük bir başarı yakaladı.

En yaygın düzen 180 derecelik dönme simetrisidir: tabloyu baş aşağı çevirdiğinizde ipucu hücreleri yine ipucu hücrelerine denk gelir. Bunun mantık üzerinde hiçbir etkisi yoktur, tamamen estetiktir. Küçük bir bedeli de var: bu simetriye sahip bir bulmacada en az ipucu sayısının 17 değil 18 olduğu düşünülüyor.

Nikoli bulmacalarını hâlâ elle hazırlıyor. Bunun nedenini anlattığı sayfada genel yayın yönetmeni Nobuhiko Kanamoto şöyle diyor: “Good Sudoku authors are always considering a solver’s feelings.” (İyi sudoku yazarları her zaman çözen kişinin duygularını düşünür.) İnsan bir hazırlayıcı tatmin edici bir yol planlayabilir: yumuşak bir açılış, ortada zekice bir adım ve temiz bir bitiş. Bilgisayar ise sonsuz sayıda geçerli bulmaca üretebilir, ama bunların böyle bir tasarım hissi taşıyıp taşımadığı ne kadar özenle süzüldüklerine bağlıdır.

Bilgisayar üreticileri genellikle nasıl çalışır?

Sudoku sitelerinin, uygulamalarının ve kitaplarının çoğu üretici programlara dayanır. Ayrıntılar değişse de genel yöntem şöyledir:

Dolu bir tablo kurulur. Rastgele seçimler yapan geri izlemeli (backtracking) bir çözücü boş tabloyu doldurur ve böylece rastgele, geçerli bir çözüm elde edilir.
İpuçları silinir. Hücreler tek tek (simetri isteniyorsa simetrik çiftler hâlinde) boşaltılır.
Her silmeden sonra teklik kontrol edilir. Bir çözücü çözümleri sayar ve ikinciyi bulduğu anda durur. Birden fazla çözüm varsa son silinen ipucu geri konur.
Sonuç derecelendirilir. İnsan tekniklerini taklit eden ikinci bir çözücü, kolay adımlardan zor adımlara doğru bulmacayı çözer ve gereken en zor tekniği kaydeder.

Ozerlyn Games’teki bulmacalar da bu ilkeleri izler: her bulmacanın tek bir çözümü vardır ve bir zorluk seviyesine atanmıştır. Böylece yalnızca mantıkla çözülebilir.

Zorluğu ipucu sayısı değil teknik belirler

Daha az ipucunun daha zor bulmaca demek olduğunu düşünmek kolaydır. Kaba bir kural olarak biraz doğruluk payı var ama güvenilir değil. María Ercsey-Ravasz ve Zoltán Toroczkai, 2012’de Scientific Reports’ta yayımlanan çalışmalarında bulmacaların zorluğunu matematiksel bir modelle ölçtü. Test ettikleri 17 ve 18 ipuçlu bulmacaların, 21–22 ipuçlu en zor bulmacalardan daha kolay olduğunu buldular. Vardıkları sonuç: zorluk yalnızca ipucu sayısına değil, ipuçlarının nereye yerleştirildiğine de bağlı.

Bir karşılaştırmayla anlatalım. A bulmacasında yalnızca 24 ipucu var, ama öyle dağılmışlar ki her aşamada bir rakamın bir satırda, sütunda ya da kutuda gidebileceği tek bir yer kalıyor. Tablo dolana kadar gizli tekli (hidden single) bulmaya devam etmeniz yeterli. B bulmacasında ise 30 ipucu var. Buna rağmen bir düzine kolay yerleştirmeden sonra kalan her hücrede iki ya da üç aday kalıyor ve hiç tekli yok. Devam etmek için X-Wing ya da bir zincir gerekiyor. İpucu sayılarına rağmen A kolay, B zor bir bulmacadır.

Bu yüzden ciddi derecelendirme sistemleri gereken teknikleri ölçer. En bilineni Sudoku Explainer (SE) puanıdır. Bir bulmacayı çözmek için gereken en zor adıma göre puan verir: tekliler düşük, ikililer ve X-Wing daha yüksek, zincirler ve zorlama ağları (forcing nets) ise daha da yüksek puan alır. Sudoku SE rating nedir? yazımız ölçeği ayrıntılı olarak anlatıyor. SE rating hesaplayıcımızla istediğiniz bulmacanın puanını kendiniz de bulabilirsiniz.

Oyuncu olarak sizin için ne anlama geliyor?

Bulmacayı ne kadar boş göründüğüne göre değil, zorluk derecesine göre seçin. Seyrek bir tablo zor olmak zorunda değildir, kalabalık bir tablo da kolay olmak zorunda değildir.
“Kolay” bir bulmaca size zor geliyorsa muhtemelen yalnızca çıplak teklileri (tek adayı kalan hücreleri) arıyorsunuz. Kolay bulmacalar çoğu zaman gizli teklilere dayanır. “Bu hücreye ne gelebilir?” yerine “Bu kutuda 7 nereye gidebilir?” diye sorun.
Tahmin etmeniz gerektiğini hissediyorsanız bir şeyi kaçırmışsınızdır. Tek çözüm olduğunda her zaman mantıklı bir sonraki adım vardır. Riskli bir şey denemeden önce aday notlarınızı yeniden kontrol edin.
Teklik de bir araçtır. İleri seviye oyuncular, bulmacanın tek çözümü olduğu bilgisini yukarıdaki 3-8 / 8-3 dikdörtgeni gibi desenleri elemek için kullanır. “Benzersiz dikdörtgen” (unique rectangle) tekniğinin temelinde bu fikir yatar.

Bunları uygulamak için online sudoku sayfamızda kendi seviyenizde bir bulmaca açın ya da yazdırılabilir sudoku sayfamızdan birkaç tane basıp kalemle çözün. Her birinde gereken en zor adımın ne olduğuna dikkat edin.

Kaynaklar

Gary McGuire, Bastian Tugemann, Gilles Civario: There Is No 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem via Hitting Set Enumeration, Experimental Mathematics 23(2), 2014, s. 190–217.
Aynı makalenin ücretsiz ön baskısı: arXiv:1201.0749 (tablo sayıları, Royle’un 49.151 bulmacalık listesi ve hesaplama ayrıntıları dahil).
Bertram Felgenhauer, Frazer Jarvis: Mathematics of Sudoku I, Mathematical Spectrum 39(1), 2006. Yöntemin özeti: Cornell Üniversitesi, “Counting Sudoku solutions”.
Ed Russell, Frazer Jarvis: Mathematics of Sudoku II, Mathematical Spectrum 39(2), 2007. Genel bakış: Mathematics of Sudoku (Wikipedia).
María Ercsey-Ravasz, Zoltán Toroczkai: The Chaos Within Sudoku, Scientific Reports 2, 725, 2012.
Peter Norvig: Solving Every Sudoku Puzzle.
Nikoli: Sudoku (bulmacanın tarihi) ve Why hand made?
Sudoku (Wikipedia): tarihçe, Howard Garns ve Dell’in Number Place bulmacası.

İyi Bir Sudoku Nasıl Yapılır? 17 İpucu, Tek Çözüm ve Gerçek Zorluk