İlginç Sorular ve Bulmacalar

Sekiz Vezir Bulmacası Aracılığı İle 1 Milyon Dolar Kazanabilirsiniz!

Satranç oynamayı sever misiniz? O zaman sekiz vezir bulmacası hakkında bir biçimde bilginiz vardır. Duymadıysanız klasik bir satranç bulmacası ile sizi tanıştıralım. Bu sorunun adı yabancı kaynaklarda Eight Queens Puzzle Türkçede Sekiz Vezir Bulmacası olarak biliniyor. İlk olarak 1848 yılında gündeme gelen soru şu şekilde: 8×8 bir satranç tahtasının üzerine 8 adet veziri öyle yerleştireceksiniz ki, iki vezirden biri diğerini doğrudan tehdit etmeyecek. Bulmaca, başka bir deyişle, iki vezirin aynı satırı, sütunu veya köşegeni paylaşmamasını gerektiriyor.

Satrancın kurallarını biliyorsanız vezirin satranç tahtası üzerinde en güçlü taş olduğunu biliyorsunuzdur. Zira her sınırsız hareket özgürlüğüne sahiptir. Bulmacanın doksan iki farklı çözümü vardır, ancak döndürmeler ve yansımalar hesaba katılırsa, 12 benzersiz çözüm ortaya çıkar.

Sekiz Vezir Bulmacası Çözümü

Sekiz Vezir Bulmacası olası çözümlerinden bir tanesi

Vezirlerin konumlarını {k1, k2, … k8} biçiminde gösterirsek genel çözüm şu şekilde olur. Bir vezir ilk sütunun k1’inci karesinde, diğeri ikinci sütunun k2’nci karesinde vb. olacaktır. On iki çözüm artık karşılık gelen sayılarla temsil edilebilir; örneğin, 41582736’daki sayısındaki rakamların her biri, soldan sağa sütunlarda alttan kn konumunu temsil eder. Yani “4”, birinci sütunun altından dördüncü konumdaki bir vezir anlamına gelir; “1” ikinci sütunda en alt konumdaki vezir anlamına gelir; “5” üçüncü sütunun en altından beşinci pozisyondaki veziri temsil eder ve bu böyle devam eder. Bu durumda 12 olası çözüm aşağıdaki gibi olur.

Karl Friedrich Gauss, 1859’da bu bulmacayla ilgilenmeye başladı ve 72 çözüm olduğu sonucuna vardı. Bulmacayı çözmek için kullandığı deneme-yanılma yönteminden memnun olmayınca da soruyu bir aritmetik problemine dönüştürdü.

Gauss’un Çözümü

Bunu nasıl başardığını görmek için yukarıdaki 41582736 sayısını ele alalım. Aslında uyguladığı yöntem Gauss’un hayat hikayesini bilenlere tanıdık gelecektir. Önce sayıyı yazdı daha sonra sayıdaki her rakamın altına kaçıncı sütunda bulunduğunu yazdı ve topladı.

Sonra da bir ters çevirme hilesi yaparak yeni bir toplam elde etti.

Her bir sütun için çıkan sonuçların farklı olup olmadığını kontrol etti. Birbiri ile aynı çıksaydı o dizilim sekiz vezir bulmacasının çözümü olamayacaktı. Ancak birbirinden farklı çıkanlar çözüm olabilirdi. Örneğimizde gördüğünüz gibi her bir sütunun sonucu birbirinden farklı ve bu bulmacanın çözümlerinden birisidir.

Ödül Bu Sorunun Neresinde?

Görünüşte basit olan bu bulmaca, genellemede teorik bir zorluk ortaya çıkarır ve çözülürse önemli teorik sonuçlar üretebilir. Aynı koşullarda, 20 adet veziri 20×20’lik bir tahta üzerine, ya da 100 adet veziri 100 x 100’lük bir tahta üzerine yerleştirmek durumunda kaldınız diyelim. Bu sorunun “n-Queen’s Puzzle” olarak adlandırılan bu biçimidir. Ve n (n=sıra, sütun ve vezir sayısı) büyüdükçe işler gerçekten karışmakta ve soruyu çözmekte son derece güçlü bilgisayarlar bile aciz kalmaktadır. Ancak bu yine de çözülebilir durumdadır. O zaman bir şart daha ekleyelim. n-Queens Completion Problem, olarak bilinen son versiyonunda bazı vezirler önceden yerleştirilmiş durumda. Ve bunları hiç hareket ettirmeden diğerlerinin yerleştirilmesi gerekiyor.

Ve bu soruyu çözebilecek bir bilgisayar programı yazılırsa, bu çözüm bizi günlük hayatımızı etkileyen başka soruların çözümüne götürebilecek. Çünkü bu soru aslında bir P – NP sorusu. ( Daha dazla bilgi için göz atın: P ile NP Birbirine Eşit midir? Bu Ne Demektir?). Bu da soruyu çözebilecek herhangi bir algoritmanın, NP sınıfındaki herhangi bir soruyu çözmek için dolaylı olarak kullanılabileceği anlamına geliyor. Bu arada hatırlatalım bu sorunun “n-Queen’s Puzzle” olan ilk versiyonu bir P=NP sorusu olarak kabul edilmiyor.

Ödül kazanmak için yapılması gereken herhangi bir algoritmanın bulmacayı makul bir sürede çözemeyeceğini kanıtlamak veya hızlı bir şekilde çözebilecek bir algoritma geliştirmek olacak. P=NP bir Milenyum Ödüllü bulmaca olduğu için bu soruyu çözebilen, o soruyu da çözmüş sayılacak ve 1 milyon dolarlık bir ödül kazanacak.

Göz Atmak İsterseniz

Kaynak:

Matematiksel

Sibel Çağlar

7 yıl Kadıköy Anadolu Lisesinin devamında lisans eğitimimi Marmara Üniversitesi İng. Matematik öğretmenliği üzerine tamamladım. Devamında 20 yıl çeşitli özel eğitim kurumlarında matematik öğretmenliği ve eğitim koordinatörlüğü yaptım. 2015 yılında matematiksel.org web sitesini kurdum. Amacım bilime ilgiyi arttırmak, bilimin özellikle matematiğin zihin açıcı yönünü açığa koymaktı. Yolumuz daha uzun ve zorlu ancak en azından deniyoruz.

Bir cevap yazın

E-posta hesabınız yayımlanmayacak.