Sudokunun Matematik ile İlişkisi: Çözüm Algoritmaları Nelerdir?

Oyun tabanlı öğrenme öğrenciler arasında motivasyonda artış; eleştirel düşünme, anlamlandırma gibi bilişsel becerilerin gelişimine aynı zamanda takım oyuncusu olabilme, oyunda girişkenlik gibi davranışsal becerilerin gelişiminekatkı sağlayarak öğrenmeyi kolaylaştırmaktadır.

Sudoku gibi basit görünen ancak karmaşık çözüm algoritmalarına sahip oyunlar; farklı yaşlarda birçok kişinin kodlama, optimizasyon, programlama gibi konuları anlamalarına yardımcı olurken bu konularda uygulama imkanı da sunmaktadır. Bu yönüyle oyun, bilim ve eğitim dünyasının birleştiği nokta olarak görülebilir. Biz yazımızda Sudokunun, matematikte görünenden çok daha derin köklere ve dallara sahip olduğunu detaylandıracağız.

Sudoku Etimolojisi ve Tarihçesi

Bugün bildiğimiz ve oynadığımız Sudokunun tarihi 1970'lerin sonlarına dayansa da köklerini çok daha eskilere götürmek mümkündür. Bu bulmaca oyununun temeli ve bir dereceye kadar öncülü, 18. yüzyılda var olan ve daha sonra bahsedeceğimiz "Latin kareleri" adlı matematiksel bir kavramdır.

Sudoku Conquest

Modern Sudoku şekillenirken Howard Garns adlı emekli bir Amerikalı mimar, 1979'da Dell Pencil Puzzles and World Game dergileri için "Sayı Yeri" anlamına gelen "Number Place" adlı bir bulmaca yarattı. Mekaniği öncüllerine benziyordu ancak sayfada daha fazla eksik sayı mı yoksa üzerinde çalışılacak daha az sayı mı olduğunu bilmek için yeterli dayanak yoktu. Bu dergiler, modern Sudokunun oluşumunda önemli bir rol oynayacaktı.

Maki Kaji adında bir Japon, bir dergide "Number Place" adlı bulmacayı gördü ve bulmacayı kendi başına mükemmelleştirdi. Kaji, yeni bulduğu bulmacayı geliştirdikten sonra en sevdiği eğlence olan at yarışlarını izlemeye gidip bu arada oyununa bir isim buldu: "Suuji wa dokushin ni kagiru". "Sayılar tek olmalı" anlamına gelen bu ismi verdikten kısa süre sonra arkadaşlarıyla at yarışlarında kazandıkları parayla "Nikoli" isminde bir yayınevi kurdular. Nikoli yönetiminde, ilk bulmacalarını kendi dergilerinde yayınlamaya başladılar. Ancak Kaji'nin iş arkadaşları, yeni oyunun adının çok uzun olduğunu söyleyince Kaji de adını 数独; 数 (Tür: "sū"), 独 (Tür: "doku"), yani Sudoku olarak kısaltıp bundan sonra Sudoku olarak kullanmaya devam etti.

İlk toplu yazdırılabilir Sudoku bulmacası 1984'te yayınlandı ve ülke çapında hızla popülerlik kazandı. Kaji ayrıca bulmacayı, çocuklar ve çok fazla kafa yormak zorunda kalmadan bir şeylerin tadını çıkarmak isteyenler için geliştirdiğini de belirtti. Günlük Sudoku bulmacaları her yaş grubunda inanılmaz ilgi gördü. Ancak Sudoku'nun uluslararası düzeyde tanınıp dünya çapında oynanması on yıldan fazla zaman aldı.

PuzzCulture

Sudokunun uluslararası yolculuğu, 2000'lerin başında İngiliz gazetelerinin bulmacayı yayınlamasıyla başladı. Eski ve çok ünlü bir gazete olan The Times, yayınlarının bir parçası olarak Sudokunun dünyanın batı kesiminde popülerleşmesinde önemli bir rol oynadı. Bulmacanın zorluk derecesini kolaydan zora doğru sıralayan bir derecelendirme sistemi getirerek Sudokunun daha geniş bir kitleye hitap etmesini sağladı.

Sudoku, kısa sürede küresel bir fenomen haline geldi ve dünya çapında gazetelerde, kitaplarda ve Nikoli gibi özel bulmaca dergilerinde yer aldı. Teknolojideki gelişmeler, özellikle de internetin yaygınlaşması, Sudoku'nun popülaritesini daha da arttırdı. Bulmaca, kısa sürede televizyon ekranlarında, video oyunlarında ve PDA'lar gibi elektronik taşınabilir cihazlarda yer almaya başladı. 2006 yılında Dünya Sudoku Şampiyonası ile birlikte zorlu Sudoku bulmacaları için Sudoku yarışmaları ve turnuvaları tüm dünyada yaygınlaştı. Bulmacanın cazibesi, erişilebilirliğinde yatıyordu; yaş veya beceri seviyesi ne olursa olsun herkes, sayma ve okuma becerileri olduğu sürece, Sudoku çözerek vakit geçirebilirdi.^[1]

Latin Kareleri

Latin Karesi, her elemanı 1'den $n$'ye kadar sayılar olan $n$ x $n$ bir ızgaradır. Böylece her eleman, her satır ve sütunda bir kez görülür. Sudoku ızgaraları, buna bir örnektir. Ancak Sudokuda ızgara içinde bloklar da bulunduğu için özel bir alt kümedirler.

Farklı kombinasyonlar denemenin yollarını araştırmak istiyorsanız Latin Kareleri oldukça faydalıdır. Kaç tane Latin Karesi olduğunu bulmak için örneğin 3. dereceden Latin Karelerine bakarsak en üst satırın 1, 2, 3 olduğunu varsayabiliriz. Bu altta yatan yapıyı etkilemez ve tüm olasılıkları daha sonra yeniden oluşturabiliriz. Burada en üst satır 1, 2, 3 olduğundan 2. satırın ilk hücresi 2 veya 3 olmalıdır. Sonuç olarak bu varsayımda olası iki farklı kare mevcuttur.

1, 2 ve 3 sayılarının altı olası şekilde atanacağı göz önüne alındığında 3. dereceden Latin Kareleri'nin sayısı 12'dir. Sayılar dereceler arttıkça hızla artmaktadır: 4. dereceden Latin Karesi sayısı 576 iken 5. dereceden sayısı 161280'dir.

Evrim Ağacı'ndan Mesaj

Neden Desteğe İhtiyacımız Var?

Aslında maddi destek istememizin nedeni çok basit: Çünkü Evrim Ağacı, bizim tek mesleğimiz, tek gelir kaynağımız. Birçoklarının aksine bizler, sosyal medyada gördüğünüz makale ve videolarımızı hobi olarak, mesleğimizden arta kalan zamanlarda yapmıyoruz. Dolayısıyla bu işi sürdürebilmek için gelir elde etmemiz gerekiyor.

Bunda elbette ki hiçbir sakınca yok; kimin, ne şartlar altında yayın yapmayı seçtiği büyük oranda bir tercih meselesi. Ne var ki biz, eğer ana mesleklerimizi icra edecek olursak (yani kendi mesleğimiz doğrultusunda bir iş sahibi olursak) Evrim Ağacı'na zaman ayıramayacağımızı, ayakta tutamayacağımızı biliyoruz. Çünkü az sonra detaylarını vereceğimiz üzere, Evrim Ağacı sosyal medyada denk geldiğiniz makale ve videolardan çok daha büyük, kapsamlı ve aşırı zaman alan bir bilim platformu projesi. Bu nedenle bizler, meslek olarak Evrim Ağacı'nı seçtik.

Eğer hem Evrim Ağacı'ndan hayatımızı idame ettirecek, mesleklerimizi bırakmayı en azından kısmen meşrulaştıracak ve mantıklı kılacak kadar bir gelir kaynağı elde edemezsek, mecburen Evrim Ağacı'nı bırakıp, kendi mesleklerimize döneceğiz. Ama bunu istemiyoruz ve bu nedenle didiniyoruz.

Destek Ol

Birkaç yüzyıl önce Fransa'da dolaşan ve biraz Latin Karesi'ni andıran bir kart bulmacası bulunmaktaydı. Amaç; bir deste iskambil kağıdındaki her şekildeki (kupa, karo, maça, sinek) en yüksek dört kartı (vale, kız, papaz, as) almak ve bunları 4x4 kare düzeninde öyle bir düzenlemekti ki her satır ve sütunda tam olarak bir vale, bir kız, bir papaz ve bir as ile bir kupa, bir karo, bir sinek ve bir maça bulunsun. Burada olan şeyin kart değerlerinin bir Latin Karesi oluşturması olduğunu görebiliriz ancak bu herhangi bir Latin Karesi çifti değildir. Bu bulmacanın birçok çözümü vardır.

18. yüzyılda daha zorlu bir problem ortaya atılmıştır: 36 Subay Problemi! Euler, 36 Subay Problemi'nin herhangi bir çözümünün, iki kümeden olası her çift kombinasyonunun tam olarak bir kez oluşacak şekilde üst üste bindirilmiş iki Latin Karesi içermesi gerektiğini bulmuştur. Bu yapılara Graeko-Latin Kareleri adını vermiştir. Çünkü bir kümenin elemanlarını Yunan harfleriyle diğerini ise Latin harfleriyle adlandırmıştır. Günümüzde bu çiftler Ortogonal Latin Kareleri olarak kullanılmaktadır.^[4]

$nxn$

Sihirli Kareler

Sihirli kareler en temel anlamda; satır, sütun ve köşegenlerdeki hücrelerde bulunan sayıların toplamının aynı olmasıdır.

Math World Wolfram

Herhangi bir özelliğe sahip en eski sayı karesi, Lo Shu karesidir. Çin efsanesine göre büyük bir sel yaşanmış, insanlar nehir tanrılarını yatıştırmak için kurbanlar sunduklarında nehirden kabuğunda doğal olmayan bir desen bulunan ve kabuktaki dairesel noktaların bir ızgara şeklinde düzenlendiği sihirli bir kaplumbağa çıkmıştır.^[3]

Wikimedia Commons

Sihirli kareler için bilinen en eski örneklerden olan bu diyagramda satır, sütun ve köşegenlerdeki noktaların toplamı hep aynı sihirli sayıdır: 15!

Sonraki yıllar boyunca sihirli kareler Hindistan ve Orta Doğu'da da ortaya çıkmış, ardından Afrika ve Avrupa'ya yayılmıştır. Hint yazar Varahamihira'nın MS 6. yüzyılda yazdığı bir kitapta sihirli kare, parfüm yapımında yardımcı olarak verilmiştir. Satır, sütun ve köşegenlerin toplamı 18'dir ve dört malzeme seçmeniz ve ardından her bir malzemeden ne kadar kullanılacağını belirlemek için satırlardan, sütunlardan ve köşegenlerden herhangi birini takip etmeniz gerekir; sonuç olarak tüm durumlarda toplam parfüm miktarı aynı olur.

Batı sanatındaki en ünlü sihirli kare muhtemelen Albrecht Dürer'in "Melencolia" gravüründe gösterilmiştir. Birçok sembolizm ögesi barındıran bu eserde melankoli Satürn gezegeni ve geometriyle ilişkilendirilmiştir. Antik gelenekte en yakın gök cisimleri farklı bir düzendeki sihirli kareyle ilişkilendirilirdi. 4. dereceden sihirli karelerle ilişkilendirilen gezegen Jüpiterdir. Bu klasik sihirli kare, matematikçi Luca Pacioli tarafından 1501 yılına ait bir kitapta okuyucuya sunulmuştur.^[4]

Daily Art Magazine

Bir Sudoku ızgarası, yarı-sihirli kare olarak adlandırılır; satır ve sütun toplamları aynıdır, ancak köşegenler bu toplama sahip olmak zorunda değildir. Latin kareleri gibi sihirli kareler de matematik açısından incelenebilecek derin bir konu olduğu için başka bir yazıda ele almak üzere esas konumuza geri dönüyoruz.

Sudoku Nedir?

Sudoku'nun standart versiyonu; 81 hücre, 9x9 kare, bir ızgaradan oluşur. Izgara, 9 adet 3x3'lük bloğa bölünmüştür. 81 hücrenin bir kısmı {1,2,3,4,5,6,7,8,9} kümesindeki sayılarla doldurulmuştur. Bu doldurulmuş hücrelere "verilenler" denir. Amaç, 9 rakamı da kullanarak tüm ızgarayı doldurmak ve her satır, her sütun ve her blokta her sayının tam olarak bir kez bulunmasını sağlamaktır. Satır, sütun ve blok üzerindeki bu kısıtlamaya "tek kural" denilmektedir. Bu şartlardaki Sudokuya, 3. dereceden Sudoku denir. Bu durumda $n$dereceden bir Sudoku, $n^2$x $n^2$ hücreden oluşan bir ızgaradır ve $n$ x $n$ boyutunda $n^2$ bloktan oluşur. Izgarayı doldurmak için kullanılan sayılar {1,2,...,$n^2$} kümesindedir ve "tek kural"ı her zaman geçerlidir.^[2]

Pi Math Cornell

Standart Sudoku'nun çözüm aşamalarını kolay bir örnek üzerinden göstermek için aşağıdaki görsel üzerinden ilerleyebiliriz.

1. aşamadaki bir ızgaraya sahip olduğumuzu varsayalım. $a$'yı içeren satır diğer tüm rakamları içerdiği için $a=1$ olmalıdır. $b$'yi içeren sütun 3 hariç tüm rakamları içerdiği için $b=3$ olmalıdır. Son olarak $a,b$ ve $c$'yi içeren blok 6 hariç tüm rakamları içerdiği için $c=6$ olmalıdır.

2. aşama için gölgelendirilmiş üç bloktan oluşan yatay dilime bakalım. Bu gölgelendirilmiş alanı bir dilim olarak düşünürsek tamamlanmış bir dilimde her rakam tam olarak üç kez görülmelidir: üç satırın her birinde bir kez ve üç bloğun her birinde bir kez. Örneğin, 6 rakamı ilk iki blokta bulunurken 3. blokta yoktur ve dilimin 2. ve 3. satırında bulunduğu için 3. bloğun 1. satırında yer almalıdır. Bu durumda $d=6$ yazılabilir.

Agora Bilim Pazarı

On İki Yıllık Esaret

Solomon Northup, ihanete uğrayıp köle olarak satılana kadar New York’ta özgür bir adamdır. Karısından ve çocuklarından koparılan Solomon, özgürlüğüne kavuşup onlara dönmeyi hayal etmektedir. Ancak sevdikleriyle iletişim kurmanın ya da özgür bir adam olduğunu kanıtlamanın hiçbir yolu olmayan Solomon, zincirlerinden kurtulabilecek midir?

Devamını Göster

₺120.00

Satın Al Tüm Ürünler

3. aşamada gölgelendirilmiş dikey dilime bakalım. En üstteki blokta 3 veya 9'un yer alabileceği hücreleri görmekteyiz. Bu durumda bu hücrelerden birinde 3, diğerinde 9 olmalıdır. Ancak hangi hücreye hangisini yazacağımızı henüz bilmiyoruz. Bu hücreler için yaptığımız bu kısıtlama, başka hücreler ile ilgili çıkarım yapmamıza yardımcı olabilir. $e$ hücresi için tek bir ihtimal söz konusudur. Çünkü dilimin en üst bloğunda 3 rakamı 2. satırda olamaz ve bu durumda tek seçenek $e=3$'tür.

Çözüm Stratejileri Nelerdir?

Sudoku günümüzde, ilkokul düzeyinde dahi uygulanabilir olduğundan oyunun tamamen aritmetik beceriye bağlı olmadığı söylenebilir. Bulmacada sadece 1'den 9'a kadar olan rakamlar haricinde, herhangi 9 sembol de bulmacayı oluşturmak için yeterli olacaktır. Bu noktada Sudoku çözmede mantıksal çıkarım yapmak öne çıkmaktadır.

Bir Sudoku bulmacasını çözmenin en temel stratejisi; öncelikle her boş hücreye, "tek kural"a aykırı olmayacak şekilde olası girdileri yazmaktır. Bir hücrede yalnız bir olası girdi varsa bu, doldurmanız gereken zorunlu bir hücredir.

Başka bir yol da bir satır, sütun veya blok seçmektir. Bir sayı belirlenerek satır, sütun veya bloktaki "tek kural"ı ihlal etmeden sayının yerleştirilebileceği tüm hücreler not edilir.

Tabi ki bu stratejiler Sudoku tablosunu tamamen doldurmak için yeterli değildir (en azından başlangıç seviye olmayanlarda). İlerleme kaydetmek için genellikle daha karmaşık analiz yöntemlerine ihtiyaç vardır ve bazen bir tahminde bulunup ilerlemeniz tahmin bir çelişkiye yol açarsa geri dönmemiz gerekir.

