1 Milyon Dolar Ödüllü Satranç sorusunun çözümüne katkı(?) (Python ile Birbirini yemeyen Kaleler)

1848 Yılında Max Bezzel, bir kuyuya taş atmış. Yıl olmuş 2017 hala insanları uğraştırıyor. Öyle ki geçtiğimiz günlerde Clay Mathematik enstitüsü Bezzel'in oraya attığı 8 Vezir sorusunu güncelleyerek, makul ve hızlı bir çözüm üreten algoritma için 1 Milyon Dolar Ödül koydu.

Sorunun orijinali şu şekilde: 8x8'lik Satranç tahtasına 8 veziri öyle bir şekilde yerleştirin ki, hiç bir vezir diğerini yemesin.

Sorunun güncel şekli ise şu: Öyle bir yöntem/yazılım olsun ki; NxN'lik Satranç tahtasına N tane veziri yerleştirsin ve hiç bir vezir diğerini yemesin. Hatta yazılım, rastgele sayıda bir birini yemeyen vezirler tahtaya yerleştirildikten sonra çalışmaya başladığında da kalan vezirleri yerleştirsin. Elbetteki bunu makul bir süre içinde yapsın.

NŞA'da sorunun orijinal halinin 4,5 milyar olasılık içinden 92 doğru çözümü var. Ancak soruyu klasik yöntemler kullanan bir yazılım ile çözmek hayli uzun sürüyor. Clay enstitüsü de aslında "teker teker deneme" yönetime alternatif arıyor ve bunun için böyle bir ödül veriyor.

İcraat'a gelelim..

Sorunun cevabı elbetteki burada yok. Güçlü bir alternatif bulmuş olsa idim, şimdi Clay'e yazıyor olurdum ;) Ancak normal bir işleyiş için prototip kabilinden bir kodlamanın nasıl olabileceğine dair yazdığım kodları paylaşacağım.

Bilindiği gibi Vezir, yatay dikey ve çapraz hareket etmekte. (Çapraz'ı da katınca benim makinada sonuç için hayli beklediği için yatay ve dikey eksenine yani aslında Kale için bir çözüm sunmuş olacağız)

• Önce, rastgele seçim için Choice modülü import ediyoruz
• Yatay eksen için harfleri, Dikey eksen için rakamları ayarlıyoruz
• Her karenin yerinin olduğu tahta dizisini elde ediyoruz( a1,a2... b1,b2.. h7,h8 )
• x defa, tekrar edecek şekilde; tahta içinden rasgele bir seçim yapıyoruz, yatay ve dikey koordinatına bakıp o yeri tahtadan çıkarıyor, kaleler'e ekliyoruz.
  her seferinde daha az seçenek arasına, rastgele bir kale ekliyor ve bunun yatay ve dikeylerini yine tahtadan çıkarıyoruz.

from random import choice
harfler=["a","b","c","d","e","f","g","h"]
x=8
tahta=[]
ar=[]
for i in harfler:
for j in range(1,x+1):
ar = [i,j]
tahta.append(ar)
kaleler=[]
for k in range(1,x+1):
r = choice(tahta); kaleler.append(r)
print "random yerlesim:", r
bas=r[0]; son=r[1]
for t in list(tahta):
if t[0]==bas: print "yatay elenen kesisim karesi",t; tahta.remove(t)
if t[1]==son:
print "dikey elenen kesisim karesi",t
try: tahta.remove(t)
except: pass

print "\n\n Birbirini Yemeyen Kale yerlesimleri:\n", kaleler, "\n\n"

Markdown Style ile pek de şık görünmedi.
Resim olarak da koyayım tab hatası olmasın. Python'da önemli malum..

Görsel 1, Görsel 2, Görsel 3