Latin Kareleri: Sudoku'nun Arkasındaki Matematik

"Her satır, her sütun, her sayı bir kez"

Sudoku tutkununun bildiği kural: 9×9 ızgara, her satır ve her sütun 1-9 sayılarını tam bir kez içerir. Üstelik 3×3 alt-kutular da öyle.

Eğer 3×3 alt-kutu kuralını kaldırırsak, geriye kalan yapıya matematikçiler Latin karesi diyor.

Resmi tanım

Bir Latin karesi $n \times n$ bir ızgaradır, $n$ farklı sembolden oluşur, her sembol her satırda ve her sütunda tam bir kez geçer.

Sembolleri 1, 2, ..., $n$ veya A, B, C, ... olarak alabiliriz.

3×3 Latin karesi örneği:

1	2	3
2	3	1
3	1	2

Her satır: 1, 2, 3'ü içerir. Her sütun da.

Tarihçe: Leonhard Euler (1770s)

Adı "Latin karesi" olarak yerleşti çünkü Leonhard Euler 1770'lerde bu yapıları incelerken Latin harflerini sembol olarak kullandı (Yunan harflerinden farklı olarak).

Euler şu soruyu sordu:

"Bir piknik tertiplemek istiyorum. 36 subay, 6 farklı rütbeden ve 6 farklı alaydan. Bu subayları 6×6 ızgarada öyle dizmeliyim ki her satır ve her sütun her rütbeden bir tane ve her alaydan bir tane içersin."

Bu, iki ortogonal Latin karesi problemidir. Euler bunun mümkün olmadığını tahmin etti.

110 yıl sonra Gaston Tarry 1900'de el ile kontrol ederek kanıtladı: 6×6 ortogonal Latin kare çifti gerçekten mevcut değildir.

Ama Euler'in daha geniş tahmini ($n \equiv 2 \mod 4$ için imkânsız) yanlış çıktı: 1960'da Bose, Shrikhande, Parker 10'dan büyük tüm $n$ değerleri için ortogonal Latin kare çifti bulunabildiğini gösterdi (6 dışında).

Sudoku'nun matematiği

Sudoku özel bir Latin karedir: 9×9 + ek 3×3 kutu kısıtı. Bu ekstra kısıt yüzünden sudoku Latin karelerden daha az çözüm'e sahip.

• Tam 9×9 Latin karelerinin sayısı: $\sim 5.5 \times 10^{27}$
• Tam 9×9 sudoku çözümlerinin sayısı: 6,670,903,752,021,072,936,960 $\sim 6.7 \times 10^{21}$

Bu, küçük bir oran ama hâlâ inanılmaz büyük bir sayı'dır.

Sudoku'yu çözmek veya kontrol etmek kolaydır ama sıfırdan oluşturmak NP-tam bir problemdir.

Ortogonal Latin kareleri

İki Latin karesi ortogonal ise, üst üste koyup her hücreyi (sembol1, sembol2) olarak yazınca, tüm sıralı çiftler tam bir kez geçer.

Örnek (3×3):

Kare A: 1, 2, 3 / 2, 3, 1 / 3, 1, 2
Kare B: 1, 2, 3 / 3, 1, 2 / 2, 3, 1

Üst üste:

• (1,1), (2,2), (3,3)
• (2,3), (3,1), (1,2)
• (3,2), (1,3), (2,1)

Tüm 9 sıralı çift mevcut. Ortogonal!

$n \times n$ için maksimum ortogonal Latin kare sayısı: $n - 1$ (eğer $n$ asal kuvvetiyse).

Pratik uygulamalar

1) Deneysel tasarım (Design of Experiments)

Ronald Fisher Latin karelerini tarımsal denemelerde kullandı. 5 farklı gübre tipini 5 farklı tarlada test etmek istersiniz; ama tarlalar kuzey-güney ve doğu-batı farklı toprak özelliklerine sahip. Latin kare tasarımı iki yönlü kontrolü sağlar.

Modern tıbbi araştırmalar, endüstriyel deneyler Latin kare tasarımları kullanır.

2) Şifreleme

One-Time Pad ve bazı modern şifreleme yöntemleri Latin kare yapılarını kullanır.

3) Hata düzeltme kodları

Reed-Solomon ve diğer kodların matematik altyapısında Latin kare benzeri yapılar.

4) Spor karşılaşmaları (Round-robin)

5 takım birbiriyle oynayacak. Her hafta 2 maç. Kim kiminle oynayacak? Latin kare tasarımı çakışmasız ve eşit dağıtım sağlar.

5) Anket tasarımı

Soru sırasının yanıtları etkilememesi için sorular rastgele sıralanır. Latin kare ile sistematik rotasyon.

Sudoku'nun matematiksel çözümü

Bir sudoku'yu çözmek bir kısıt tatmin problemi (CSP). Çözüm yöntemleri:

1) Backtracking

Boş hücrelere değer atayıp çelişki çıkarsa geri dönmek. Klasik yöntem.

2) Dancing Links (Knuth)

Donald Knuth'un "Algoritma X" ve Dancing Links veri yapısı sudoku'yu çok hızlı çözer.

3) SAT çözücüler

Sudoku'yu Boolean tatmin problemine dönüştürüp modern SAT solver'ları kullanmak.

4) Sinir ağları

Modern AI yöntemleri sudoku çözmek için kullanılır.

Bir sudoku'nun tek çözümlü olması için en az 17 başlangıç ipucu olması gerekir (2012'de brute force ile kanıtlandı).

Daha derin: kombinatoryal tasarımlar

Latin kareleri, kombinatoryal tasarımlar (combinatorial designs) adlı geniş matematik alanının bir parçasıdır. Diğer örnekler:

• Steiner sistemleri: belirli yapısal noktalardan oluşan ızgaralar.
• Block designs: deneysel tasarımlarda blok dizilimi.
• Hadamard matrisleri: ortogonal yapılar.

Bu yapılar sinyal işleme, kodlama teorisi, kriptografi gibi alanlarda kullanılır.

"Düzenli Eğlence"

Sudoku'nun popülerleşmesi 2004 sonrasındaydı (Japon yayıncı Nikoli modern formunu geliştirdi; The Times 2004'te basmaya başladı). Ama matematiksel altyapısı 250 yıldır var.

Bir kalemden bir sudoku oynarken, Euler'in 1770'lerde başlattığı bir matematik geleneğini sürdürüyorsunuz. Latin kareleri matematiksel estetik ve deneysel verimlilik birleşiminin güzel bir örneği.

Bir 9×9 ızgaranın arkasında 250 yıllık matematik hikâyesi var.