Satranç oynamayı sever misiniz? O zaman size güzel 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.
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