Aslında olayın satranç tahtasında filan geçmesine gerek yoktu. 64 kare olsun gerisi önemli değil. 64 karenin her birinde ya bir taş olabilir ya da boştur. Demek ki \(2^{64}\) başlangıç pozisyonumuz var. Kral bunların herhangi birini başlangıçta istediği gibi ya da rastgele dizebilir.
Olası her taş dizilimi tabii ki seçilmiş bir kareye karşılık geliyor, çünkü ikinci vezir tahtayı gördüğünde üzerinde böyle bir pozisyon olacak ve kendisi bu taş diziliminden doğru kareyi bulacak. Tabii bu taş diziliminden doğru kareyi bulma yöntemi kolay bir işlem olmalı, yoksa olası taş dizilimleri sayısı akıldı tutulabilecek bir küme değil.
Birinci vezir de olası bir taş diziliminden bu kare numarasına gidecek pozisyona tek bir değişiklikle gidebilecek bir yöntem bulmalı.
Eğer benim bu soruyla gereksiz boğuşmalarım yerine doğrudan cevaba geçmek istiyorsanız doğrudan çözüm bölümüne atlayabilirsiniz.
Bilmeceyi önce küçük sayıda kareli tahtalar için çözmeye çalıştım. Üç kare için çözüm bulmak kolaydı. Kareleri ikili düzende göstereceğim. Eğer karede taş varsa değeri 1, boş ise 0 olacak. Bu şekilde deneme yanılmayla aşağıdaki gibi bir çözüme ulaşmak kolay.
- kare anlamına gelen dizilimler: 000, 001, 110
- kare anlamına gelen dizilimler: 010, 101
- kare anlamına gelen dizilimler: 100, 011, 111
Herhangi bir pozisyondan bir başka pozisyon grubuna tek hamlede gidildiğini de deneyerek gösterdim:
[table id=17 /]
Bu tablodan da görüldüğü gibi bazı durumlarda birinci vezirin bir hamlesi yok ama bilmecenin birinci versiyonu için kurallara uygun olduğundan sorun değil diye düşündüm. Bundan sonra henüz bir düzen göremediğimden bir sonraki büyüklüğe geçtim ve 2×2 tahta için soruyu çözmeye başladım. Aslında dikkat edersek tahtanın 2×2 olması ya da 4×1 olması arasında bir fark yok. Önemli olan toplam dört kare olması.
Bu sefer tabii ki pozisyonların hangi karelere karşılık geldiğini bulmam üç karede olduğu kadar çabuk olmadı. Ne de olsa dağıtmam gereken pozisyon sayısı ufak bir büyümeye rağmen üstsel olarak artmaktaydı. Bunun için bu dağıtım aşamasında bazı ekstra kurallar bulmam gerektiğini düşündüm. İlk önce olası pozisyonları listeledim.
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
16 değişik pozisyon beni bekliyordu. Bu aşamada düşünebildiğim ilk kural şöyle bir taneydi. Bir dizilim sadece bir kare anlamına geliyordu, örneğin 0001 diziliminin 1. kare anlamına gelmesi gibi. Dolayısıyla bu pozisyondan diğer karelerin anlamlarına geçişler olmalıydı ve bu geçişlerin de sadece tek bir bit değişikliğiyle (yani sadece bir kareye taş koyarak ya da sadece bir kareden bir taş alarak) mümkün olması gerekiyordu. Ayrıca 4 kareden oluşan problem için herhangi bir dizilimden mesafesi 1 olan dönüşümler de tam 4 taneydi. Örneğin:
0000 başlangıç pozisyonu ise, bir bit değişikliğiyle elde edebileceğimiz farklı pozisyonlar 0001, 0010, 0100 ve 1000 olmak üzere 4 adettir.
Bunun üzerine her dizilim için 1 uzaklıkta olan dizilimleri işaretlemeye başladım. İşaretlemeleri azaltabilmek için yukarıda sırayla yazdığım ikilik düzendeki sayıları bu sefer Gray kodlama ile yazdım. Bu kodlamanın özelliği komşu iki sayı arasında her zaman 1 bir fark olmasıdır.
0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000
Bu listede de orijinal listedeki aynı sayılar var. Sadece sıralaması farklı. Dikkat edilirse listedeki son sayı ile ilk sayı arasındaki mesafe de 1 bit. Sonra sırayla her sayıyı aralarındaki mesafe 1 olan diğer sayılarla birleştirmeye başladım. Biraz karışık bir şekil çıkıyor ama bu büyüklükteki bir problem için kabul edilebilir bir durum bence. Burada bu problemin çizge teorisiyle bir ilişkisinin olabileceğini düşündüm ama o derinliklere girmeye gerek yok diye düşündüm.
Ondan sonra pozisyonları işaretlemeye başladım, yani hangi pozisyonun hangi kareye karşılık geldiğini. Sadece tek bir taşın bulunduğu pozisyonları kolaylık olsun diye o karenin numarasıyla eşleştirdim. Yani 0001 dizilimi 1. kare ile, 0010 dizilimi 2. kare ile, 0100 dizilimi 3. kare ile ve 1000 dizilimi de 3. kareye karşılık geldi. Bu eşleştirme 3 kare için olan çözümle de uyuşuyordu. Bağlantılarla beraber işlerin kolay olacağını düşünmüştüm ama ilk zorluk hemen ortaya çıktı. Bazı dizilimler için birden fazla aday vardı. Basitçe bir programla bu atamalar kolayca yapılabilirdi ama problem üzerine düşünme fırsatını da kaçırmayayım diye elle devam ettim. Bu arada bana yardımcı olacak başka kurallar da arıyordum. Bulabildiğim başka bir kural da şuydu:
Aynı kareye karşılık gelen iki dizilim arasındaki bit farkı iki olamaz.
Örneğin 0000 ve 0101 dizilimlerinin ikisi de 2 karesine karşılık gelsin. Bu iki dizilime de aynı mesafede olan başka bir dizilim olarak 0100 dizilimini alalım. Bu da başka bir kareye karşılık gelecektir. Her bir pozisyondan kendi karesinin de dahil olduğu dört değişik kareye tek hamlede gidebilmek gerekiyor, aslında üç başka kare yeterli ama problemin ikinci kısmına göre dördünü de düşünmeye başladım. Eğer her dizilim için sadece dört tane 1 mesafe uzaklıkta dizilim varsa ve bunların ikisi aynı kareye ait ise, bu pozisyondan en fazla 3 değişik kareye ulaşılabilir.
Bu yardımcı kuralı da kullanınca 4 kare için çözümlerden birini deneme yanılmayla da olsa kolayca bulabildim. Çözümleri bulabilmeme rağmen hala bir kural ya da genelleme bulamamıştım. Ayrıca beni daha da düşündüren şey ikinci vezirin durumuydu. 64 kare için çok fazla pozisyon olacağından doğru kareyi söylemesi için basit bir kural kullanması gerekiyordu.
Çözüm
Sonunda bu grupları deneme yanılma yerine basit bir işlemle bulan yöntemlere baktım. Bu yöntemlerden bir tanesi şöyle:
Elimizdeki kareleri 0’dan 63’e kadar numaralandıralım. Şimdi herhangi bir pozisyonun karşılık geldiği kareyi bulmak için şu işlemi yapalım. Üzerinde taş olan her karenin numarasını ikilik düzende alt alta yazıp bu sayıları toplayalım. Toplama işlemini yaparken eldeleri göz ardı edeceğiz. Buna xor işlemi denilmektedir. Bu işlemin güzel tarafı toplamanın da çıkarmanın da aynı işlemle yapılması. O zaman ikinci vezirin yapacağı işlem iyice kolaylaşacak. Bu yöntem ayrıca birinci vezirin de gruplara ayırmadan biraz daha uzun ama kolay bir işlem yapmasını sağlayacak.
Birinci vezir kralın hazırladığı pozisyon için bu toplamı hesaplar. Ardından kralın gösterdiği kareye bakar ve aynı işlemin bu sonucu vereceği bir işlem planlar. Bir örnekle bu işlemlere bir bakalım:
Başlangıçtaki pozisyonda 3., 7., 17. ve 24. karelerde taşlar olsun. Kral da 25. kareyi göstermiş olsun. Birinci vezir ilk önce şu işlemi yapacak
\(000011\oplus{000111\oplus{010001\oplus{011000}}}=001101=13 \)
İkinci vezirin hesaplaması gereken toplam ise 25 olduğundan birinci vezir hangi sayı ile 13 sayısının xor toplamının 25 olduğunu hesaplar. Bu da 20’dir. Yani birinci vezir 20. karede taş varsa alır, yoksa oraya taş koyar. Şimdi o işlemi hesaplayıp bunun işe yarayıp yaramadığını kontrol edelim.
\(000011\oplus{000111\oplus{010001\oplus{011000\oplus{010100}}}}=011001=25 \)
Bu durum için bu yöntem çalıştı ama acaba her durum için bir çözüm olacak mı? İlk önce ilk pozisyonun ürettiği toplamla kralın seçtiği karenin aynı olması durumunda ne olacağına kısaca bir bakalım. Bu durumda birinci vezir hamlesinde sıfırıncı karedeki taşı alacaktır ya da o kareye taş koyacaktır. Sıfırıncı karede taş olsa da olmasa da xor toplamına katkısı sıfırdır ama bu esneklik çok güzel bir problemi de çözüyor. Problemin ikinci varyantı bu şekilde her zaman çözülebiliyor, çünkü her pozisyonun sıfırıncı karenin değişik olduğu ikizi de aynı kareye karşılık geliyor ve kral bu kareyi seçse bile birinci vezirin her zaman yapacak bir hamlesi oluyor.
Diğer durumlarda da 0 ile 63 arasındaki bir sayıyla toplandığında (xor) 0 ile 63 arasındaki bütün sayıları verecek bir kare numarası her zaman bulunacaktır. En azından 64 kare için. Bunun ispatını şimdilik bu yazıda vermeyeceğim. İleride belki bunun için ayrı bir yazı yazarım, referans veririm ya da belki bu yazıya ek yaparım.