Daha karmaşık bir strateji, bir satır, sütun veya blok içindeki hücre çiftlerine veya üçlülerine bakmaktır. Bir hücre çiftinin sadece iki giriş seçeneğine sahip olduğunu ancak hangi rakamın nereye geleceğini bilmiyorsak da yine de elde edebileceğimiz bir sonuç, bu sayı çiftinin komşulukta herhangi bir yere gelemeyeceğidir. Bu diğer olasılıkların sayısını azaltacaktır. Eğer zorunlu giriş yoksa en az girdi olasılığına sahip hücreyi seçerek bahsedilen stratejilere uygun rakam yazılır ve devam edilir. Bir çelişkiyle karşılaşıldığında (bir satırda, bir sütunda veya bir blokta tekrarlanan rakam) adımlar geri alınır ve çelişki ortadan kalkana kadar işlemler ilerletilir. Bu bir bakıma deneme yanılma stratejisi olarak adlandırılabilir.

9x9'luk Kaç Sudoku Bulmacası Yazılabilir?

9x9 ızgarada kaç Sudoku çözümü vardır? Bu soruyu sormamızın sebebi, verilenlere sahip bir Sudoku ızgarasında tek çözümün olmasıdır. Felgenhauer ve Frazer Jarvis, 2006 yılının başında bunu hesaplamak için bir yöntem kullanmıştır. Bu yönteme göre üç blok satırına "ızgaranın bantları", üç blok sütununa ise "yığınlar" denilmektedir. $i$. satır ve $j$. sütundaki bir hücre $(i,j)$ pozisyonu olarak tanımlanır.

Yazılacak tüm farklı Sudoku ızgaralarının sayısına $N$ diyelim. Öncelikle ızgara blokları şu şekilde etiketlendirilir:

Bu noktada blok bazında ilerlersek B1 bloğunu geçerli bir şekilde doldurmanın kaç yolu vardır? B1 bloğunu 1'den 9'a dokuz farklı rakam ile dolduracağımızdan B1 bloğunun ilk hücresi için 9 seçenek vardır. İkinci hücre için 8 seçenek kalır ve böyle ilerler. Yani temelde 9 farklı rakamın/sembolün permütasyon sayısı hesaplanır: 9 farklı sembol, 9 hücreye kaç farklı şekilde yerleştirilebilir? O halde B1 bloğunu doldurmanın $9!$ yolu vardır. Yapabileceğimiz ilk basitleştirici varsayım, B1 bloğunun gösterildiği gibi 1,2,...,9 sırasıyla doldurulmasıdır:

B1 bloğunun kaç geçerli Sudoku tablosu oluşturabileceğini $N_1$olarak adlandıralım. Toplam geçerli Sudoku ızgarası sayısı $N$ olduğundan $N_1$$=N/9!$ yazılabilir.

Şimdi B2 ve B3 bloklarının ilk satırlarının doldurma yollarını ele alalım. B1 bloğunun ilk satırında 1,2 ve 3 sayıları bulunduğundan bu sayılar satırın geri kalanında yer alamaz. Bu nedenle B2 ve B3 bloklarının ilk satırlarında 4, 5, 6, 7, 8 ve 9 rakamları kullanılabilir. B2 ve B3 bloklarındaki ilk satırların doldurulmasındaki tüm olası yollar listelenir. Bunun 10 yolu vardır ve B2 bloğu ile B3 bloğunun yer değiştirebileceği de düşünülünce mümkün olan 20 yol vardır. Bu 20 olasılık göz önüne alındığında ilk bandı nasıl doldurabileceğimiz bulunabilir.

