Yeni Bir Milenyum Sorusuna Var mısınız? Queen’s Puzzle

Satranç oynamayı sever misiniz? O zaman sizi heyecanladıracak bir haberimiz var…

“Queen’s Puzzle’ adı verilen satranç oyunundaki karmaşık durumu çözene 1 milyon dolar ödül teklif ediliyor.

“The Queen’s Puzzle”  ilk olarak 1848 yılında yazılmış. Soru şu: 8×8 bir satranç tahtasının üzerine 8 adet veziri öyle yerleştireceksiniz ki, iki vezirden biri diğerini doğrudan tehdit etmeyecek.

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.

Bu soru 92 farklı şekilde çözülebiliyor (yaklaşık 4.5 milyar olası kombinasyon arasında). Bu nedenle de matematikçiler uzun süreli bir çalışmayla işleri biraz daha ilginçleştirmek istemişler.

Olası çözümlerden bir tane

Toplamda 64 kareden oluşan sadece 8 x 8 standart boyutlu bir satranç tahtası ile sınırlı olmak yerine sorunun boyutlarını  herhangi bir sayıdaki vezir sayısını içerecek şekilde genişletsek ne olurdu?

Bu durumda 20 adet veziri 20×20’lik bir tahta üzerinde, ya da 100 adet veziri 100 x 100’lük bir tahta üzerinde yerleştirmek durumunda kalırdınız. Ve bunların hiç biri diğer vezirlerle aynı sırada, sütunda ya da diagonal olarak aynı hizada olmamalılar.

Sorunun “n-Queen’s Puzzle” olarak adlandırılan bu biçimi (n=sıra, sütun ve vezir sayısı) yüksek rakamlara eriştiğinde (örneğin n=1000), işler gerçekten, ama gerçekten karışmakta. Olasılıkların sayısı o denli artıyor ki, son derece güçlü bilgisayarlar bile aciz kalabiliyorlar.

Bu yeterince zor bir durum değilmiş gibi bir şart daha ekleniyor soruya: Vezirlerden bazıları önceden yarleştirilmiş ve sabit durmak zorunda olursa ne olur?

nxn tahta üzerinde bazı vezirler daha önceden yerleştirilmiş olsaydı, bu vezirleri hareket ettirmeden n-Queen’s puzzle’a bir çözüm getirebilir miydiniz?” diye soruyor  St. Andrews Üniversitesi’nden bilgisayar bilimcisi Ian Gent.

Soruyu kafanızda canlandırmak kolay olabilir ama, herhangi bir sayı için soruya etkin bir çözüm getirebilmek, işlemsel karmaşıklık alanının karşılaştığı en zor durumlar arasında yerini koruyor.

Gent, “Sorunu hızlı çözebilecek bir bilgisayar programı yazılabilinirse, bu çözüm bizi günlük hayatımızda etkileyen başka soruların çözümüne adapte edilebilir.” diyerek sorunun önemini vurguluyor.

Gent’in ekibi yayınladıkları makalede n-Queens Tamamlanma Sorunu’nun aslında bir P – NP Sorunu olduğunu belirtti. Bu, n-Queens Tamamlanma Sorunu’nu çözebilecek herhangi bir algoritmanın, NP sınıfındaki herhangi bir sorunu çözmek için dolaylı olarak kullanılabileceği anlamına gelir.

Gent’e göre, ödül herhangi bir algoritmanın bulmacayı makul bir sürede çözemeyeceğini kanıtlayarak veya hızlı bir şekilde çözebilecek bir algoritma geliştirerek ya da matematiksel olarak, polinom zamanı olarak bilinen şeyi kullanarak kazanılabilir.

Bu yüzden Clay Matematik Enstitüsü, Milenyum Ödüllü Sorularının bir parçası olarak soruyu çözebilecek herkese 1 milyon dolarlık bir ödül öneriyor.

Şimdiden kolay gelsin…

Not: Quenn Türkçe’de vezire karşılık gelmektedir.

Detaylı okuma: http://jair.org/papers/paper5512.html

Kaynak: http://www.sciencealert.com/if-you-like-chess-and-free-money-we-have-some-really-really-good-news

Matematiksel

 

Yazıyı Hazırlayan: Sibel Çağlar

Kadıköy Anadolu Lisesi, Marmara Üniversitesi İngilizce Matematik Öğretmenliği, ardından uzun süre özel sektörde matematik öğretmenliği, eğitim koordinatörlüğü diye uzar gider özgeçmişim… Önemli olan katedilen değil, biriktirdiklerimiz ve aktarabildiklerimizdir bizden sonra gelenlere... Eğitim sisteminin içinde bulunduğu çıkmazı yıllarca iliklerimde hissettikten sonra, peki ama ne yapabilirim düşüncesiyle bu web sitesini kurmaya karar verdim. 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.

Bunlara da Göz Atın

Nobel: Bilimin Zirvesi

Herkesin merakla beklediği 2017 Nobel ödülleri sahiplerini buldu. Tabi ödül alanları destekleyenler kadar eleştirenler de …

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir