Matematikçi 150 yıllık satranç problemini çözdü

150 yıldan fazla bir süredir matematikçileri şaşkına çeviren bir satranç problemi sonunda çözüldü.

N-veliler problemi çok daha basit bir bulmaca olarak başladı ve ilk olarak Alman satranç gazetesi Schachzeitung'un 1848 sayısında satranç bestecisi Max Bezzel tarafından ortaya atıldı. Satranç tahtasındaki en güçlü taşlar olan ve herhangi bir sayıda kareyi yatay, dikey ve çapraz olarak hareket ettirebilen sekiz rakip vezirin, herhangi bir vezir diğerine saldırmadan 64 karelik standart bir tahtaya kaç farklı şekilde yerleştirilebileceğini sordu.

Sadece iki yıl sonra ortaya çıkan cevap, sekiz kraliçeyi birbirlerinin boğazından uzak tutan 92 konfigürasyon olduğu ve çözümlerin 12'si dışında tümünün basit rotasyonlar ve birbirlerinin yansımaları olduğuydu. Ancak 1869'da, matematikçi Franz Nauck, sorunun daha da şaşırtıcı bir yinelemesini istedi: Standart bir 8'e 8 tahtada sekiz kraliçeyi yapılandırmak yerine, 1.000'e 1.000'lik bir tahtada 1.000 kraliçeye ne dersiniz? Peki ya bir milyon, hatta bir milyar? 

Bir zamanlar nispeten basit olan bir bulmaca, çok daha derin bir matematik problemi haline gelmişti - bir n'ye n'lik bir tahtada herhangi bir sayıda kraliçeyi ('n' olarak temsil edilen) konumlandırmanın yollarının sayısı için genel bir kuralın keşfedilmesini gerektiren bir bulmaca. .  

Şimdi, Harvard Üniversitesi Matematik Bilimleri ve Uygulamaları Merkezi'nde matematikçi olan Michael Simkin, neredeyse kesin bir cevap buldu. 

Muazzam bir n'ye n tahtada, n tane vezir yerleştirmenin yaklaşık (0.143n)^n yolu vardır, böylece hiçbiri birbirine saldıramaz. Bu, milyonda bir tahtada, 1 milyon kraliçenin düzenlenebileceği tehditkar olmayan konfigürasyonların sayısının kabaca 1 ve ardından 5 milyon sıfır olduğu anlamına gelir.

Simkin'in bir denklemin bu yakın yaklaşımını bulması yaklaşık beş yılını aldı. Matematikçiler genellikle problemleri daha yönetilebilir parçalara ayırmanın yollarını bularak çözerler. Ancak, bir tahtanın merkezine daha yakın yerleştirilen vezirler, kenarlardaki vezirlerin saldırabileceğinden çok daha fazla kareye saldırabileceğinden, n-vezir sorunu oldukça asimetriktir ve bu nedenle, basitleştirmeye inatla dirençlidir.   

Zürih'teki İsviçre Federal Teknoloji Enstitüsü'nde matematikçi olan Zur Luria ile işbirliği yapan Simkin, başlangıçta, kenar karelerin bir halka şekli oluşturmak için tahtanın etrafına sarıldığı, problemin daha simetrik 'toroidal' bir versiyonunu düşünerek görevi basitleştirdi. . Bu düzenleme, örneğin vezirlerin sol üstte kaybolmasını ve sağ altta yeniden görünmesini sağlar. Aynı zamanda, nereye yerleştirilirlerse yerleştirilsinler, her vezirin muadilleriyle aynı sayıda kareye saldırabileceği anlamına gelir.

İlk yaklaşım olarak toroidal tahtayı kullanarak, iki matematikçi daha sonra probleme 'rastgele açgözlü algoritma' adı verilen bir strateji uyguladı. Rastgele bir vezir yerleştirdiler ve saldırdığı tüm kareleri bloke ettiler; daha sonra bir sonraki vezir, saldıran kareleri sırayla bloke edilerek kalan noktalara oturmak üzere seçilirdi. Çift, bir toroidal tahtadaki n kraliçenin konfigürasyonlarının sayısı üzerinde kaba bir alt sınır - veya mümkün olan en düşük sayı - bulana kadar bunu çoklu konfigürasyonlar üzerinde yapmaya devam etti. 

Ancak tahminleri mükemmel olmaktan uzaktı. Kartın etrafı saran yapısı, bazı konfigürasyonlarda son birkaç vezir konumunu bulmalarını engelledi. Sorunu birkaç yıl boyunca bıraktıktan sonra ikili, algoritmalarını normal bir tahtaya uyarlama fikriyle geri döndü ve bu da son kraliçeler için toroidal tahtadan daha fazla saklanma noktası sağladı. Rastgele açgözlü algoritmayı standart, toroidal olmayan bir tahtaya uyarlayarak çift, bu alt sınır tahmininin doğruluğunu biraz geliştirdi.

Ancak cevapları umdukları kadar net değildi - rastgele açgözlü algoritma, her karenin diğerleriyle aynı saldırı avantajını sağladığı simetrik problemlerde en iyi sonucu verir. Bu, kenar karelerin merkezdeki karelere göre çok daha az saldırı kabiliyetine sahip olduğu standart bir tahta için geçerli değildir. 

Bu sorunu çözmek için Simkin, algoritmayı uyarlaması gerektiğini fark etti. Standart bir tahtadaki uygulanabilir konfigürasyonların çoğunda, tahtanın kenarlarında - daha az kareye saldırdıkları yerlerde - merkezinden daha fazla kraliçe bulunduğundan, Simkin kareleri ağırlıklandırarak rastgele açgözlü algoritmayı geliştirdi. Vezirleri rastgele atayan algoritması yerine, tercihen vezirleri mümkün olan en fazla sayıda konfigürasyona ayrılacak noktalara yerleştirdi. Bu, Simkin'in her bir tahta bölümünde kaç tane kraliçenin işgal edeceğine odaklanmasına ve geçerli sayıda konfigürasyon için bir formül bulmasına izin verdi, böylece alt sınır tahmininin doğruluğunu daha da geliştirdi.

'Eğer bana, 'Vezirlerini tahtaya falanca şekilde koymanı istiyorum' deseydin, o zaman algoritmayı analiz edebilir ve sana bu kısıtlamaya uyan kaç tane çözüm olduğunu söyleyebilirdim, Simkin yaptığı açıklamada . 'Resmi anlamda, sorunu bir optimizasyon sorununa indirger.'

Ancak bir sayının alt sınırını bulmak, bundan daha büyük sonsuz bir sayı kümesi bırakır. Çözüme gerçekten ulaşmak için Simkin'in bir üst sınır bulması gerekiyordu. Sorunun bu ikinci yarısını çözmek için, tahtaya yeni bir vezir yerleştirildikten sonra saldırıya uğramayan karelerin sayısını not etmeyi içeren 'entropi yöntemi' adlı bir stratejiye döndü. Bu yöntemi kullanarak, alt sınırındaki sayıyla neredeyse mükemmel bir şekilde eşleşen bir sayıyı tüküren bir maksimum sınır formülü üretti; Simkin, formülü neredeyse kesin olarak uyguladığı sonucuna vardı.

Gelecekteki çalışmalar, iki sınırı birbirine daha da yakınlaştırmaya çalışabilir, ancak Simkin, kendisinden önceki herkesten daha yakın hale geldiğinden, bu zorluğu başka birinin fethetmesi için bırakmaktan memnundur.

Simkin, 'Kişisel olarak bir süreliğine n-kraliçeler sorunuyla işim bitebileceğini düşünüyorum.' Dedi. 'Yapacak başka bir şey olmadığı için değil, sadece satrancı hayal ettiğim ve hayatıma devam etmeye hazır olduğum için.'

Simkin, henüz hakemli olmayan çalışmasını arXiv ön baskı veritabanında yayınladı .

Author Zafer Öz