Saf üst sıra {1,2,3} (B1'de); {4,5,6} (B2'de); {7,8,9} (B3'te) olmak üzere ilk bandı tamamlamanın $(3!{)}^6$ yolu olduğu ortaya çıkar. Burada B2 ve B3'ün ikinci sırasına {1,2,3} ve {7,8,9}; aynı şekilde B2 ve B3'ün üçüncü sırasına {1,2,3} ve {4,5,6} zorunlu olarak yerleştirilir ve ardından tüm konfigürasyonları elde etmek için yeniden sıralamalar yapılır.

Karışık üst sıraların durumu daha karmaşıktır. Verilen örnekteki üst sıra ele alındığında buradaki $a,b$ ve $c$; herhangi bir sıradaki 1,2 ve 3 rakamlarıdır:

Izgaraya göre $a$ seçildikten sonra $b$ ve $c$ için kalan iki sayı herhangi bir şekilde seçilebilir çünkü aynı satırdadırlar. $a$ için üç farklı seçenek olduğundan B2 ve B3 bloklarının her birindeki üç basamak, çeşitli geçerli ilk bantlar oluşturacak şekilde yer değiştirebildiğinden bu durumda toplam konfigürasyon sayısı $3$ x $(3!{)}^6$olacaktır. Benzer şekilde ilk satırların kalan 17 durumunun her birini de aynı sayıyı elde edecek şekilde hesaplayabiliriz. Buradan standart B1 bloğu için olası ilk bantların sayısı bulunur. Saf üst sıralardan ilk bant tamamlamalarının sayısı ($2$ x $(3!{)}^6$) ile karışık üst sıralardan ilk bant tamamlamalarının sayısı ($18$ x $3$ x $(3!{)}^6$) toplanır, 2612736 olası durum elde edilir.

Felgenhauer ve Jarvis, tüm bu ele alınan olası durumlar ve son hesaplamaları yapmak için bir bilgisayar programı yazdılar. Standart B1 bloğu için $N_1$ sayısını hesapladılar ve başta da belirttiğimiz gibi $N$ 'i bulmak için $9!$ ile çarptılar.^[2]

Sonuç:

$N=6670903752021072936960$ yani yaklaşık olarak $6,671$x $10^{21}$ bulundu.

Sudoku ve Çizge Teorisi

Temeli 1736 yılında Leonhard Euler tarafından atılan Çizge Teorisi'nde çizge, düğümler ve bu düğümleri birbirine bağlayan kenarlardan oluşan bir ağ yapısı olarak tanımlanabilir. Çizge Teorisi, gerçek dünyadaki çeşitli problemleri düğümler ve kenarlardan oluşan grafikler olarak temsil ederek anlama ve çözme konusunda güçlü bir çerçeve sunar.

Wikimedia Commons

Köşe kümesi {1,2,3,4} ve kenar kümesi {1-2, 1-3, 1-4, 2-4, 3-4} olan bu basit grafiği örnek olarak alalım. Çizge teorisi bağlamında graf renklendirme önemli bir kavramdır. Bu, bir grafın köşelerine bitişik iki köşenin aynı renge sahip olmaması koşuluyla farklı renkler atamayı içerir. Bunun önemli bir adımı, grafın köşelerini renklendirmek için gereken minimum renk sayısını belirlemektir; bu sayıya "kromatik sayı" denir. Bu örnekte kromatik sayı 3'tür. Yani 3 renge ihtiyacımız vardır; bunlar mavi, kırmızı ve yeşil olsun. O halde yukarıdaki grafik üzerinde düşünürsek 1 numaralı düğüm mavi olmak üzere 2 numaralı düğüme mavi rengi atayamayız. Aynı şey 3 numaralı düğüm için de geçerlidir. Ancak 2 ve 3 numaralı düğümlere kırmızı renk atanabilir. Son olarak 4 numaralı düğüm kurala uygun şekilde yeşil renk olmalıdır.

Sudoku örneğinde ise amaç, bulmacanın kısıtlamalarını karşılayacak şekilde düğümlere 1'den 9'a kadar olan sayıları renk olarak atamaktır. Bu yaklaşım Sudoku ızgarasının doğal yapısını gösterir ve Sudoku bulmacalarını çözmek için çizge teorisinin prensiplerini uygular. Bu sayede de bulmacanın kombinatoryal yönlerine dair bilgi edinmemizi ve Sudokunun zorluklarıyla başa çıkmak için yeni bir yaklaşım sunmamızı sağlar.

Sudoku ızgarasının hücrelerini graftaki (çizge) düğümler, ortak satır sütun ve blokları da aralarındaki bağıntılar (kenarlar) olarak hayal ederek Sudokuyu bir köşe renklendirme problemine dönüştürebiliriz. Bu yolla Çizge Teorisi kullanarak Sudokuya çözüm üretilebilir.

Standart 9x9 bir Sudoku grafiği 81 köşeden oluşacak ve her köşe Sudoku tablosundaki bir hücreyi temsil edecektir. Grafik renklendirme yöntemiyle Sudoku çözmek için öncelikle bu köşeler arasındaki bağıntıları kurmamız gerekir. Her düğüme Sudoku ızgarasındaki konumunu temsil eden benzersiz bir pozisyon atarız; bu sayede hangi düğümlerin satır, sütun ve bloklara göre bağlanması gerektiğini belirleyebiliriz.

Öncelikle her düğümü aynı satırdaki diğer tüm düğümlere bağlıyoruz. Örneğin 14. düğümü aynı satırdaki diğer düğümlere bağlayalım.Bu işlem aynı satırdaki düğümler arasında kenarlar oluşturarak bir satırdaki düğümlerin ortak bir bağlantıyı paylaştığı bir grafik ortaya çıkarır. Benzer işlemler aynı sütundaki ve aynı bloktaki (3x3'lük bölge) tüm düğümleri birbirine bağlayarak da gerçekleştirilir.

Bu bağlantıları; yaptığımız gibi satırlar, sütunlar ve bloklar temelinde kurarak her düğümün aşağıdaki şekilde bağlandığı bir grafik oluşturuyoruz:

Tüm bu işlemleri, verilenleri olan bir Sudoku grafiğine entegre edelim ve Sudoku ızgarasında verilen 7 rakamını ele alalım. Öncelikle Sudoku ızgarasında verilen 7 rakamlarını grafikte temsil eden iki köşenin aynı renge sahip olmasını sağlamak istiyoruz ve bunun için 7 rakamına sahip bu iki köşe arasına bağlantılar kuruyoruz. Bu bağlantı, 7 rakamına sahip köşelerden birini diğer 7 rakamına sahip köşenin tüm komşularıyla bağlayarak kurulur:

Bu entegrasyonlar, sonraki aşamalarda fonksiyon olarak bilgisayar programları yardımıyla bizi istenen sonuca ulaştırır.^[5]

Sudoku Çözüm Algoritmaları

Sudoku çözümü için farklı algoritmalar kullanılabilir. Welsh-Powell Algoritması, temelde renklendirilecek bir sonraki köşeyi titizlikle seçmeye odaklanır. Bunun yanı sıra Karger's Algoritması'nda amaç, grafı iki parçaya ayıran en az kenar sayılı kesiti bulmaktır.

Welsh-Powell Algoritması (Açgözlü Algoritma)

Açgözlü boyama, renklendirilecek bir sonraki köşeyi dikkatlice seçmeye odaklanır. Bir köşe renklendirildikten sonra rengi asla değişmez. Bu kategorideki ünlü algoritmalardan biri olan Welsh-Powell Algoritması'nın çalışma prensibi şu şekildedir:

1. Her bir köşenin derecesini bulun (derece, o köşeye bağlı kenarların sayısıdır).
2. Köşeleri derecelerine göre azalan sırada sıralayın.
3. Listeyi inceleyin ve renkli köşelere bağlı olmayan her köşeyi aynı renkle boyayın.
4. Renklendirilmiş köşeleri listeden çıkarın ve tüm köşeler renklendirilene kadar işlemi tekrarlayın.

Karger's Algoritması

Yönlendirilmiş ve ağırlıksız bir graf verildiğinde grafı birbirinden ayıran en küçük kesim yani en az sayıda kenar bulunur. Bir örnek üzerinden gösterelim:

Karger's Algoritması adımları şu şekildedir:

1. Daraltılmış graftan başlayın.
2. Rastgele bir kenar seçin (u-v olsun), u ve v'yi tek bir köşeye birleştirerek daraltılmış grafı güncelleyin.
3. İki köşeyle temsil edilen kesiti döndürün.

Son durumda grafın iki köşesi kalır ve bu noktada durulur. Elde edilen grafın kenar sayısı Karger's Algoritması'nın ürettiği kesimdir.^[6]

Sudoku Çözümünde Algoritmaların Kullanımı

Sudoku bulmacası çözümlerinin daha pratik ve hızlı olabilmesi için birçok uygulama tasarlanmakta ve geliştirilmektedir. Çizge Teorisi'ne dayalı Welsh-Powell Algoritması ve Karger's Algoritması bu amacı destekleyen metodlardır.

Sudoku gibi basitten zora kategorilendirilebilecek, farklı yaşlara hitap eden bir bulmaca; matematikteki Çizge Teorisi ve bağlantılı olan algoritmaların yazılım ve programlamada kullanılmasıyla bir araya gelebilmektedir.